Java의 정렬 알고리즘은 무엇입니까?
- WBOY앞으로
- 2023-05-05 11:13:14737검색
1. 버블 정렬
import java.util.Arrays;//冒泡排序public class BubbleSort_01 {
public static void main(String[] args) {
int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
//记录比较次数
int count=0;
//i=0,第一轮比较
for (int i = 0; i < a.length-1; i++) {
//第一轮，两两比较
for (int j = 0; j < a.length-1-i; j++) {
if (a[j]>a[j+1]) {
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
count++;
}
}
System.out.println(Arrays.toString(a));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
System.out.println("一共比较了："+count+"次");//一共比较了：105次
}}버블 정렬 최적화 1:
import java.util.Arrays;public class BubbleSort1_01 {
public static void main(String[] args) {
int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
int count=0;
for (int i = 0; i < a.length-1; i++) {
boolean flag=true;
for (int j = 0; j < a.length-1-i; j++) {
if (a[j]>a[j+1]) {
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
flag=false;
}
count++;
}
if (flag) {
break;
}
}
System.out.println(Arrays.toString(a));// [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
System.out.println("一共比较了："+count+"次");//一共比较了：95次
}}2.Select Sort
import java.util.Arrays;//选择排序:先定义一个记录最小元素的下标，然后循环一次后面的，找到最小的元素，最后将他放到前面排序好的序列。public class SelectSort_02 {
public static void main(String[] args) {
int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
for (int i = 0; i < a.length-1; i++) {
int index=i;//标记第一个为待比较的数
for (int j = i+1; j < a.length; j++) { //然后从后面遍历与第一个数比较
if (a[j]<a[index]) { //如果小,就交换最小值
index=j;//保存最小元素的下标
}
}
//找到最小值后，将最小的值放到第一的位置，进行下一遍循环
int temp=a[index];
a[index]=a[i];
a[i]=temp;
}
System.out.println(Arrays.toString(a));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
}}3.
rreee4 . 쉘 정렬(Shell Sort)
import java.util.Arrays;//插入排序:定义一个待插入的数，再定义一个待插入数的前一个数的下标，然后拿待插入数与前面的数组一一比较，最后交换。public class InsertSort_03 {
public static void main(String[] args) {
int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
for (int i = 0; i < a.length; i++) { //长度不减1，是因为要留多一个位置方便插入数
//定义待插入的数
int insertValue=a[i];
//找到待插入数的前一个数的下标
int insertIndex=i-1;
while (insertIndex>=0 && insertValue <a[insertIndex]) {//拿a[i]与a[i-1]的前面数组比较
a[insertIndex+1]=a[insertIndex];
insertIndex--;
}
a[insertIndex+1]=insertValue;
}
System.out.println(Arrays.toString(a));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
}}5. 퀵 정렬(Quick Sort)
import java.util.Arrays;//希尔排序：插入排序的升级public class ShellSort_04 {
public static void main(String[] args) {
int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
int count=0;//比较次数
for (int gap=a.length / 2; gap > 0; gap = gap / 2) {
//将整个数组分为若干个子数组
for (int i = gap; i < a.length; i++) {
//遍历各组的元素
for (int j = i - gap; j>=0; j=j-gap) {
//交换元素
if (a[j]>a[j+gap]) {
int temp=a[j];
a[j]=a[j+gap];
a[j+gap]=temp;
count++;
}
}
}
}
System.out.println(count);//16
System.out.println(Arrays.toString(a));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
}}
6. 
import java.util.Arrays;//快速排序：冒泡排序的升华版public class QuickSort_05 {
public static void main(String[] args) {
//int a[]={50,1,12,2};
int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
quicksort(a,0,a.length-1);
System.out.println(Arrays.toString(a));
}
private static void quicksort(int[] a, int low, int high) {
int i,j;
if (low>high) {
return;
}
i=low;
j=high;
int temp=a[low];//基准位,low=length时，会报异常，java.lang.ArrayIndexOutOfBoundsException: 4 ，所以必须在if判断后面,就跳出方法。
while(i<j){
//先从右边开始往左递减，找到比temp小的值才停止
while ( temp<=a[j] && i<j) {
j--;
}
//再看左边开始往右递增，找到比temp大的值才停止
while ( temp>=a[i] && i<j) {
i++;
}
//满足 i<j 就交换,继续循环while(i<j)
if (i<j) {
int t=a[i];
a[i]=a[j];
a[j]=t;
}
}
//最后将基准位跟 a[i]与a[j]相等的位置，进行交换,此时i=j
a[low]=a[i];
a[i]=temp;
//左递归
quicksort(a, low, j-1);
//右递归
quicksort(a, j+1, high);
}}7. 힙 정렬(Heap Sort)Heap Sort 1단계: 초기 힙 buildHeap을 빌드하고 싱크(arr, i, length)를 사용하여 힙 상단 값을 조정합니다.
2단계: 힙의 최상위 요소를 싱크하는 목적은 가장 큰 요소를 힙의 맨 위에 띄운 다음 싱크(arr, 0,length)를 사용하여 조정하는 것입니다.
import java.util.Arrays;//归并排序public class MergeSort_06 {
public static void main(String[] args) {
int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
//int a[]={5,2,4,7,1,3,2,2};
int temp[]=new int[a.length];
mergesort(a,0,a.length-1,temp);
System.out.println(Arrays.toString(a));
}
private static void mergesort(int[] a, int left, int right, int[] temp) {
//分解
if (left<right) {
int mid=(left+right)/2;
//向左递归进行分解
mergesort(a, left, mid, temp);
//向右递归进行分解
mergesort(a, mid+1, right, temp);
//每分解一次便合并一次
merge(a,left,right,mid,temp);
}
}
/**
*
* @param a 待排序的数组
* @param left 左边有序序列的初始索引
* @param right 右边有序序列的初始索引
* @param mid 中间索引
* @param temp 做中转的数组
*/
private static void merge(int[] a, int left, int right, int mid, int[] temp) {
int i=left; //初始i，左边有序序列的初始索引
int j=mid+1;//初始化j，右边有序序列的初始索引（右边有序序列的初始位置即中间位置的后一位置）
int t=0;//指向temp数组的当前索引，初始为0
//先把左右两边的数据（已经有序）按规则填充到temp数组
//直到左右两边的有序序列，有一边处理完成为止
while (i<=mid && j<=right) {
//如果左边有序序列的当前元素小于或等于右边的有序序列的当前元素，就将左边的元素填充到temp数组中
if (a[i]<=a[j]) {
temp[t]=a[i];
t++;//索引向后移
i++;//i后移
}else {
//反之，将右边有序序列的当前元素填充到temp数组中
temp[t]=a[j];
t++;//索引向后移
j++;//j后移
}
}
//把剩余数据的一边的元素填充到temp中
while (i<=mid) {
//此时说明左边序列还有剩余元素
//全部填充到temp数组
temp[t]=a[i];
t++;
i++;
}
while (j<=right) {
//此时说明左边序列还有剩余元素
//全部填充到temp数组
temp[t]=a[j];
t++;
j++;
}
//将temp数组的元素复制到原数组
t=0;
int tempLeft=left;
while (tempLeft<=right) {
a[tempLeft]=temp[t];
t++;
tempLeft++;
}
}
}8. Counting Sort (Count Sort)
참조 링크
알고리즘의 단계는 다음과 같습니다.
정렬할 배열에서 가장 큰 요소 max를 찾습니다.
i 값을 갖는 각 요소의 발생 횟수를 계산합니다. 배열에 i번째 항목을 입력하고
- 모든 개수를 누적합니다(count의 첫 번째 요소부터 시작하여 각 항목이 이전 항목에 추가됨)
- 대상 배열 채우기 역순으로: 새 배열의 count [i] 항목에 배치된 각 요소를 추가합니다. 요소가 배치될 때마다 count [i]가 차감됩니다
-
public class Heap_Sort_07 { public static void main(String[] args) { int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48}; sort(a); System.out.println(Arrays.toString(a)); } public static void sort(int[] arr) { int length = arr.length; //构建堆 buildHeap(arr,length); for ( int i = length - 1; i > 0; i-- ) { //将堆顶元素与末位元素调换 int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; //数组长度-1 隐藏堆尾元素 length--; //将堆顶元素下沉 目的是将最大的元素浮到堆顶来 sink(arr, 0,length); } } private static void buildHeap(int[] arr, int length) { for (int i = length / 2; i >= 0; i--) { sink(arr,i, length); } } private static void sink(int[] arr, int index, int length) { int leftChild = 2 * index + 1;//左子节点下标 int rightChild = 2 * index + 2;//右子节点下标 int present = index;//要调整的节点下标 //下沉左边 if (leftChild < length && arr[leftChild] > arr[present]) { present = leftChild; } //下沉右边 if (rightChild < length && arr[rightChild] > arr[present]) { present = rightChild; } //如果下标不相等 证明调换过了 if (present != index) { //交换值 int temp = arr[index]; arr[index] = arr[present]; arr[present] = temp; //继续下沉 sink(arr, present, length); } }}9. -
버킷 정렬(Bucket Sort)은 정렬할 데이터를 여러 개의 버킷으로 나누어 각 버킷에 있는 데이터를 차례로 꺼내는 방식입니다. 정렬을 완료합니다.
버킷 정렬: i 값을 가진 요소를 버킷 i에 넣고 마지막으로 버킷에 있는 요소를 순서대로 쏟아 붓습니다.
버킷 정렬 순서 아이디어:
양적 배열을 빈 버킷으로 설정합니다.
순서를 검색하여 해당 버킷에 항목을 하나씩 넣습니다. 
- 비어있지 않은 버킷의 항목을 원래 시퀀스에 다시 넣습니다.
-
import java.util.Arrays;public class CountSort_08 { public static void main(String[] args) { int[] array = { 4, 2, 2, 8, 3, 3, 1 }; // 找到数组中最大的值 ---> max:8 int max = findMaxElement(array); int[] sortedArr = countingSort(array, max + 1); System.out.println("计数排序后的数组： " + Arrays.toString(sortedArr)); } private static int findMaxElement(int[] array) { int max = array[0]; for (int val : array) { if (val > max) max = val; } return max; } private static int[] countingSort(int[] array, int range) { //range:8+1 int[] output = new int[array.length]; int[] count = new int[range]; //初始化： count1数组 for (int i = 0; i < array.length; i++) { count[array[i]]++; } //计数： count2数组，累加次数后的，这里用count2区分 for (int i = 1; i < range; i++) { count[i] = count[i] + count[i - 1]; } //排序：最后数组 for (int i = 0; i < array.length; i++) { output[count[array[i]] - 1] = array[i]; count[array[i]]--; } return output; }}10. Radix Sort (Raix Sort) - 정렬할 배열 [53, 3, 542, 748, 14, 214]이 있다고 가정하는데, radix sort를 사용하여 정렬하는 방법은 무엇인가요?
먼저 기수 정렬의 버킷이라고도 하는 이와 같은 10개의 1차원 배열이 있습니다. 버킷 정렬을 사용하여 구현되었습니다.
첫 번째 라운드에서는 요소의 한 자리 숫자로 구분합니다: [542, 53, 3, 14, 214,748]
두 번째 라운드에서는 요소의 열 자리 숫자로 구분합니다: [3, 14, 214, 542, 748, 53]
세 번째 라운드는 요소의 100번째 자리로 구분됩니다: [3, 14, 53, 214, 542, 748]
public class BucketSort_09 {
public static void sort(int[] arr){
//最大最小值
int max = arr[0];
int min = arr[0];
int length = arr.length;
for(int i=1; i<length; i++) {
if(arr[i] > max) {
max = arr[i];
} else if(arr[i] < min) {
min = arr[i];
}
}
//最大值和最小值的差
int diff = max - min;
//桶列表
ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();
for(int i = 0; i < length; i++){
bucketList.add(new ArrayList<>());
}
//每个桶的存数区间
float section = (float) diff / (float) (length - 1);
//数据入桶
for(int i = 0; i < length; i++){
//当前数除以区间得出存放桶的位置 减1后得出桶的下标
int num = (int) (arr[i] / section) - 1;
if(num < 0){
num = 0;
}
bucketList.get(num).add(arr[i]);
}
//桶内排序
for(int i = 0; i < bucketList.size(); i++){
//jdk的排序速度当然信得过
Collections.sort(bucketList.get(i));
}
//写入原数组
int index = 0;
for(ArrayList<Integer> arrayList : bucketList){
for(int value : arrayList){
arr[index] = value;
index++;
}
}
}}
Radix 정렬은 교환하는 것입니다. space for time 고전적인 알고리즘은 데이터가 충분할 때, 수천만에 도달하면 메모리 공간이 부족하여 힙 메모리 오버플로가 발생합니다
위 내용은 Java의 정렬 알고리즘은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
성명：
이 기사는 yisu.com에서 복제됩니다. 침해가 있는 경우 admin@php.cn으로 문의하시기 바랍니다. 삭제