-
八大基于比较的排序算法及三大基于非比较的排序算法总结
本文主要介绍五类排序算法, 如下图所示. 这几类排序算法对于我们学生毕业前和毕业后都非常重要, 毕竟 期末常考, 考研常考, 面试常问. 下面主要以举例的形式来实现各个算法, 明白其原理, 并比较其空间复杂度和时间复杂度, 从而达到见到排序问题都有着比较熟悉的思路.
1 插入排序
1.1 直接插入排序
插入排序的基本思想: 主要分为两个区间, 无序区间和有序区间, 每次选择无序区间的第一个元素, 在有序区间内选择合适的位置进行插入操作.
插入过程如下图所示:
代码:public class InsertSort { 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; } } public static void main(String[] args) { int[] arr = {3,2,5,7,1,6,8,9,4}; System.out.println(Arrays.toString(arr)); insertSort(arr); System.out.println(Arrays.toString(arr)); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
运行结果:
性能分析:
1.2 折半插入排序
折半插入的详细过程如下:
代码:public class InsertSort { public static void bsInsertSort(int[] array) { for (int i = 1; i < array.length; i++) { int tmp = array[i]; int left = 0; int right = i; while (left < right) { int aver = (left + right) / 2; if (tmp >= array[aver]) { left = aver + 1; } else { right = aver; } } for (int j = i; j > left; j--) { array[j] = array[j-1]; } array[left] = tmp; } } public static void main(String[] args) { int[] arr = {3,2,5,7,1,6,8,9,4}; System.out.println(Arrays.toString(arr)); bsInsertSort(arr); System.out.println(Arrays.toString(arr)); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
运行结果:
性能分析:
1.3 希尔排序
希尔排序的基本思想: 把待排序列中的数据分成若干个组, 并对每组的数据进行排序, 重复上述工作, 直到等于 1 的时候, 所有记录即将排序完毕.
- 希尔排序是对直接排序的优化;
- 当 gap > 1 的时候都是预排序列, 当 gap == 1 时, 数组即将为有序序列, 对于整体而言可以达到优化的效果.
- 一般 gap 的值为: gap = (gap / 3) + 1, 或者是 gap = (gap / 2) + 1.
详细过程如下:
代码如下:public class InsertSort { public static void shell(int[] arr, int gap) { for (int i = gap; i < arr.length; i++) { int tmp = arr[i]; int j = i-gap; for (; j >= 0; j-=gap) { if (arr[j] > tmp) { arr[j+gap] = arr[j]; } else { break; } } arr[j+gap] = tmp; } } public static void shellSort (int[] array) { int gap = array.length; while (gap > 1) { gap = gap / 3 + 1; shell(array, gap); } } public static void main(String[] args) { int[] arr = {3,2,5,7,1,6,8,9,4}; System.out.println(Arrays.toString(arr)); shellSort(arr); System.out.println(Arrays.toString(arr)); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
运行结果:
性能分析:
2 选择排序
2.1 直接选择排序
直接选择排序比较简单, 每一次排序只能确定一个数值, 因此这里不再进行描述其详细过程.
代码如下:public class SelectSort { public static void selectSort(int[] array) { for (int i = 0; i < array.length; i++) { for (int j = i+1; j < array.length; j++) { if (array[j] < array[i]) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } } } } public static void main(String[] args) { int[] arr = {3,2,5,7,1,6,8,9,4}; System.out.println(Arrays.toString(arr)); selectSort(arr); System.out.println(Arrays.toString(arr)); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
运行结果:
性能分析:
2.2 堆排序
2.1 堆的概念
- 堆逻辑上就是一颗完全二叉树, 物理上是保存在数组中;
- 大根堆: 满足任意结点的值都大于其子树中结点的值;
- 小根堆: 满足任意结点的值都小于其子树中结点的值.
- 堆的基本作用就是快速找到集合中的最值, 关于其逻辑结构和存储结构如下图所示(以小根堆为例):
2.2 操作过程–向下调整
向下调整的前提是左右子树必须已经是一个堆才能调整.我们以小堆为例, 如下所示.
- index 如果已经是叶子结点, 则调整过程结束;
– 判断 index 位置有没有孩子;
– 因为堆是完全二叉树, 因此没有左孩子就一定没有右孩子, 所以要进行判断有没有左孩子;
– 因为堆的存储结构是数组, 所以判断是否有左孩子即判断左孩子下标是否越界, 即 left >= size越界; - 确定 left 或 right, 谁是 index 的最小孩子 min;
– 如果右孩子不存在, 则 min = left;
– 如果右孩子存在, 比较 array[left] 和 array[right] 值的大小, 选择小的为 min; - 比较 array[index] 的值和 array[min] 的值, 如果 array[index] <= array[min], 则满足堆的性质, 调整结束;
- 如果 array[index] >= array[min], 交换 array[index] 和 array[min] 的值;
- 因为 min 位置的堆的性质可能被破坏, 所以把 min 视作 index, 如此重复以上过程.
其中: array 代表存储堆的数组; size 代表数组中被视为堆数据的个数; index 代表要调整位置的下标; left 代表 index 左孩子下标; right 代表 index 右孩子下标; min 代表 index 的最小值孩子的下标.
2.3 操作过程–建堆
关于堆的建立基本思想就是从倒数第一个非叶子节点的子树开始调整, 一直调整到根节点的树, 即为堆.这里我们以大根堆为例.
2.4 堆排序过程
堆排序的基本思想也是选择排序, 只是不再使用遍历的方式查找无序区间的最大值, 而是通过堆来选择无序区间的最大的数; 还需要注意: 升序排序要建大堆; 降序排序要建小堆.
详细过程如下:
代码如下:
public class SelectSort { public static void createHeap(int[] arr) { //从小到大排序 --> 大根堆 for(int i = (arr.length - 1 - 1)/2;i>=0;i--) { siftDown(arr,i, arr.length); } } public static void siftDown(int[] arr,int root,int len) { int parent = root; int child = 2*parent+1; while (child < len) { if(child+1 < len && arr[child] < arr[child+1]) { child++; } //child的下标就是左右孩子的最大值下标 if(arr[child] > arr[parent]) { int tmp = arr[child]; arr[child] = arr[parent]; arr[parent] = tmp; parent = child; child = 2*parent+1; } else { break; } } } public static void heapSort(int[] arr) { createHeap(arr); //O(n) int end = arr.length - 1; while (end > 0) { //O(N*LogN) int tmp = arr[end]; arr[end] = arr[0]; arr[0] = tmp; siftDown(arr,0,end); end--; } } public static void main(String[] args) { int[] arr = {3,2,1,5,8,7,6,4,9}; System.out.println(Arrays.toString(arr)); heapSort(arr); System.out.println(Arrays.toString(arr)); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
运行结果:
性能分析:
3 交换排序
3.1 冒泡排序
冒泡排序的基本思想就是两两进行比较, 也就是相邻的两个元素进行比较, 每次一个外循环都可以确定一个最大值, 并将这个最大值放在无序序列的最后面, 持续这个过程, 直到整个序列有序.
详细执行过程如下:
代码如下:public static void bubbleSort(int[] arr) { for (int i = 0; i < arr.length-1; i++) { boolean flag = false; for (int j = 0; j < arr.length-1-i; j++) { if (arr[j] > arr[j+1]) { int tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp; flag = true; } } if (flag == false) { break; } } } public static void main(String[] args) { int[] arr = {3,2,5,7,1,6,8,9,4}; System.out.println(Arrays.toString(arr)); bubbleSort(arr); System.out.println(Arrays.toString(arr)); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
运行结果:
性能分析: 这里需要注意一下: 如果序列是优化过的, 也就是有序的, 其时间复杂度可能是 O(n).
3.2 快速排序
快速排序的基本思想如下:
- 从待排序列中选择一个数, 作为基准值(pivot);
关于基准值的选择主要有三种方式:
1) 选择边上的数字, 例如我们经常会选择序列的首位数字作为基准值;
2) 随机选择;
3) 三位数中, 也就是arr[start], arr[mid], arr[end] 这三个数中选择中间大的数字, 下面的代码我们就是用的这种方式.- 遍历整个待排序列, 将比基准值小的放在基准值的左边, 将比基准值大的或者相等的放在基准值的右边, 如下图所示;
- 采用分治的思想, 对基准值左右两个区间按照以上顺序处理, 直到小区间的长度等于 1 的时候, 代表已经有序.
关于快速排序这里主要介绍两种方法, 一种是递归遍历的方式, 另一种是非递归遍历的方式.
3.2.1 递归实现
详细过程如下:
代码如下:public class SwapSort { public static int partition(int[] arr, int low, int high) { int tmp = arr[low]; while (low < high) { while (low < high && arr[high] >= tmp) { high--; } arr[low] = arr[high]; while (low < high && arr[low] <= tmp) { low++; } arr[high] = arr[low]; } arr[high] = tmp; return low; } public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } public static void selectPivotMedianOfThree(int[] arr, int start, int end, int mid) { while (true) { if (arr[mid] > arr[start]) { swap(arr, start, mid); continue; } if (arr[start] > arr[end]) { swap(arr, start, end); continue; } if (arr[mid] > arr[end]) { swap(arr, start, end); continue; } break; } } public static void quick(int[] arr, int start, int end) { if (start >= end) { return; } int mid = (start+end)/2; selectPivotMedianOfThree(arr, start, end, mid); int pivot = partition(arr, start, end); quick(arr, start, pivot-1); quick(arr, pivot+1, end); } public static void quickSort(int[] arr) { quick(arr, 0, arr.length-1); } public static void main(String[] args) { int[] arr = {3,2,5,7,1,6,8,9,4}; System.out.println(Arrays.toString(arr)); quickSort(arr); System.out.println(Arrays.toString(arr)); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
运行结果:
性能分析:
3.2.2 非递归实现
非递归的实现需要用到栈, 详细过程如下:
代码如下:public class SwapSort { public static int partition(int[] arr, int low, int high) { int tmp = arr[low]; while (low < high) { while (low < high && arr[high] >= tmp) { high--; } arr[low] = arr[high]; while (low < high && arr[low] <= tmp) { low++; } arr[high] = arr[low]; } arr[high] = tmp; return low; } public static void quickSort2(int[] arr) { Stack<Integer> stack = new Stack<>(); int start = 0; int end = arr.length - 1; int pivot = partition(arr, start, end); // 左边有两个元素及以上 if (pivot > start + 1) { stack.push(0); stack.push(pivot - 1); } if (pivot < end - 1) { stack.push(pivot + 1); stack.push(end); } while (!stack.empty()) { end = stack.pop(); start = stack.pop(); pivot = partition(arr, start, end); // 左边有两个元素及以上 if(pivot > start+1) { stack.push(0); stack.push(pivot-1); } if(pivot < end-1) { stack.push(pivot+1); stack.push(end); } } } public static void main(String[] args) { int[] arr = {3,2,5,7,1,6,8,9,4}; System.out.println(Arrays.toString(arr)); quickSort2(arr); System.out.println(Arrays.toString(arr)); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
运行结果:
4 归并排序
关于归并排序也是有两种实现方式, 递归实现和非递归实现, 其思路如下.
4.1 递归实现
**递归实现归并排序的基本思想: 就是一直对半分, 直到分到剩下一个或者是两个元素的时候为止, 然后对分开到最后的小序列进行排序比较, 比较完后回到上一层的序列中再次进行比较, 直到序列整体有序. **
详细过程如下:
代码如下:public class MergeSort { /** * 递归实现 */ public static void merge(int[] arr, int low, int mid, int high) { int s1 = low; int e1 = mid; int s2 = mid + 1; int e2 = high; int[] tmp = new int[high - low + 1]; int k = 0; // 代表 tmp 数组的下标 while (s1 <= e1 && s2 <= e2) { if (arr[s1] <= arr[s2]) { tmp[k++] = arr[s1++]; } else { tmp[k++] = arr[s2++]; } } // 有两种情况 while (s1 <= e1) { // 说明第二个归并段没有了数据, 把第一个归并段剩下的数据全部拷过来 tmp[k++] = arr[s1++]; } while (s2 <= e2) { // 说明第一个归并段没有了, 把第二个归并段剩下的数据全部拷贝过来 tmp[k++] = arr[s2++]; } // tmp 数组当中, 存储的就是当前归并好的数据 for (int i = 0; i < tmp.length; i++) { arr[i + low] = tmp[i]; } } public static void mergeSortInternal(int[] arr, int low, int high) { if (low >= high) { return; } int mid = (low + high) / 2; mergeSortInternal(arr, low, mid); mergeSortInternal(arr, mid + 1, high); // 合并的过程 merge(arr, low, mid, high); } public static void mergeSort1(int[] arr) { mergeSortInternal(arr, 0, arr.length - 1); } public static void main(String[] args) { int[] arr = {3,2,5,7,1,6,8,9,4}; System.out.println(Arrays.toString(arr)); mergeSort1(arr); System.out.println(Arrays.toString(arr)); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
运行结果:
性能分析:
4.2 非递归实现
对于非递归来实现的基本思想就是先从 i = 1开始, 对 i*2 的序列进行排序, 如下图所示, 首先对 3,2 进行排序, 然后再对 2,3,5,7 进行排序, 然后再对 1,2,3,5,6,7,8,9 八个元素进行排序, 最后再对所有元素进行排序.
详细思路如下:
代码如下:public class MergeSort { public static void merge2(int[] arr, int gap) { int[] tmp = new int[arr.length]; int k = 0; int s1 = 0; int e1 = s1 + gap - 1; int s2 = e1 + 1; int e2 = s2 + gap - 1 < arr.length ? s2 + gap - 1 : arr.length - 1; // 需要保证有两个归并段 while (s2 < arr.length) { while (s1 <= e1 && s2 <= e2) { if (arr[s1] <= arr[s2]) { tmp[k++] = arr[s1++]; } else { tmp[k++] = arr[s2++]; } } while (s1 <= e1) { tmp[k++] = arr[s1++]; } while (s2 <= e2) { tmp[k++] = arr[s2++]; } // 一组完成后, 确定新的区间的开始和结束 s1 = e2 + 1; e1 = s1 + gap - 1; s2 = e1 + 1; e2 = s2 + gap - 1 < arr.length ? s2 + gap - 1 : arr.length - 1; } while (s1 <= arr.length - 1) { tmp[k++] = arr[s1++]; } for (int i = 0; i < tmp.length; i++) { arr[i] = tmp[i]; } } public static void mergeSort2(int[] arr) { for (int i = 1 ; i < arr.length; i*=2) { merge2(arr, i); } } public static void main(String[] args) { int[] arr = {3,2,5,7,1,6,8,9,4}; System.out.println(Arrays.toString(arr)); mergeSort2(arr); System.out.println(Arrays.toString(arr)); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
运行结果:
5 非比较类排序
非比较排序只需要了解即可, 知道是怎么排的, 这里我们不再演示代码.
5.1 计数排序
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中, 计数排序要求输入的数据必须是有确定范围的整数.具体算法如下:
- 找出待排序列中的最大值和最小值, 用于确定新开辟的空间的大小;
- 统计数组中的每个值为 i 的元素出现的次数, 存入到数组对应的 i 位置;
- 对额外空间内的数据进行计算, 得出每一个元素的正确位置;
- 将待排序列中每一个元素移到计算得出的正确位置上.
详细过程如下:
5.2 基数排序
基数排序的基本思想就是"多关键字排序", 其实现方式有两种:
- 最高位优先: 即按最高位排成若干子序列, 再对每个子序列按次高位排序, 如扑克牌, 先按照花色进行排序分为四种花色, 然后再按照每种花色的 13 张牌进行排序, 最终使扑克牌整体有序;
- 最低位优先: 这种方式不必分成子序列, 每次排序全体关键字都参与, 也就是说不通过比较, 而是通过"分配"和"收集"来进行, 还是扑克牌的例子, 可以先按数字将牌分配到 13 个桶中, 然后从第一个桶依次收集, 再将收集好的牌按花色分配到 4 个桶中, 然后还是从第一个桶开始依次收集, 通过两次"分配"和"收集"操作, 最终使牌有序.
详细过程如下:
5.3 桶排序
桶排序可以说是计数排序的升级版本, 利用函数的映射关系, 高效与否的关键就在于这个映射函数的确定, 需要做到以下两点:
- 在额外空间充足的情况下, 尽量增大桶的容量;
- 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中.
也可以这么理解, 当输入的数据可以均匀的分配到 K 个桶中的时候效率比较高, 当输入的数据被分配到同一个桶中的时候, 效率比较低.
详细过程如下:
6 复杂度总结
-
相关阅读:
程序员内功-设计模式篇
JavaScript实战游戏逻辑
luming.02无限进步 #我的创作纪念日
SAP入门到放弃系列之QM物料主数据&检验类型设置
10 个用图表解释JavaScript 闭包的面试题
Swagger3+knife4j的使用
Pycharm无法完整运行django设计的网页
互联网+教育时代，线下教培机构的新机遇
【Go语言】Go语言中的字典
三十一、java版 SpringCloud分布式微服务云架构之Java ArrayList
- 原文地址：https://blog.csdn.net/Onion_521257/article/details/125349659