排序算法（初级版）之快排、归并、堆排序
排序算法是算法中的基础，也是面试常问常考的算法之一，今天先简单整理一下最常考的三个排序算法。以后有空（希望有空）了再统一优化一下。
七大排序算法的复杂度分析
| 排序算法 | 最坏时间辅助度 | 平均时间复杂度 | 空间复杂度 | 稳定性 | 备注 |
| 冒泡排序 | O(n^2) | O(n^2) | O(1) | YES | |
| 交换排序 | O(n^2) | O(n^2) | O(1) | YES | |
| 选择排序 | O(n^2) | O(n^2) | O(1) | 不稳定 | |
| 插入排序 | O(n^2) | O(n^2) | O(1) | YES | |
| 希尔排序 | O(n^s)1<s<2 | O(NlogN) | O(1) | 不稳定 | |
| 快速排序 | O(n^2) | O(NlogN) | O(1) | 不稳定 | |
| 归并排序 | O(NlogN) | O(NlogN) | O(n) | YES | |
| 堆排序 | O(NlogN) | O(NlogN) | O(1) | 不稳定 |
快速排序：最坏时间复杂度为O(n^2)，平均为O(NlogN)。当原数组已是排好序的，时间效率最差。总而言之，原数组越乱，效率越高。
之前整理过一篇，做过详细的分析，但是代码可读性不太好，今天重新写一遍代码。
public void quickSort(int[] num,int begin,int end){ if(num == null || begin >= end) return; int tem = num[end]; int i = 0, j = end; while(i < j){//时刻检查i < j while(i < j && num[i] < tem){i++;} if(i < j)num[j--] = num[i]; while(i < j && num[j] > tem){ j--;} if(i < j)num[i++] = num[j]; } num[j] = tem; quickSort(num, begin, i - 1); quickSort(num, i + 1, end); }
归并排序：最坏时间复杂度达到了O(NlogN)。空间复杂度只有O(n)，非常棒。但是大数据的话，好像没有快排效率高。
mergeSort是我最喜欢的算法。同快排一样，分治法的实现，写起来，朗朗上口。
本算法我偷懒，开辟了额外的空间，这样写起来不需要来回的检查边界，比较方便，道理都是一样的，可以看之前的总结，算法过程总结的比较详细。
public int[] mergeSort(int[] num) { if (num == null || num.length == 0) return null; if (num.length == 1) return num; int[] former = mergeSort(Arrays.copyOfRange(num, 0, num.length >> 1)); int[] latter = mergeSort(Arrays.copyOfRange(num, num.length >> 1, num.length)); return merge(former, latter); } private int[] merge(int[] num1, int[] num2) { if (num1 == null || num1.length == 0) return num2; if (num2 == null || num2.length == 0) return num1; int i = 0, j = 0, index = 0; int[] res = new int[num1.length + num2.length]; while (i < num1.length && j < num2.length) { if (num1[i] < num2[j]) { res[index++] = num1[i++]; } else { res[index++] = num2[j++]; } } while (j < num2.length) { res[index++] = num2[j++]; } while (i < num1.length) { res[index++] = num1[i++]; } return res; }
堆排序：最坏时间复杂度达到了O(NlogN)。空间复杂度只有O(1)，非常棒。但是大数据的话，好像没有快排效率高。（跟merge一样，不信你试试！）
堆排序的最主要的操作在于调整堆，建堆的过程其实还是调整堆的过程。之前的总结比较详细，不太明白的可以看这里。之前的总结用了迭代实现，这里用了递归，更符合树的特点
public class HeapSort { public void heapSort(int[] array){ if(array == null || array.length <= 1) return; buildHeap(array);//build the heap int length = array.length; while(length > 1){ swap(array, 0, length - 1); adjust(array, --length, 0); } } private void buildHeap(int[] heap){ for(int i = heap.length / 2; i >= 0; i--){ adjust(heap,heap.length, i); } } private void adjust(int[] a,int length,int k){ int left = 2 * k + 1; int right = 2 * k + 2; if(left < length || right < length){ int min = k; if(left < length && a[left] < a[min]){ min = left; } if(right < length && a[right] < a[min]){ min = right; } if(min != k){ swap(a, min, k); adjust(a,length, min); } } } private void swap(int[] a,int i ,int j){ if(i != j){ a[i] += a[j]; a[j] = a[i] - a[j]; a[i] -= a[j]; } } public static void main(String[] args) { int[] a = {1,3,5,7,9,0,2,4,6,8}; HeapSort test = new HeapSort(); test.heapSort(a); System.out.println(Arrays.toString(a)); } }