【Java笔记】七大排序

1. 直接插入排序

时间复杂度： 最坏情况：O(n ² ) 最坏情况：O(n)
空间复杂度： O(1)
稳定性： 稳定

如果一个排序本身就是稳定的排序那么他可以被实现为不稳定的排序
但是如果一个排序本身就是不稳定的排序那么他就不可能被实现为稳定的排序
当数据趋于有序使用直接插入排序最快

代码：

	// 1. 直接插入排序public static void insertSort(int[] array) {for (int i = 1; i < array.length; i++) {int tmp = array[i];int j = i - 1;for (; j >= 0; j--) {if (array[j] > tmp) {array[j + 1] = array[j];} else {break;}}array[j + 1] = tmp;}}

过程演示：

2. 希尔排序

时间复杂度： O(n ^1.3 ) ~ O(n ^1.5 )
空间复杂度： O(1)
稳定性： 不稳定

	// 2. 希尔排序public static void shellSort(int[] array) {int gap = array.length;while (gap > 0) {gap /= 2;shell(array, gap);}}private static void shell(int[] array, int gap) {for (int i = gap; i < array.length; i++) {int tmp = array[i];int j = i - gap;for (; j >= 0 ; j -= gap) {if (array[j] > tmp) {array[j + gap] = array[j];} else {break;}}array[j + gap] = tmp;}}

演示：

3. 选择排序

时间复杂度： O(n ² )
空间复杂度： O(1)
稳定性： 不稳定

方式一：

	// 3. 选择排序public static void selectSort(int[] array) {for (int i = 0; i < array.length; i++) {int minIndex = i;for (int j = i + 1; j < array.length; j++) {if (array[j] < array[minIndex]) {minIndex = j;}}swap(array, i, minIndex);}}private static void swap(int[] array, int i, int minIndex) {int tmp = array[i];array[i] = array[minIndex];array[minIndex] = tmp;}

过程演示：

方式二：
时间复杂度： O(n ² )

	// 方式二public static void selectSort2(int[] array) {int left = 0;int right = array.length - 1;while (left < right) {int minIndex = left;int maxIndex = left;for (int i = left + 1; i <= right; i++) {if (array[i] < array[minIndex]) {minIndex = i;}if (array[i] > array[maxIndex]) {maxIndex = i;}}swap(array, left, minIndex);// 第一个数据是最大值if (left == maxIndex) {maxIndex = minIndex;}swap(array, right, maxIndex);left++;right--;}}

过程演示：

4. 堆排序(重要)

时间复杂度： O(N*logN )
空间复杂度： O(1)
稳定性： 不稳定

	// 4. 堆排序public static void heapSort(int[] array) {// 创建大根堆creatHeap(array);int end = array.length - 1;while (end > 0) {// 交换swap(array, 0, end);// 向下调整siftDown(array, 0, end);end--;}}private static void creatHeap(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] < array[child + 1]){child++;}if (array[child] > array[parent]) {swap(array, child, parent);parent = child;child = 2 * parent + 1;} else {break;}}}

5. 冒泡排序

时间复杂度： O(n ² ) 下面代码最好情况是：O(n)
空间复杂度： O(1)
稳定性： 稳定

	// 5. 冒泡排序public static void bubbleSort(int[] array) {// i 代表的是趟数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;}}// 如果flg == false，说明没有进入if语句，表示数组已经有序了，无需再排序，直接break即可if (!flg) {break;}}}

6. 快速排序（重要）

6.1 Hoare 法

时间复杂度： 最坏情况是单分支的树（1,2,3,4,5）O(n ² ) ，但是一般不会这么用；最好情况是：O(n*logn)
空间复杂度： 最坏情况：单分支的树O(n)；最好情况O(logn)
稳定性： 不稳定

	// 6. 快速排序// hoare 版public static void quickSort(int[] array) {quick(array, 0, array.length - 1);}private static void quick(int[] array, int left, int right) {if (left >= right) {return;}// 划分int par = partition(array, left, right);quick(array, left, par - 1);quick(array, par + 1, right);}private static int partition(int[] array, int start, int end) {int i = start; // 保存start初始位置int pivot = array[start];while (start < end) {// 如果数组是1,2,3,4,5加start < end是为了防止越界while (start < end && array[end] >= pivot) {end--;}// 如果数组是5,4,3,2,1加start < end是为了防止越界while (start < end && array[start] <= pivot) {start++;}swap(array, start, end);}// start == endswap(array, i, start);return start;}

过程演示：

6.1.1 Hoare 法优化

