Loading... # 排序算法 ## 冒泡排序 > (O(n<sup>2</sup>)/O(n)/O(n<sup>2</sup>)|O(1),稳定) 依次交换相邻元素最值，最值沉降至末尾 ```java public void bubbleSort(int[] arr){ int temp = 0; boolean flag = false; for (int i = 1; i < arr.length-1; i++) { flag = false; for (int j = 0; j < arr.length-1-i; j++) { if(arr[j]>arr[j+1]){//排序顺序决断点 temp = arr[j+1]; arr[j+1] = arr[j]; arr[j] = temp flag = true } } if(!flag){ break; } } } ``` ## 选择排序 > (O(n<sup>2</sup>)/O(n<sup>2</sup>)/O(n<sup>2</sup>)|O(1),不稳定) 依次查询最值放在前面 ```java public void selectSort(int[] arr){ int min = 0; int index = 0; for(int i= 0;i< arr.length-1;i++){ min = arr[i]; index = i; for(int j=i+1;j<arr.length;j++){ if(min>arr[j]){//排序顺序决断点 min = arr[j]; index = j; } } if(index!=i){ arr[index] = arr[i]; arr[i] =min; } } } ``` ## 插入排序 > (O(n<sup>2</sup>)/O(n)/O(n<sup>2</sup>)|O(1),稳定) 序列分为有序序列和无序序列，依次从无序序列插入值到有序序列中 ```java public void insertSort(int[] arr){ int insertVal = 0; int index = 0; for(int i=1;i<arr.length;i++){ insertVal = arr[i]; index = i-1; while(index>=0 && insertVal < arr[index]){//排序顺序决断点 arr[index+1] = arr[index]; index--; } arr[index+1] = insertVal; } } ``` ## 快速排序-冒泡排序PRO > (O(nlog<sub>2</sub>n)/O(nlog<sub>2</sub>n)/O(n<sup>2</sup>)|O(nlog<sub>2</sub>n),不稳定) ```java public void quickSort(int[] arr,int low,int high){ int temp =arr[low]; int i = low; int j = high; while(i<j){ //从高下标找比目标值小的 while(i<j && temp<=arr[j]){ j--; } if(i<j){ arr[i++] = arr[j]; } //从低下标找比目标值大的 while(i<j && temp>=arr[i]){ i++; } if(i<j){ arr[j--] = arr[i]; } arr[i] = temp; quickSort(arr,low,i-1); quickSort(arr,i+1,high); } } ``` ## 希尔排序-插入排序PRO > (O(n<sup>1.3</sup>)/O(n)/O(n<sup>2</sup>)|O(1),不稳定) ```java //交换法-更快 public void shellSort(int[] arr){ int insertVal = 0; int insertIndex = 0; for(int gap = arr.length/2 ;gap>0 ;gap/=2){ for(int i=gap;i<arr.length;i++){ insertVal = arr[i]; insertIndex = i; while(insertIndex-gap>=0 && insertVal<arr[insertIndex-gap]){ arr[insertIndex] = arr[insertIndex-gap]; insertIndex-=gap; } arr[insertIndex] = insertVal; } } } //移位法 public void insertSort(int[] arr){ int insertVal = 0; int index = 0; for(int i=1;i<arr.length;i++){ insertVal = arr[i]; index = i-1; while(index>=0 && insertVal < arr[index]){//排序顺序决断点 arr[index+1] = arr[index]; index--; } arr[index+1] = insertVal; } } ``` ## 归并排序 > (O(nlog<sub>2</sub>n)/O(nlog<sub>2</sub>n)/O(nlog<sub>2</sub>n)|O(1),稳定) ```java //将数组分成小数组直至两两元素比较 public void mergeSort(int[] arr,int low,int high){ if(low<high){ int mid = (low + high)/2; mergeSort(arr,low,mid); mergeSort(arr,mid+1,high); merge(arr,low,mid,high); } } //合并两个已排序数组 public void merge(int[] arr,int low ,int mid,int high){ int[] temp = new int[high-low+1]; int tempIndex = 0; int i = low; int j = mid+1; while(i<=mid&&j<=high){ if(arr[i]<=arr[j]){ temp[tempIndex++] = arr[i++]; }else{ temo[tempIndex++] = arr[j++]; } } while(i<=mid){ temp[tempIndex++] = arr[i++]; } while(j<=high){ temo[tempIndex++] = arr[j++]; } tempIndex=0; while(tempIndex<temp.length)){ arr[low++] = temp[tempIndex]; } } ``` ## 堆排序 > (O(nlog<sub>2</sub>n)/O(nlog<sub>2</sub>n)/O(nlog<sub>2</sub>n)|O(1),不稳定) ```java public void heapOrder(int[] arr){ for(int i=arr.length/2-1;i>0;i--){ adjustHeap(arr,i,arr.length) } //调整好的大/小顶堆 int temp = 0; for(int i = arr.length-1;i>0;i--){ //首尾交换，最值沉降到末尾，待排序元素数量-1 temp = arr[i]; arr[i] = arr[0]; arr[0] = temp; //因交换，顶堆被打乱，重新调整 adjustHeap(arr,0,i); } } public void adjustHeap(int[] arr,int index,int length){ int temp = arr[index]; for(int i=2*index+1;i<length;i=2*i+1){ if(i+1<length && arr[i]<arr[i+1]){ i++; } if(temp<arr[i]){ arr[index] = arr[i]; index = i; }else{ break; } arr[i] = temp; } } ``` Last modification：October 14th, 2020 at 10:46 pm © 允许规范转载
