【DS】八大排序算法实现详解
温馨提示：这篇文章已超过385天没有更新，请注意相关的内容是否还可用！
✨博客主页: 心荣~
✨系列专栏:【Java实现数据结构】
✨一句短话: 难在坚持,贵在坚持,成在坚持!
文章目录
- 一. 排序的概念
- 二. 插入排序
- 1. 直接插入排序
- 2. 希尔排序
- 二. 选择排序
- 1. 直接选择排序
- 2. 堆排序
- 三. 交换排序
- 1. 冒泡排序
- 2. 快速排序
- 2.1 Hoare法
- 2.2 挖坑法
- 2.3 前后指针法
- 2.4 性能分析及快速排序优化
- 2.4 非递归实现快速排序
- 四. 归并排序
- 1. 递归实现的归并排序
- 2. 非递归实现归并排序
- 3. 性能分析
- 4. 海量数据的排序问题
- 五. 常见排序算法性能分析总结
- 六. 计数排序(非基于比较)
一. 排序的概念
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持 不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳 定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
二. 插入排序
1. 直接插入排序
- 基本思想：
直接插入排序是一种简单的插入排序法，其基本思想是： 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到 一个新的有序序列; 实际中我们玩扑克牌时，就用了插入排序的思想。
- 实现过程:
首先只看序列当中的第一个元素, 那么这一个元素是有序的, 从第二个元素开始，将当前待排序元素的下标设为i， 并使用变量tmp储存该元素，设下标j，默认第一个值为i-1(从已经有序的部分最后一个位置开始比较);
如果下标j对应元素比tmp大，则将该元素则向右移动一个位置（即将这个元素放到j+1位置），并将j–，直到j //把第一个元素当为有序的,从第二个元素开始,往前面的序列中插入 for (int i = 1; i tmp) { array[j+1] = array[j]; }else { //此时j位置元素比tmp小,j+1就是要插入的位置; break; } } array[j+1] = tmp; } }
其他的代码实现:
下面的这两个代码与上面流程稍有不同, 但思想是一样的, 流程如下:
想让 arr[0…0] 上有序，这个范围只有一个数，当然是有序的。
想让 arr[0…1] 上有序，所以从 arr[1] 开始往前看，如果 arr[1]
依此类推……
想让 arr[0…i] 上有序，所以从 arr[i] 开始往前看，如果 arr[i]
最后一步，
想让 arr[0…N-1] 上有序，arr[N-1] 这个数不停向左移动，一直移动到左边的数字不再比自己大，停止移动。
与上面的流程不同之处在于, 上面是将要插入的值保存下来, 然后找到要插入的位置, 最后进行赋值插入; 比较如果 arr[i]
// 交换 public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } // 插入排序 public static void insertSort1(int arr[]) { if (arr == null || arr.length == 0) { return; } for (int i = 0; i = 0 && arr[newValIndex-1] > arr[newValIndex]) { swap(arr, newValIndex-1, newValIndex); newValIndex--; } } } // insertSort1更简洁的写法 public static void insertSort2(int arr[]) { if (arr == null || arr.length == 0) { return; } // i标识的是新插入的元素 for (int i = 1; i = 0 && arr[prev] > arr[prev+1]; prev--) { swap(arr, prev, prev+1); } } }- 性能分析:
元素集合越接近有序，直接插入排序算法的时间效率越高
时间复杂度 空间复杂度 稳定性 最好：数组有序，O(N)最坏：O(N ^ 2) O(1) 稳定的排序 2. 希尔排序
- 基本思想及实现过程:
希尔排序法又称缩小增量法, 希尔排序是直接插入排序的改进,
把待排序文件中所有记录分成gap个组，距离为gap的记录分在同一组内，并对每一组内的记录进行插入排序。
希尔排序gap先大后小, gap大于1的状态，称为预排序 ; 这个过程是让数组不断接近有序, 直到最终gap等于1 , 此时数组已经接近有序的了, 所有数据在统一在一组内排序就会很快。
gap递减的规则不唯一 , 可以循环除3加1，也可以除2; 下面的代码中用的是除2实现。
假如有10个元素需要排序，首先将这10个元素为5组，对每组分别进行直接插入排序，再分为2组，并对每组分别进行直接插入排序，最后分为1组，进行直接插入排序;
- 实现代码:
/** *希尔排序(插入排序的优化) * 时间:记住 O(N^1.3) 就好 * 空间:O(1) * 稳定性:不稳定 */ public static void shellSort(int[] array) { int gap = array.length; //将数组中的元素分为gap组,每组元素之间间隔gap个元素, //将每组中的元素进行插入排序 while(gap > 1) { gap /= 2; shell(array, gap); } } private static void shell(int[] array, int gap) { //和插入排序的过程一样,只不过,每个元素的下一个元素与当前元素间隔为gap for (int i = gap; i = 0; j -= gap) { if (array[j] > tmp) { array[j+gap] = array[j]; }else { break; } } array[j+gap] = tmp; } }- 性能分析:
时间复杂度 空间复杂度 稳定性 O(N ^ 1.3) O(1) 不稳定的排序 希尔排序的效率与怎么分组息息相关，严蔚敏和殷人昆的《数据结构》书中中对希尔排序的效率问题是这样表示的：
《数据结构(C语言版)》— 严蔚敏
《数据结构-用面向对象方法与C++描述》— 殷人昆
二. 选择排序
1. 直接选择排序
- 基本思想：
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
- 实现过程:
在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素
若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素
具体流程如下:
arr[0…n-1] 范围上，找到最小值所在的位置，然后把最小值交换到 0 号位置；
arr[1…n-1] 范围上，找到最小值所在的位置，然后把最小值交换到 1 号位置；
arr[2…n-1] 范围上，找到最小值所在的位置，然后把最小值交换到 2 号位置；
依此类推……
arr[n-1…n-1] 范围上，找到最小值位置，然后把最小值交换到 n-1 号位置；
- 实现代码:
/** *直接选择排序 *时间:O(N^2) *空间:O(1) *稳定性:不稳定 */ public static void selectSort(int[] array) { for (int i = 0; i array[j]) { minIndex = j;//更新 } } //如果i和minIndex相等就没必要去交换 if(i != minIndex) { swap(array, i, minIndex); } } } private static void swap(int[] array, int i, int j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; }其他代码实现:
// 选择排序 public static void selectSort (int[] arr) { if (arr == null || arr.length == 0) { return; } for (int i = 0; i arr[j] ? j : maxValIndex; } swap(arr, maxValIndex, i); } }- 性能分析:
直接选择排序思考非常好理解，但是效率不是很好 , 实际中很少使用
时间复杂度 空间复杂度 稳定性 O(N ^ 2) O(1) 不稳定的排序 2. 堆排序
- 基本思想及实现过程:
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。
需要注意的是排升序要建大堆，排降序建小堆。
升序排序步骤：
- 将数组转换成大根堆，使用索引end标记最后一个元素。
- 将堆顶元素与end处元素交换，end–。
- 对堆顶结点进行向下调整，调整的结点下标不大于end。
- 重复2,3步骤，直到end
//排升序,先将数组改成一个大根堆
createBigHeat(array);
int end = array.length-1;
//end=0时,只剩最后一个元素,位置也就自动确定了
while(end 0) {
//将堆顶元素(也就是在确定最大元素)与数组最后一个位置元素交换
swap(array, 0, end);
//向下调整,注意此时不能把end位置处的元素算在调整范围内了
shiftDown(array, 0, end);
end--;
}
}
private static void createBigHeat(int[] array) {
//从最后一个根节点开始向上调整
for (int parent = (array.length-1-1)/2; parent >= 0 ; parent--) {
shiftDown(array, parent, array.length);
}
}
private static void shiftDown(int[] array, int parent, int len) {
int child = parent*2+1;
//判断有左孩子
while(child array[parent]) {
swap(array, child, parent);
parent = child;
child = parent*2+1;
}else{
break;
}
}
}
private static void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
- 性能分析:
堆排序使用堆来选数，效率就高了很多
时间复杂度 空间复杂度 稳定性 O( N*logN ) O(1) 不稳定的排序 三. 交换排序
基本思想：
所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特 点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
1. 冒泡排序
- 基本思想和实现过程：
从第二个元素开始，将该元素与前一个元素比较，如果前一个元素比较大，则交换。直到最后一个元素为最大元素，这一过程称为一趟冒泡 ; 每进行一趟冒泡排序，下次排序比较的范围就缩小一个位置，因为每进行一趟冒泡排序就会确定一个元素的最终位置。
在 arr[0…n-1] 范围上：
arr[0] 和 arr[1]，谁大谁来到 1 号位置；
arr[1] 和 arr[2]，谁大谁来到 2 号位置；
依此类推……
arr[n-2] 和 arr[n-1]，谁大谁来到第 n-1 号位置上；
在 arr[0…n-2] 范围上，重复上面的过程，但最后一步是 arr[n-3] 和 arr[n-2] ，谁大谁来到第 n-2 号位置上；
在 arr[0…n-3] 范围上，重复上面的过程，但最后一步是 arr[n-4] 和 arr[n-3]，谁大谁来到第 n-3 号位置上；
依此类推……
最后在 arr[0…1] 范围上，重复上面的过程，但最后一步是 arr[0] 和 arr[1]，谁大谁来到第 1 号位置上；
如果数组在冒泡前就有序了呢 , 这时候不需要再进行冒泡比较了，所以基于上面的思想可以进行优化，基本思路就是当遇到一趟排序时并没有发生元素交换，这时候就说明数组已经有序了，下一趟就不用排了，所以代码中可以使用一个标记，如果在冒泡过程中发生了交换 , 就改变标记的状态 , 这样就可以在下次冒泡前根据这个标记来确定之后是否需要继续冒泡排序了。
- 实现代码:
/** *冒泡排序 *时间:不考虑优化的话O(N^2); *空间:O(1) *稳定性:稳定 */ public static void bubbleSort(int[] array) { boolean flag = true; for (int i = 0; i array[j+1]) { swap(array, j, j+1); flag = false; } } if(flag) { break; } } } private static void swap(int[] array, int i, int j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; }其他代码实现:
// 冒泡排序, 没有优化过的 public static void bubbleSort(int[] arr) { if (arr == null || arr.length == 0) { return; } for (int i = arr.length-1; i >= 0; i--) { for (int j = 1; j if (arr[j-1] arr[j]) { swap(arr, j-1, j); } } } }- 性能分析:
时间复杂度 空间复杂度 稳定性 不考虑优化,最坏 : O( N^2 )最好：O(N), 数组有序。 O(1) 稳定的排序 2. 快速排序
基本思想:
从数组中找一个基准值 ，然后以该基准值，将比基准值小的元素排在基准值左边，比基准值大的元素排在基准值右边，此时基准值在数组中的排序位置已经确定了，再对基准值左边和右边的序列以相同的方式重新找基准值并将比基准值小的排左边，大的排右边，直到只剩下一个元素，此时所有的元素排序位置都确定了，排序完成。
快速排序递归实现的主框架与二叉树前序遍历规则非常像，在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。
将区间按照基准值划分为左右两半部分的常见方式有：
- Hoare版
- 挖坑法
- 前后指针
实现快速排序有三步，第一找基准值， 第二确定基准值位置，第三对基准值左右序列进行相同的找基准操作，最终会使所有的元素有序。
2.1 Hoare法
实现过程:
- 以范围内第一个元素为基准值。
- 先让right从右边界开始向前遍历，遇到比基准值小的元素为止 ; 再让left从左边界开始向后遍历，遇到比基准值大的元素时停止。
- 然后交换这两个元素，继续2过程。
- 直到left与right相遇为止，将相遇位置（比基准值小的元素）与基准值原位置交换，此时基准值的位置确定，基准左边元素比基准值小，右边元素比基准值大。
- 分别对基准值左右序列进行上述相同的操作：取左边界元素为基准值，通过Hoare法确定基准值排序位置; 直到左右序列只有一个元素或没有元素为止。
注意：一定要先让right找比基准值小的元素，再让left找比基准值大的元素，这样保证最后相遇时的元素一定是比基准值小的元素。
实现代码:
/** * Hoare快速排序 * 时间:N*logN * 空间:O(logN) * 稳定性:不稳定 * * 当数据是有序的时候,这个快排的时间复杂度是O(n^2) * 空间复杂度：O(n) */ public static void quickSortHoare(int[] array) { quickHoare(array, 0, array.length-1); } private static void quickHoare(int[] array, int start, int end) { if(start >= end) {//这里必须写上>号,预防没有左树或者右树的情况 return; //比如: 1 2 3 4 5 或者 5 4 3 2 1 } int pivot = partitionHoare(array, start, end); quickHoare(array, start, pivot-1); quickHoare(array, pivot+1, end); } private static int partitionHoare(int[] array, int left, int right) { int i = left; //把范围内的第一个元素当作基准 int pivot = array[left]; while(left = pivot) {//这里的等号要理解,如果没有的话可能会出现死循环的情况,比如开头和结尾的元素相同 right--;//left left++;//left int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } quickDigging(array, 0, array.length-1); } private static void quickDigging(int[] array, int start, int end) { if(start = end) { return; } int pivot = partitionDigging(array, start, end); quickDigging(array, start, pivot-1); quickDigging(array, pivot+1, end); } private static int partitionDigging(int[] array, int left, int right) { int pivot = array[left];//将第一个元素作为基准保存起来,此时第一个位置就是一个坑位 while(left tmp) { array[j+1] = array[j]; }else { break; } } array[j+1] = tmp; } } private static int findMidValOfIndex(int[] array, int start, int end) { int midindex = (end+start) / 2; if(array[start] array[end]) { return end; }else{ return midindex; } }else { if(array[midindex] > array[start]) { return start; }else if(array[midindex] = pivot) { right--; } //在右边找到比基准小的元素,然后赋值给左边的坑位,此时右边就空出一个坑位 array[left] = array[right]; while(left start+1) { stack.push(start); stack.push(pivot-1); } //判断基准右边是不是还有两个以上的元素 if(pivot > end-1) { stack.push(pivot+1); stack.push(end); } } } private static int partitionDigging(int[] array, int left, int right) { int pivot = array[left];//将第一个元素作为基准保存起来,此时第一个位置就是一个坑位 while(left = pivot) { right--; } //在右边找到比基准小的元素,然后赋值给左边的坑位,此时右边就空出一个坑位 array[left] = array[right]; while(left
- 性能分析:
- 实现代码:
- 基本思想和实现过程：
- 性能分析:
- 基本思想及实现过程:
- 性能分析:
- 实现代码:
- 实现过程:
- 基本思想：
- 性能分析:
- 实现代码:
- 基本思想及实现过程:
- 性能分析:
- 实现过程:
- 基本思想：