三数取中法：找到三个数，分别是start、end、mid下标对应的值，找到三个数的中位数作为划分基准

	// hoare 法优化// 三数取中法找到划分基准public static void quickSort(int[] array) {quick(array, 0, array.length - 1);}private static void quick(int[] array, int left, int right) {if (left >= right) {return;}// 优化二// 当节点数小于某一个阈值，没有必要进行递归，直接使用插入排序效率更高，因为所有排序都是越排越有序的！if (right - left + 1 < 7) {insertSort1(array, left, right);return;}// 优化一int index = midThreeNum(array, left, right);swap(array, left, index);// 划分int par = partition(array, left, right);quick(array, left, par - 1);quick(array, par + 1, right);}// 找到三个数，分别是start、end、mid下标对应的值，找到三个数的中位数作为划分基准private static int midThreeNum(int[] array, int start, int end) {int mid = (start + end) / 2;// 3 < 5  start == 3  end == 5   x == midif (array[start] < array[end]) {if (array[mid] < array[start]) {// x < 3 < 5return start;} else if (array[mid] > array[end]) {// 3 < 5 < xreturn end;} else {// 3 < x < 5return mid;}} else {// 5 > 3  start == 5  end == 3  x == midif (array[mid] > array[start]) {// x > 5 > 3return start;} else if (array[mid] < array[end]) {// 5 > 3 > xreturn end;} else {// 5 > x > 3return mid;}}}// 直接插入排序public static void insertSort1(int[] array, int start, int end) {for (int i = start + 1; i <= end; i++) {int tmp = array[i];int j = i - 1;for (; j >= start; j--) {if (array[j] > tmp) {array[j + 1] = array[j];} else {break;}}array[j + 1] = tmp;}}private static int partition(int[] array, int start, int end) {int i = start;int pivot = array[start];while (start < end) {while (start < end && array[end] >= pivot) {end--;}while (start < end && array[start] <= pivot) {start++;}swap(array, start, end);}// start == endswap(array, i, start);return start;}

6.2 挖坑法（重点）

	// 挖坑法public static void quickSort(int[] array) {quick(array, 0, array.length - 1);}private static void quick(int[] array, int left, int right) {if (left >= right) {return;}// 划分int par = partition(array, left, right);quick(array, left, par - 1);quick(array, par + 1, right);}private static int partition(int[] array, int start, int end) {int pivot = array[start];while (start < end) {while (start < end && array[end] >= pivot) {end--;}array[start] = array[end];while (start < end && array[start] <= pivot) {start++;}array[end] = array[start];}array[start] = pivot;return start;}

过程演示：

6.3 快速排序的非递归写法

	// 快速排序的非递归写法public static void quicksort2(int[] array) {int left = 0;int right = array.length - 1;// 找到一个基准值int par = partition(array, left, right);Stack<Integer> stack = new Stack<>();// 判断一下par左边是否只有一个元素了，如果只有一个元素则没必要继续排序了，否则将入栈if (par > left + 1) {stack.push(left);stack.push(par - 1);}if (par < right - 1) {stack.push(par + 1);stack.push(right);}while (!stack.isEmpty()) {right = stack.pop();left = stack.pop();par = partition(array, left, right);if (par > left + 1) {stack.push(left);stack.push(par - 1);}if (par < right - 1) {stack.push(par + 1);stack.push(right);}} }

过程演示：

7. 归并排序

时间复杂度： O(n*logn)
空间复杂度： O(n)
稳定性： 稳定

	// 7. 归并排序public static void mergeSort(int[] array) {mergeSortFunc(array, 0, array.length - 1);}private static void mergeSortFunc(int[] array, int left, int right) {if (left == right) {return;}int mid = (left + right) / 2;// 分解mergeSortFunc(array, left, mid);mergeSortFunc(array, mid + 1, right);// 合并merge(array, left, right, mid);}private static void merge(int[] array, int left, int right, int mid) {int start1 = left;int end1 = mid;int start2 = mid + 1;int end2 = right;int[] tmpArr = new int[right - left + 1];int k = 0;// 此时2个数组都只收有一个数据while (start1 <= end1 && start2 <= end2) {if (array[start1] <= array[start2]) {tmpArr[k++] = array[start1++];} else {tmpArr[k++] = array[start2++];}}// 一个数组被遍历完while (start1 <= end1) {tmpArr[k++] = array[start1++];}while (start2 <= end2) {tmpArr[k++] = array[start2++];}// 保证tmpArr当中的元素是有序的for (int i = 0; i < tmpArr.length; i++) {array[i + left] = tmpArr[i];}}

过程演示：

海量数据的排序问题

外部排序：排序过程需要在磁盘等外部存储进行的排序

在内存只有 1G，需要排序的数据有 100G 的情况下

因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序

1. 先把文件切分成 200 份，每个 512 M
2. 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
3. 进行 2路归并，同时对 200 份有序文件做归并过程，最终结果就有序了

8. 总结

排序方法	平均时间复杂度	空间复杂度	稳定性
直接插入排序	O(n2)	O(1)	稳定
希尔排序	O(n 1.3 ) ~ O(n 1.5 )	O(1)	不稳定
选择排序	O(n2)	O(1)	不稳定
堆排序	O(nlogn)	O(1)	不稳定
冒泡排序	O(n2)	O(1)	稳定
快速排序	最坏O(n2)，最好O(nlogn)	单分支的树O(n)，最好情况O(logn)	不稳定
归并排序	O(nlogn)	O(n)	稳定