引言
排序的稳定性
对于一组待排序的数据，数据中有两个或两个以上的相同的元素，在经过排序后，这两个或两个以上的相同元素与之前未排序的顺序相同，则说明此排序操作是稳定的。
举例说明：
在下图中，待排序数据 ① 经过排序成为 ② ，我们发现绿色数字5和红色数字5与排序前的顺序并未发生改变，那么排序 ② 就是稳定的。
反之，排序 ③ 就是不稳定的。
三个稳定的排序
本篇博客所提到的稳定的排序：直接插入、冒泡、归并。
一、直接插入排序
思想：
从数组的第二个元素开始，将当前元素存为临时变量，然后与当前下标之前的位置进行比较元素，大的放后面，小的放前面。
/** * 直接插入排序 * 时间复杂度（最坏情况下）：O(n^2) * 时间复杂度最好情况下：O(n)，即一组数据已经有序了 * 所以，对于插入排序来说，待排序的一组数据趋于有序，那么排序的速度越快 * 空间复杂度：O(1) * 是否稳定：稳定 */ public class Test { public static void main(String[] args) { int[] arr = {8,5,9,4,7}; insertSort(arr); System.out.println(Arrays.toString(arr)); } public static void insertSort(int[] arr){ for (int i = 1; i < arr.length; i++) { int temp = arr[i]; int j = i-1; for (; j >= 0 ; j--) { if(arr[j] > temp){ //前面的元素比后面的元素大，就交换 arr[j+1] = arr[j]; }else { break; } } arr[j+1] = temp; } } //写成这样更简洁 public static void insertSort2(int[] arr){ for (int i = 1; i < arr.length; i++) { int temp = arr[i]; int j = i-1; for (; j >= 0 && arr[j] > temp; j--) { arr[j+1] = arr[j];//前面的元素比后面的元素大，就交换 } arr[j+1] = temp; } }
输出结果：
二 、希尔排序
希尔排序本质上就是直接插入排序，只不过对其进行了分组。当我们给定了一组数据，直接插入排序直接对这组数据进行了排序，而希尔可以将其先分成某个组别，之后对这些组别分别进行排序操作。
让我们来看下面的一个例子，可以发现每当我们进行一次排序后，小的数字都比较靠前，而大的数字都比较靠后，这就会致使下一次的排序速度的更快。
关于时间复杂度这里我还没弄懂，不过大话数据结构这本书上说明：不同的增量序列所对应的时间复杂度不同，增量序列实际上对应的就是我们进行排序时分的组别元素的个数，这和算法很有关系，我暂且不作考虑了。。。
但是有一点很重要，就是：不管我们分了多少组，每一组有多少元素，我们都必须在最后的时候，分为一组。也就是说：我们最后要对整组数据进行排序。这很好理解，因为不论我们怎么分组排序，最后很大可能都不会把一组数据排序好我们想要的结果，但是我们最后一次排序的时候一定会快很多，因为最后一组数据非常趋近于我们想要的排序序列！
/** * 希尔排序 * 时间复杂度[ 和增量是有关系的 ]：O(n^1.3) - O(n^1.5) * 空间复杂度：O(1) * 稳定性：不稳定 * 希尔排序在排序的过程中，发生了跳跃性的交换元素， * 在最坏的情况下，就很有可能发生了排序后的相同元素与排序前的顺序不匹配 */ public class Test { public static void main(String[] args) { int[] arr = {4,12,5,8,9,14,11,6,15,2,13,1,3,10,7}; shellSort(arr); System.out.println(Arrays.toString(arr)); } //希尔排序，传入 gap 进行分组 public static void shellSort(int[] arr){ int gap = arr.length; while(gap > 1){ shell(arr, gap); gap = gap / 2; //[7组,3组,1组] } shell(arr, 1); } //开始排序 public static void shell(int[] arr, int gap){ for (int i = gap; i < arr.length; i++) { int temp = arr[i]; int j = i - gap; for (; j >= 0; j = j-gap) { if(arr[j] > temp){ arr[j+gap] = arr[j]; }else { break; } } arr[j+gap] = temp; } } }
输出结果：
三、选择排序
思想：
每一趟排序后，第一个元素一定是最小的。
/** * 时间复杂度：O(n^2) * 时间复杂度在最坏情况下或者是最好情况下都是 O(n^2) * 空间复杂度：O(1) * 稳定性：不稳定 */ public class Test { public static void main(String[] args) { int[] arr = {8,5,9,4,7}; selectSort2(arr); System.out.println(Arrays.toString(arr)); } public static void selectSort(int[] arr){ for (int i = 0; i < arr.length; i++) { for(int j = i+1; j < arr.length; j++){ if(arr[i] > arr[j]){ int temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; } } } } //选择排序优化 public static void selectSort2(int[] arr){ for (int i = 0; i < arr.length; i++) { int minIndex = i; for(int j = i+1; j < arr.length; j++){ if(arr[j] < arr[minIndex]){ minIndex = j; } } if(minIndex != i){ //如果两个数相同，就不进行交换 int temp = arr[minIndex]; arr[minIndex] = arr[i]; arr[i] = temp; } } } }
输出结果：
四、堆排序
堆排序在我之前的博客上有介绍，这里就不再赘述，主要阐明一下思想。
思想：
① 如果我们将待排序的一组数据进行升序，那么我们就先创建一个大顶堆，目的是始终将堆顶的元素置为最大值。
② 堆排序的实际操作就是将堆顶元素与堆尾元素进行交换。
③ 每次堆排序过后，就立即调整一次，调整为大顶堆，以便下一次排序。
/** * 堆排序 * createMaxHeap 时间复杂度：O(n) * shiftDown 时间复杂度：O(log n) * heapSort 时间复杂度：O(n * log n) [ heapSort 函数里面嵌套了 shiftDown 函数 ] * =>总时间复杂度：O(n * log n) [ O(n) + O(n * log n) ] * * 空间复杂度：O(1) * 稳定性：跳跃式排序，不稳定（试想极端条件下，待排序的每个数据都为1） */ public class Test { public static void main(String[] args) { //int[] arr = {8,5,9,4,7}; int[] arr = {8,5,9,2,6,11,26,56,35,49,99,70,21,2,4,7,2}; createMaxHeap(arr); heapSort(arr); System.out.println(Arrays.toString(arr)); } //堆排序 public static void heapSort(int[] arr){ int end = arr.length - 1; while (end > 0){ //1. 先交换 int temp = arr[0]; arr[0] = arr[end]; arr[end] = temp; //2. 后调整 //每次调整的其实都是树的根节点及根节点向下 shiftDown(arr,0, end); end--; } } //创建一个大顶堆，目的是始终将堆顶的元素置为最大值 public static void createMaxHeap(int[] arr){ int child = arr.length - 1; //处理每棵树的顺序 for (int parent = (child-1)/2; parent >= 0 ; parent--) { shiftDown(arr,parent,arr.length); } } //向下调整 public static void shiftDown(int[] arr, int parent, int len){ int child = parent*2 + 1; while(child < len){ if(child+1 < len && arr[child] < arr[child+1]){ child++; } if(arr[child] > arr[parent]){ int temp = arr[parent]; arr[parent] = arr[child]; arr[child] = temp; } parent = child; child = parent*2 + 1; } } }
输出结果：
五、冒泡排序
思想：
将紧挨着的数据进行比较，一趟代表遍历完数组一次，而每一趟冒泡排序之后，最大的元素一定放在最后一位。
优化分析：
在内层 for 循环中的 if 语句中，判断布尔类型 isSorted ，如果进入了 if 语句，说明进行了交换，isSorted 置为 false；反之，如果某一趟的 if 语句一次也没进去，isSorted 就为初始的 true，说明从这一趟往后，数据已经有序。
/** * 冒泡排序 * 时间复杂度：O(n^2) * 空间复杂度：O(1) * 稳定性：稳定 */ public class Test { public static void main(String[] args) { //int[] arr = {8,5,9,4,7}; int[] arr = {8,5,9,2,6,11,26,56,35,49,99,70,21,2,4,7,2}; bubbleSort2(arr); System.out.println(Arrays.toString(arr)); } public static void bubbleSort(int[] arr){ for (int i = 0; i < arr.length-1; i++) { //假设待排序有5个数据，只比较了4趟 for (int j = 0; j < arr.length-1-i; j++) { //每一趟比较了多少次 if(arr[j] > arr[j+1]){ int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } } //冒泡排序优化 public static void bubbleSort2(int[] arr){ //举个例子 arr = {4,3,5,6,7}, 第一趟冒泡排序结束以后，实际上已经有序 for (int i = 0; i < arr.length-1; i++) { boolean isSorted = true; for (int j = 0; j < arr.length-1-i; j++) { if(arr[j] > arr[j+1]){ //若某一趟一次也没有交换，那么isSorted 还是为 true，即数组已经有序 int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; isSorted = false; } } if(isSorted){ break; } } } }
输出结果：
六、快速排序
思想：
通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序的目的。
步骤总结：
（1）选择枢轴（基准、pivot）
（2）分割数据
① 从后面序列找比枢轴小的放到枢轴前面
② 从前面序列找枢比轴大的放到枢轴后面
通过枢轴分割数据，使得枢轴左边的值比枢轴小，枢轴右边的值比枢轴大
（3）重复递归被枢轴分割的数据，可以先处理左边的数据，再处理右边的数据
1. 快速排序递归写法
/** * 快速排序 * 递归写法 * 最坏时间复杂度：O(n^2), 最好时间复杂度：O(n*logn)[刚好平均分割整个数据] * 最坏空间复杂度：O(n), 最好空间复杂的：O(logn) * 稳定性：不稳定 */ public class Test { public static void main(String[] args) { //int[] arr = {5,2,3,9,4,7}; int[] arr = {8,5,9,2,6,11,26,56,35,49,99,70,21,2,4,7,2}; int start = 0; int end = arr.length-1; quickSort(arr,start,end); System.out.println(Arrays.toString(arr)); } public static void quickSort (int[] arr, int start, int end){ if(start >= end){ //边界条件 return; } int i = start; int j = end; int temp = arr[i]; while (i < j){ //1. 从后面序列找比枢轴小的放到枢轴前面 //whille 循环中的"="防止死循环重复赋值, i<j 防止此次循环数组越界 while (i < j && arr[j] >= temp){ j--; } arr[i] = arr[j]; //2. 从前面序列找比枢轴大的放到枢轴后面 while (i < j && arr[i] <= temp){ i++; } arr[j] = arr[i]; } arr[i] = temp;//填上缺口 int pivot = i; //拿到每次新的枢轴 //3. 分别递归求左右两边的序列 quickSort(arr,start,pivot-1); quickSort(arr,pivot+1,end); } }
输出结果：
图解分析：
2. 优化快速排序
（1）随机选取基准
随机选取基准的时候，会带来不确定的因素，很有可能优化不成功。
（2）使用三数取中法来确定分割的基准，一般取左端、右端及中间的三个数，而这在这三个数中，中间大小的数被确定为基准。比方说：[ 3 1 5 ]，我们取 3，因为最小数为 1，最大数为 5。这样可以避免两种极端的情况：
① 当最大或最小的数分布在数据的两边
② 当数据整体有序的情况
（3） 将和基准相同的元素，从分散的位置聚集到一起，这样会使递归的次数减少，从而使程序运行速度更快。
（4）当分割一定的长度后，使用直接插入排序。
3. 三数取中法优化
/** * 快速排序优化 * 三数取中法 */ public class Test { public static void main(String[] args) { //int[] arr = {6,1,2,7,9,3,4,5,10,8}; int[] arr = {8,5,9,2,6,11,26,56,35,49,99,70,21,2,4,7,2}; //int[] arr = {5,2,3,9,4,7}; quickSort(arr,0,arr.length-1); System.out.println(Arrays.toString(arr)); } public static void quickSort(int[] arr, int start, int end){ if(start >= end){ return; } //三数取中法，防止取到顺序/逆序的情况 int midValIndex = findMidValIndex(arr, start, end); //交换基准 int temp = arr[start]; arr[start] = arr[midValIndex]; arr[midValIndex] = temp; int base = partition(arr,start,end); //接收基准 quickSort(arr,start,base-1); quickSort(arr,base+1,end); } //找中间值 public static int findMidValIndex(int[] arr, int start, int end){ int mid = (start+end) / 2; if(arr[start] < arr[end]){ if(arr[mid] < arr[start]){ return start; }else if(arr[mid] > arr[end]){ return end; }else { return mid; } }else { if(arr[mid] < arr[end]){ return end; }else if(arr[mid] > arr[start]){ return start; }else { return mid; } } } //寻找基准 public static int partition(int[] arr, int start, int end){ int temp = arr[start]; while(start < end){ //在数据的后半部分寻找比基准小的 while(start < end && arr[end] >= temp){ // “=” 防止死循环，防止重复赋值 end--; } arr[start] = arr[end]; //在数据的前半部分寻找比基准大的 while(start < end && arr[start] <= temp){ start++; } arr[end] = arr[start]; } arr[start] = temp; return start; } }
4. 快速排序的非递归写法
/** * 快速排序 * 非递归写法 */ public class Test { public static void main(String[] args) { //int[] arr = {5,2,3,9,4,7}; int[] arr = {8,5,9,2,6,11,26,56,35,49,99,70,21,2,4,7,2}; int start = 0; int end = arr.length-1; quickSort(arr,start,end); System.out.println(Arrays.toString(arr)); } public static void quickSort(int[] arr, int start, int end){ Stack<Integer> stack = new Stack<>(); int pivot = partition(arr,start,end); if(start+1 < pivot){ stack.push(start); stack.push(pivot-1); } if(pivot < end-1){ stack.push(pivot+1); stack.push(end); } while (!stack.isEmpty()){ end = stack.pop(); start = stack.pop(); pivot = partition(arr,start,end); if(start+1 < pivot){ stack.push(start); stack.push(pivot-1); } if(pivot < end-1){ stack.push(pivot+1); stack.push(end); } } } public static int partition (int[] arr, int i, int j){ int temp = arr[i]; while (i < j){ //1. 从后面序列找比枢轴小的放到枢轴前面 //"="防止死循环重复赋值, i<j 防止此次循环数组越界 while (i < j && arr[j] >= temp){ j--; } arr[i] = arr[j]; //2. 从前面序列找枢比轴大的放到枢轴后面 while (i < j && arr[i] <= temp){ i++; } arr[j] = arr[i]; } arr[i] = temp; return i;//拿到每次的枢轴 } }
七、归并排序
1. 合并两个有序数组
理解归并排序之前，一定要知道两个已经有序的数组是怎么合并的，并理解它们的思想。
思想：
① 定义 s1 为 arr1 数组的初始下标，e1 为 arr1 数组的末尾下标。
② 定义 s2 为 arr2 数组的初始下标，e2 为 arr2 数组的末尾下标。
③ 将 s1 和 s2 进行比较，较小者放入新的数组中，紧着，让 s1 / s2 进行遍历，之后循环重复实现以上的操作，直到有一个数组遍历完，就可以将另一个未遍历完的数组中的剩下元素放入新数组的末尾。
代码较为简单，不再赘述。
/** * 合并两个有序的数组 */ public class Test { public static void main(String[] args) { int[] arr1 = {1,6,7,9}; int[] arr2 = {2,3,5,8}; int[] arr = merge(arr1,arr2); System.out.println(Arrays.toString(arr)); } public static int[] merge(int[] arr1, int[] arr2){ int[] arr = new int[arr1.length+arr2.length]; int s1 = 0; int e1 = arr1.length-1; int s2 = 0; int e2 = arr2.length-1; int i = 0; while (s1 <= e1 && s2 <= e2){ if(arr1[s1] < arr2[s2]){ arr[i++] = arr1[s1++]; }else { arr[i++] = arr2[s2++]; } } while (s1 <= e1){ arr[i++] = arr1[s1++]; } while (s2 <= e2){ arr[i++] = arr2[s2++]; } return arr; } }
输出结果：
现在我们来看一下归并排序的思想：
归并排序就是先在一个待排序数组中选择一个中间下标对应元素（并不是大小为中间元素），通过这个元素分割成两个逻辑上的数组，在这两个数组中，再寻找中间对应元素，之后不断分割，直至某个数组无法再分。这样一来，就可以对某一个数组进行有序排序，之后再进行整合，而这里每次整合过后，都要回归原始数组中。
在下图分析中，拆就是递的过程，合就是归的过程，所以这体现了递归的思想。
2. 归并排序递归写法
/** * 归并排序 * 时间复杂度：O(n*logn) * 空间复杂度：O(n) * 稳定性：稳定 */ public class Test { public static void main(String[] args) { //int[] arr = {9,6,7,1,3,8,5,2}; int[] arr = {8,5,9,2,6,11,26,56,35,49,99,70,21,2,4,7,2}; int low = 0; int high = arr.length-1; mergeSort(arr,low,high); System.out.println(Arrays.toString(arr)); } public static void mergeSort(int[] arr, int low, int high){ if(low == high){ return; } int mid = (low+high) / 2; mergeSort(arr,low,mid); //先拆左边 mergeSort(arr,mid+1,high); //再拆右边 merge(arr,low,mid,high); //拆完过后，开始合并 } //合并 public static void merge(int[] arr, int low, int mid, int high){ int[] temp = new int[high-low+1]; int i = 0; int s1 = low; int e1 = mid; int s2 = mid+1; int e2 = high; while (s1 <= e1 && s2 <= e2){ if(arr[s1] < arr[s2]){ temp[i++] = arr[s1++]; }else { temp[i++] = arr[s2++]; } } while (s1 <= e1){ temp[i++] = arr[s1++]; } while (s2 <= e2){ temp[i++] = arr[s2++]; } //将 temp 中的数组拷贝至原数组中 for (int j = 0; j < i; j++) { arr[j+low] = temp[j]; //”j+low“ 以防对原数组进行覆盖 } } }
输出结果：
3. 归并排序非递归写法
/** * 归并排序 * 非递归写法 */ public class Test { public static void main(String[] args) { int[] arr = {9,6,7,1,3,8,5,2}; mergeSort(arr); System.out.println(Arrays.toString(arr)); } public static void mergeSort(int[] arr){ int size = 1; // 第一次归并两个元素，第二次归并四个元素... while (size < arr.length){ for (int i = 0; i < arr.length; i += size*2) { int low = i; int mid = low+size-1; if(mid >= arr.length){ mid = arr.length-1; } int high = mid+size; if(high >= arr.length){ high = arr.length-1; } merge(arr,low,mid,high); } size *= 2; } } public static void merge(int[] arr, int low, int mid, int high){ int[] ret = new int[high-low+1]; int s1 = low; int e1 = mid; int s2 = mid+1; int e2 = high; int i = 0; while (s1 <= e1 && s2 <= e2){ if(arr[s1] < arr[s2]){ ret[i++] = arr[s1++]; }else { ret[i++] = arr[s2++]; } } while (s1 <= e1){ ret[i++] = arr[s1++]; } while (s2 <= e2){ ret[i++] = arr[s2++]; } for (int j = 0; j < i; j++) { arr[j+low] = ret[j]; } } }
输出结果：
八、了解三个不需要比较数据就能进行排序的方法
1. 基数排序
说明：可以将下面装数据的容器想象成队列的结构，而不是栈。
下图只是为了方便演示，所以才会画成这个容器哦。
2. 计数排序
3. 桶排序
