2.4 堆排序
2.4.1 堆排序基本思想
堆排序 (Heapsort) 是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
2.4.2 堆排序实现代码
public static void heapSort(int[] array){ crearMaxheap(array); int end=array.length-1; while(end>0){ swap(array,0,end); siftDown(array,0,end); end--; } } private static void crearMaxheap(int[] array){ for (int parent = (array.length-1-1)/2; parent >=0 ; parent--) { siftDown(array,parent,array.length); } } private static void siftDown(int[] array,int parent,int len){ int child=2*parent+1; while(child<len){ if(child+1<len && array[child+1]>array[child]){ child=child+1; } //孩子最大值以及找到 if(array[child]>array[parent]){ swap(array,child,parent); parent=child; child=2*parent+1; }else{ break; } } }
2.4.3 堆排序特性总结
- 堆排序使用堆来选数，效率就高了很多。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(1)
- 稳定性：不稳定
2.5 冒泡排序
2.5.1 冒泡排序基本思想
就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特
点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
2.5.2 冒泡排序实现代码
public static void bubbleSort(int[] array){ for (int i = 0; i < array.length-1; i++) { boolean flg=false; for (int j = 0; j < array.length-1-i; j++) { if(array[j]>array[j+1]){ swap(array,j,j+1); flg=true; } } if(flg==false){ break; } } }
2.5.3 冒泡排序特性总结
- 冒泡排序是一种非常容易理解的排序
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：稳定
2.6 快速排序
2.6.1 快速排序基本思想
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
2.6.2 快速排序实现代码
public static void quickSort(int[] array){ int start=0; int end= array.length-1; quick(array,start,end); } private static void quick(int[] array,int start,int end){ if(start>=end){ return; } int pivot=paratition(array,start,end); quick(array,start,pivot-1); quick(array,pivot+1,end); } //选轴值 private static int paratitionHoare(int[] array,int left,int right){ int i=left; int tmp=array[left]; while (left<right){ while (left<right && array[right]>=tmp){ right--; } while (left<right && array[left]<=tmp){ left++; } swap(array,left,right); } swap(array,i,left); return left; } //选基准的两种方法 //挖坑法 private static int paratition(int[] array,int left,int right){ int tmp=array[left]; while(left<right){ while (left<right && array[right]>=tmp){ right--; } array[left]=array[right]; while (left<right && array[left]<=tmp){ left++; } array[right]=array[left]; } //相遇之后，把tmp放到坑里 array[left]=tmp; return left; }
2.6.3 快速排序非递归实现
private static void quickNor(int[] array,int start,int end){ if(start>=end){ return; } Stack<Integer> stack=new Stack<>(); int pivot=paratitionHoare(array,start,end); if(pivot-1>start){ //说明左边有2个以上的元素 stack.push(start); stack.push(pivot-1); } if(pivot+1<end){ //说明右边有2个以上的元素 stack.push(pivot+1); stack.push(end); } while (!stack.isEmpty()){ end=stack.pop(); start=stack.pop(); pivot=paratitionHoare(array,start,end); if(pivot-1>start){ //说明左边有2个以上的元素 stack.push(start); stack.push(pivot-1); } if(pivot+1<end){ //说明右边有2个以上的元素 stack.push(pivot+1); stack.push(end); } }
2.6.4 快速排序特性总结
- 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
- 时间复杂度：O(N*logN)
- 空间复杂度：O(logN)
- 稳定性：不稳定
2.7 归并排序
2.7.1 归并排序基本思想
归并排序（ MERGE-SORT ）是建立在归并操作上的一种有效的排序算法 , 该算法是采用分治法（ Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：
2.7.2 归并排序实现代码
public static void mergeSort(int[] array){ mergeSortFun(array,0,array.length-1); } private static void mergeSortFun(int[] array,int start,int end){ if(start>=end){ return; } int mid=(start+end)/2; mergeSortFun(array,start,mid); mergeSortFun(array,mid+1,end); //开始合并 merge(array,start,mid,end); } private static void merge(int[] array,int left,int mid,int right){ int s1=left; int e1=mid; int s2=mid+1; int e2=right; int k=0; int[] tmpArr=new int[right-left+1]; while (s1<=e1 && s2<=e2){ if(array[s1]<=array[s2]){ tmpArr[k++]=array[s1++]; }else { tmpArr[k++]=array[s2++]; } } while (s1<=e1){ tmpArr[k++]=array[s1++]; } while (s2<=e2){ tmpArr[k++]=array[s2++]; } for (int i = 0; i < tmpArr.length; i++) { array[i+left]=tmpArr[i]; } }
2.7.3 归并排序非递归实现
public static void mergeSortNor(int[] array){ int gap=1; while (gap<array.length){ for (int i = 0; i < array.length; i+=gap*2) { int left=i; int mid=left+gap-1; int right=mid+gap; //mid和right可能会越界 if(mid>=array.length){ mid=array.length-1; } if(right>=array.length){ right=array.length-1; } merge(array,left,mid,right); } gap*=2; } }
2.7.4 归并排序特性总结
- 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(N)
- 稳定性：稳定
三、排序算法复杂度及稳定性一览表
| 排序方法 | 最好 | 平均 | 最坏 | 空间复杂度 | 稳定性 |
| 冒泡排序 | O(n) | O(n^2) |
O(n^2) | O(1) | 稳定 |
| 插入排序 | O(n) | O(n^2) |
O(n^2) |
O(1) | 稳定 |
| 希尔排序 | O(n) | O(n^1.3) | O(n^2) | O(1) | 不稳定 |
| 堆排序 | O(n*logn) | O(n*logn) | O(n*logn) | O(1) | 不稳定 |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
快速排序O(n*logn)O(n*logn)
O(n^2)
O(log(n)) ~ O(n)
不稳定归并排序O(n*logn)O(n*logn)O(n*logn)O(n)稳定
