八大排序算法

转x33g5p2x  于2021-12-06 转载在 其他  
字(14.9k)|赞(0)|评价(0)|浏览(416)

性能对照表

排序算法平均情况最好情况最坏情况辅助空间稳定性
冒泡排序O(n^2)O(n)O(n^2)O(1)稳定
选择排序O(n^2)O(n^2)O(n^2)O(1)稳定
插入排序O(n^2)O(n)O(n^2)O(1)稳定
希尔排序取决于增量序列O(n)O(n^2)O(1)不稳定
归并排序O(nlogn)O(nlogn)O(nlogn)O(n)稳定
快速排序O(nlogn)O(nlogn)O(n^2)O(logn)~O(n)不稳定
堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定
桶排序O(n+k)O(n+k)O(n+k)O(n+m)稳定

冒泡排序

动画排序过程

执行流程

基本原理:
在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较，让较小的数往下沉，较大的往上冒。即：每当两相邻的数比较后发现他们的排序与排序要求相反时，就将他们互换。
优缺点:
优点：稳定
缺点：慢，每次只能移动两个相邻的数据；

未优化前的代码

  1. package 排序算法;
  3. public class 冒泡排序 {
  4.     public static void main(String[] args) {
  5.         int[] arr = {12,2,0,-1,45,0,12,45,78,45};
  6.         System.out.println("排序前：");
  7.         for(int i: arr){
  8.             System.out.print(i+" ");
  9.         }
  10.         sort(arr);
  11.         System.out.println();
  12.         System.out.println("排序后：");
  13.         for(int i: arr){
  14.             System.out.print(i+" ");
  15.         }
  16.     }
  18.     /** * 自定义冒泡排序方法 * @param arr */
  19.     public static void sort(int[] arr) {
  20.         for (int end=arr.length-1; end>0; end--) {
  21.             for (int begin=1; begin<=end; begin++) {
  22.                 if (arr[begin] < arr[begin-1]) {
  23.                     int temp = arr[begin-1];
  24.                     arr[begin-1] = arr[begin];
  25.                     arr[begin] = temp;
  26.                 }
  27.             }
  28.         }
  30.     }
  31. }

解释：

  1. 首先看内层for循环，begin表示每一轮比较的初始下标（我习惯于用后一个跟前一个比较，因此我初始值设为1而不是0，我判断的代码是if (arr[begin] < arr[begin-1])，刚开始比较的话就是 if (arr[1] < arr[0]) ）
  2. 当不满足begin<=end的条件就结束循环，这里end表示的是每一轮比较的最后下标（因此这里我用的是小于等于而不是小于），因为这个最后下标会随着每一轮比较的结束，越来越小，因此这个end就对应最外层for循环的循环变量
  3. 最外层for循环，我的end初始值是arr.length-1，表示第一轮循环的最后下标是arr.length-1，end–，直到end为1的时候（终结条件end>0）结束所有比较！！！！

演示效果：

冒泡排序优化 - 01

思考：未优化前的代码，每轮比较，如果在比较前的代码已经有序，我们仍然需要循环且比较，这种循环并比较是没有意义的，因为数组已经有序了。

思路：我们可以加一个Boolean类型的标志flag来监控每一轮比较是否发生交换，初始值为true，如果发生交换就将flag设为false，最后判断如果flag为true（没有发生任何交换，说明已经有序）就break退出整个外层循环。结束！！！！

  1. /** * 优化冒泡 - 1 * @param arr */
  2.     public static void sort1(int[] arr) {
  3.         for (int end=arr.length-1; end>0; end--) {
  4.             Boolean flag = true;    // 加一个Boolean类型的标志来监控，每一轮比较是否发生交换
  5.             for (int begin=1; begin<=end; begin++) {
  6.                 if (arr[begin] < arr[begin-1]) {
  7.                     int temp = arr[begin-1];
  8.                     arr[begin-1] = arr[begin];
  9.                     arr[begin] = temp;
  10.                     flag = false;   // 如果发生交换就将flag设为false
  11.                 }
  12.             }
  13.             if (flag) break;    // 如果flag为true，说明这一轮并未发生任何交换，也就意味着数组已经有序
  14.         }
  16.     }

冒泡排序优化 - 02

前言：上述那个优化，触发的概率很小，只有当每轮比较所有的数据已经完全有序之后才会触发生效。
我再提供一个触发概率比较大的优化。。。
思考：每轮比较，如果序列尾部已经局部有序，按照以前的代码，end值还是end–，需要逐步-1，其实这是没必要的，因为尾部已经局部有序了，应该让end直接变成尾部无序最后一个下标（也就是尾部局部有序序列的第一个下标的前一个下标）

思路：我们可以记录最后一次交换的位置，减少比较的次数

  1. /** * 优化冒泡 - 2 * @param arr */
  2. public static void sort2(int[] arr) {
  3.     for (int end=arr.length-1; end>0; end--) {
  4.         int sortedIndex = 1;    // sortedIndex用来记录最后交换的下标，它的初始值是在数组完全有序的时候用的，用来结束最终循环
  5.         for (int begin=1; begin<=end; begin++) {
  6.             if (arr[begin] < arr[begin-1]) {
  7.                 int temp = arr[begin-1];
  8.                 arr[begin-1] = arr[begin];
  9.                 arr[begin] = temp;
  10.                 sortedIndex = begin;    // 将交换后的下标赋值给sortedIndex
  11.             }
  12.         }
  13.         end = sortedIndex;  // 将sortedIndex（最终交换的下标）赋值给end
  14.     }
  16. }

选择排序

动画排序过程

执行流程

基本原理:
第一趟：从第1个记录开始，将后面n-1个记录进行比较，找到（选择）其中最小的记录和第一个记录进行交换；
第二趟：从第2个记录开始，将后面n-2个记录进行比较，找到（选择）其中最小的记录和第2个记录进行交换；
…
第i趟：从第i个记录开始，将后面n-i个记录进行比较，找到（选择）其中最小的记录和第i个记录进行交换；

以此类推，经过n-1趟比较，将n-1个记录排到位，剩下一个最大记录直接排在最后；

代码实现

  1. public class 选择排序 {
  2.     public static void main(String[] args) {
  3.         int[] arr = {12,2,0,-1,45,0,12,45,78,45};
  4.         System.out.println("排序前：");
  5.         for(int i: arr){
  6.             System.out.print(i+" ");
  7.         }
  8.         sort(arr);
  9.         System.out.println();
  10.         System.out.println("排序后：");
  11.         for(int i: arr){
  12.             System.out.print(i+" ");
  13.         }
  14.     }
  16.     /** * 自定义简单选择排序方法 * @param arr */
  17.     public static void sort(int[] arr) {
  18.         int l = arr.length;
  19.         // begin表示最前面的、最终要交换的下标。每比较一轮,说明已经找到一个最小的，然后再从下一个开始再来一轮新的比较，即begin+1
  20.         for (int begin=0; begin<l; begin++){
  21.             int minIndex = begin;   // minIndex用来记录这一轮比较中，数值最小的，它的下标
  22.             for (int next=begin+1; next<l; next++) {   // next表示要跟最小值（arr[minIndex]）比较的值的下标
  23.                 if (arr[next] < arr[minIndex]) {
  24.                     minIndex = next;    // 如果下一个值比最小值还小，就用这个值的下标重新赋值给minIndex
  25.                 }
  26.             }
  27.             // 找到最小值的下标后，就用这个最小值与最前面的值进行交换
  28.             int temp = arr[begin];
  29.             arr[begin] = arr[minIndex];
  30.             arr[minIndex] = temp;
  31.         }
  32.     }
  33. }

解释：

  1. begin表示最前面的、最终要交换的下标。每比较一轮,说明已经找到一个最小的，然后再从下一个开始再来一轮新的比较，即begin+1
  2. minIndex用来记录这一轮比较中，数值最小的，它的下标
  3. next表示要跟最小值（arr[minIndex]）比较的值的下标
  4. 如果下一个值比最小值还小，就用这个值的下标重新赋值给minIndex
  5. 这一轮比较结束后，并找到最小值的下标后，就用这个最小值与最前面的值进行交换

演示效果：

插入排序

动画排序过程

概述

插入排序非常类似于打扑克牌并为其排序。拿到手里的牌就是已排序好的，还未起的牌就是待排序的牌。

执行流程

  1. 在执行过程中，插入排序会将序列分为2部分； 头部是已经排序好的，尾部是待排序的；
  2. 从头开始扫描每一个元素；每当扫描到一个元素，就将它插入到头部合适的位置，使得头部数据依然保持有序；

代码实现

  1. package 排序算法;
  3. public class 插入排序 {
  4.     public static void main(String[] args) {
  5.         int[] arr = {0,9,8,6,5,7,3,1,2,4,0,10,11,12,13,15};
  6.         System.out.println("排序前：");
  7.         for(int i: arr){
  8.             System.out.print(i+" ");
  9.         }
  10.         sort1(arr);
  11.         System.out.println();
  12.         System.out.println("排序后：");
  13.         for(int i: arr){
  14.             System.out.print(i+" ");
  15.         }
  16.     }
  18.     /** * 自定义插入排序方法 * @param arr */
  19.     public static void sort(int[] arr) {
  20.         // begin表示当前要插入的元素（类比打扑克，相当于刚起的的牌），因为这张牌要跟前一个比较，因此begin从1开始
  21.         for (int begin=1; begin<arr.length; begin++) {
  22.             int cur = begin; // cur表示当前牌的下标，这里为了防止begin被污染，因此加了一个临时变量
  23.             while (cur-1>=0 && arr[cur]<arr[cur-1]) { //cur-1不能小于0 且 当前牌比前一张牌小 
  24.                 // 开始交换
  25.                 int temp = arr[cur];
  26.                 arr[cur] = arr[cur-1];
  27.                 arr[cur-1] = temp;
  28.                 // 交互后，cur--，再比较再前面一张牌
  29.                 cur--;
  30.             }
  31.         }
  32.     }
  33. }

演示效果：

插入排序优化 - 01

我们会发现前面那个代码需要大量的交换，需要三行代码。我们可以避免这种交换，转变成如果前面的值比后面的值大，就让前面的值直接向后移动即可，前提是我们需要提前备份要插入的值。

  1. /** * 插入排序优化 - 01 * @param arr */
  2.     public static void sort1(int[] arr) {
  3.         for (int begin=1; begin<arr.length; begin++) {
  4.             int cur = begin;
  5.             int value = arr[cur]; // 定义一个临时值备份当前值
  6.             while (cur-1>=0 && value<arr[cur-1]) {
  7.                 arr[cur] = arr[cur-1]; // 直接让前面的值覆盖后面的值，相当于直接移动，不存在交换
  8.                 cur--;
  9.             }
  10.             arr[cur] = value; // 最后把备份的值插入正确的位置
  11.         }
  12.     }

插入排序优化 - 02

如上代码我们会发现，当我们在找某个值要插入的合适位置时，我们需要当前值跟前面的值一个一个的进行比较，如果数据比较多，这种比较效率是比较低的。因为数组前部分是有序队列，而我们这里是想要找到某个合适的位置，这里我们可以考虑用二分查找法去查找这个位置，便可以大大提高我们的查找效率。
想要了解二分查找去看一下这片文章 【二分查找法】

怎么找到这个合适的值呢？
其实就是要找到有序队列中，第一个大于插入数据的值的位置，这个位置就是我们要插入的位置
查找代码：

  1. /** * 找到数组中第一个大于某个值的下标（插入排序优化时可以用到） */
  2. public static int firstBig(int[] arr, int v) {
  3.     if (arr==null || arr.length<0) return -1; // 如果数组为空则直接返回-1，表示搜索失败
  4.     int begin = 0;  // begin初始值设为0
  5.     int end = arr.length; // 左闭右开[begin,end)
  6.     while (begin < end) {
  7.         int min = (begin+end) >> 1;
  8.         if (v<arr[min]) {   // 因为我们要找的是第一个大于v的值，这里不能是v<=arr[min]，否则min之前的一段是找不到目标下标的
  9.             end = min;
  10.         }else if (v>=min) { // 因为我们要找的是第一个大于v的值，因此这个 '='必须与'>'关联到一块儿
  11.             begin = min+1;
  12.         }
  13.     }
  14.     return begin; // 等begin=end的时候，就是我们要找的下标
  15. }

插入排序优化代码：

  1. /** * 插入排序优化 - 02 （sort2 + firstBig） * @param arr */
  2.     public static void sort2(int[] arr) {
  3.         for (int begin=1; begin<arr.length; begin++) {
  4.             int mv = begin-1;
  5.             int value = arr[begin]; // 定义一个临时值备份当前值
  6.             int i = firstBig(arr, begin); // 从前面有序队列中找到，第一个大于value的值，该值的下标就是要插入的位置
  7.             while (mv>=i) {
  8.                 arr[mv+1] = arr[mv];
  9.                 mv--;
  10.             }
  11.             arr[i] = value;
  12.         }
  13.     }
  15.     /** * 找到数组中大于某个值的第一个值的下标 */
  16.     public static int firstBig(int[] arr, int index) {
  17.         int v = arr[index];
  18.         if (arr==null || arr.length<0) return -1; // 如果数组为空则直接返回-1，表示搜索失败
  19.         int begin = 0;  // begin初始值设为0
  20.         int end = index; // 左闭右开[begin,end)
  21.         while (begin < end) {
  22.             int min = (begin+end) >> 1;
  23.             if (v<arr[min]) {   // 因为我们要找的是第一个大于v的值，这里不能是v<=arr[min]，否则min之前的一段是找不到目标下标的
  24.                 end = min;
  25.             }else if (v>=min) { // 因为我们要找的是第一个大于v的值，因此这个 '='必须与'>'关联到一块儿
  26.                 begin = min+1;
  27.             }
  28.         }
  29.         return begin; // 等begin=end的时候，就是我们要找的下标
  30.     }

希尔排序

动画排序过程

执行流程

希尔排序是插入排序的改进版本，弥补了插入排序在某些情况下的缺点。
例如，当长度为100的数组，前面有序区域的数组长度为80，此时我们用第81个数去跟前面有序区域的所有元素比较大小，但恰巧第81个数又是这100个数里最小的，它本应该在索引为1的位置，如图所示

本例中第81个数据的值为1，那么前面有序区域里的80个元素都要往后移动一个位置，这种情况就非常影响排序性能。

因此，我们就要想办法尽可能早点让小的值靠前，让大的值靠后，这样就能避免上述情况了，这就是希尔排序要解决的问题。
希尔排序也叫做缩小增量排序，它通过先设置一个增量n（增量的求法是自己定义的，你的希尔排序的时间复杂度跟你自定义的增量规则有关，这里我们定义一个简单的增量规则n=n/2），大小为数组长度的一半，将间隔为n的元素视作一个组，然后对每个组内部的元素进行从小到大进行插入排序；然后再将增量n缩小一半，再次进行分组插入排序，直到增量n为1，因为增量为1的时候，所有的元素都为同一个组了

为了方便大家理解，我用一个例子来展示一个完整的希尔排序过程，首先数据的初始状态如图所示，这里为了更好地体现希尔排序的优点，我特地把值较大的元素放到了靠左的位置，把值较小的元素放到了靠右的位置

该数组长度为8，因此我们设置初始的增量为 8 / 2 = 4，那么该数组的分组情况如下图所示：

图中颜色相同的元素为一组，每组内的各个元素间隔都为4，现在对每个组内进行从小到大排序，排序结果如下图所示：

此时我们将增量缩小一半，即 4 / 2 = 2，同样的，现在将所有元素重新组合，把所有间隔为2的元素视作一组，分组结果如下图所示：

图中颜色相同的元素为一组，每组内的各个元素间隔都为2，现在对每个组内进行从小到大排序，排序结果如下图所示：

我们继续将增量缩小一半，即 2 / 2 = 1，同样的，现在将所有元素重新组合，把所有间隔为1的元素视作一组，此时所有的元素都为同一组了，就相当于对所有的数据进行普通的插入排序，我们可以看到，对比最开始的数据，总得来说，小的值都比较靠左了，大的值也都比较靠右了，这样排序起来效率就很高了。结果如下图所示：

接下来用一个动图，演示一下完整的希尔排序全过程

代码实现

根据上述流程的讲解相信大家都应该有思路了，接下来演示我写希尔排序的步骤
1、首先写出插入排序算法

  1. public static void sort1(int[] arr) {
  2.         for (int begin=1; begin<arr.length; begin++) {
  3.             int cur = begin;
  4.             int value = arr[cur]; // 定义一个临时值备份当前值
  5.             while (cur-1>=0 && value<arr[cur-1]) {
  6.                 arr[cur] = arr[cur-1]; // 直接让前面的值覆盖后面的值，相当于直接移动，不存在交换
  7.                 cur--;
  8.             }
  9.             arr[cur] = value; // 最后把备份的值插入正确的位置
  10.         }
  11.     }

这段代码是上面插入排序-优化01的代码，我们在这个段代码的基础上简单修改即可
2、首先加个for循环，step作为增量， 来表示根据增量不同，进行不同轮的排序，每一轮我们都使用插入排序对序列排序

  1. for (int step=arr.length/2; step>0; step/=2){
  2.             
  3. }

3、将第一步中插入排序的代码直接放到循环中

  1. for (int step=arr.length/2; step>0; step/=2){
  2.     for (int begin=1; begin<arr.length; begin++) {
  3.         int cur = begin;
  4.         int value = arr[cur]; // 定义一个临时值备份当前值
  5.         while (cur-1>=0 && value<arr[cur-1]) {
  6.             arr[cur] = arr[cur-1]; // 直接让前面的值覆盖后面的值，相当于直接移动，不存在交换
  7.             cur--;
  8.         }
  9.         arr[cur] = value; // 最后把备份的值插入正确的位置
  10.     }
  11. }

这段代码目前是不能运行的，接下来我们稍作修改

  1. 首先第二层for循环的初始值begin就不能为1了，应该为step
  2. 然后while循环里的条件要变一下，应该写成while (cur-step>=0 && value<arr[cur-step])
  3. while代码段里，改成arr[cur] = arr[cur-step]; cur-=step;

4、修改完成后的代码

  1. //希尔排序
  2. public static void sort(int[] arr) {
  3.     for (int step=arr.length/2; step>0; step/=2){
  4.         for (int begin=step; begin<arr.length; begin++) {
  5.             int cur = begin;
  6.             int value = arr[cur]; // 定义一个临时值备份当前值
  7.             while (cur-step>=0 && value<arr[cur-step]) {
  8.                 arr[cur] = arr[cur-step]; // 直接让前面的值覆盖后面的值，相当于直接移动，不存在交换
  9.                 cur-=step;
  10.             }
  11.             arr[cur] = value; // 最后把备份的值插入正确的位置
  12.         }
  13.     }
  14. }

总结

上述情况中，希尔排序最坏情况下的时间复杂度为O(n²)。其实希尔排序的时间复杂度跟增量也有关系，我们上面是通过数组长度一直取一半获取的增量，其实还有一些别的增量规则，可以使得希尔排序的效率更高，例如Hibbard增量序列、Sedgewick增量序列，本文就不对这两种增量做过多的讲解了，大家可以去网上搜索一下。

归并排序

动画排序过程

执行流程

归并排序采用了 分治（Divide and Conquer）和 递归（Recursion）的思想（快速排序也是一样，这里你可以和快速排序比较一下他们的区别）

流程：

  1. 划分：将待排序列二分，一直向下划分，直到只有一个元素为止（只有一个元素相当于已排序）
  2. 合并：将已排序的两个子序列合并为一个新的有序序列（主要逻辑）

实现代码

归并排序实现代码：

  1. /** * 归并排序 * @param arr：待排序的数组 * @param tempArr：辅助的临时数组 * @param left：最左边下标 * @param right：最右边下标 */
  2. public static void sort(int[] arr, int[] tempArr, int left, int right) {
  3.     // 如果只有一个元素，那么就不需要再继续划分了 （只有一个元素本身就是有序的，只需要被合并即可）
  4.     // 如果 left<right则表示至少有两个元素，则需要继续划分 递归调用sort
  5.     if (left < right) {
  6.         int mid = (left+right)/2;   // 找到中间点
  7.         // 递归划分左半区域
  8.         sort(arr, tempArr, left, mid);
  9.         // 递归划分右半区域
  10.         sort(arr, tempArr, mid+1, right);
  11.         // 将划分后的排序合并（排序的主要逻辑在这个方法里）
  12.         merge(arr, tempArr, left, mid, right);
  13.     }
  14. }
  16. /** * 将划分后的排序合并（排序的主要逻辑在这个方法里） * @param arr * @param tempArr * @param left * @param mid * @param right */
  17. public static void merge(int[] arr, int[] tempArr, int left, int mid, int right) {
  18.     // 标记左半区第一个未合并的元素下标
  19.     int l_pos = left;
  20.     // 标记右半区第一个未合并的元素下标
  21.     int r_pos = mid+1;
  22.     // 临时数组元素的下标
  23.     int pos = left;
  25.     // 合并（左半区、有半区都存在未合并的元素）
  26.     while (l_pos<=mid && r_pos<=right) {
  27.         if (arr[l_pos] < arr[r_pos])    // 左半区第一个未合并的元素 小于 右半区第一个未合并的元素
  28.             tempArr[pos++] = arr[l_pos++]; // 将更小的那个数放到临时数组中 且pos、l_pos下标后移
  29.         else
  30.             tempArr[pos++] = arr[r_pos++];   // 同上
  31.     }
  32.     // 合并左半区剩余的元素（如果右半区已经合并完）
  33.     while (l_pos <= mid)
  34.         tempArr[pos++] = arr[l_pos++];
  36.     // 合并右半区剩余的元素（如果左半区已经合并完）
  37.     while (r_pos <= right)
  38.         tempArr[pos++] = arr[r_pos++];
  40.     // 把临时数组中合并后的元素复制回原来的数组
  41.     while (left <= right) {
  42.         arr[left] = tempArr[left];
  43.         left++;
  44.     }
  45. }

测试代码：

  1. public static void main(String[] args) {
  2.     Scanner sc = new Scanner(System.in);
  3.     System.out.println("请输入你想生成随机数的个数");
  4.     int num = sc.nextInt();
  5.     int[] arr = new int[num];
  6.     int[] tempArr = new int[num];
  7.     for (int i=0; i<num; i++) arr[i] = (int)(Math.random()*100);
  8.     System.out.println("排序前的数据：");
  9.     for (int i=0; i<arr.length; i++)
  10.         System.out.print(arr[i]+" ");
  12.     long begin = System.currentTimeMillis();
  13.     sort(arr, tempArr, 0, arr.length-1);
  14.     long end = System.currentTimeMillis();
  16.     System.out.println();
  17.     System.out.println("总耗时为："+(end-begin));
  18.     System.out.println("排序后的数据：");
  19.     for (int i=0; i<arr.length; i++)
  20.         System.out.print(arr[i]+" ");
  22.     System.out.println();
  24. }

总结

空间复杂度：O(n)

  • 因为创建一个相同大小的临时数组嘛

时间复杂度：O(NlogN)

  1. 每一层归并的时间复杂度为O(N)
  2. 归并层数最大为O(logN+1)

快速排序

动画排序过程

执行流程

执行流程：

  1. 从序列中选择一个轴点元素（pivot）。假设每次选择第一个位置的元素为轴点元素；
  2. 利用pivot将序列分割成2个子序列 。 将小于pivot的元素放到pivot前面（左侧）；将大于pivot的元素放到pivot后面（右侧）；等于pivot的元素放到哪都可以；
  3. 对子序列进行1、2操作。直到不能再分割（子序列中只剩下一个元素）；

案列图：

快速排序的大致思想我们了解了，关键是我们怎么构建轴点呢？

轴点构造：

  1. 一般选取数组的第一个元素作为轴点元素（pivot）
  2. 将轴点元素（pivot）备份一份，后面会用
  3. begin表示坐标，初始值是轴点坐标；end表示坐标，初始值是最后元素下标；
  4. 从右向左开始检索。如果end坐标的元素大于轴点元素，则不用动，end–；检索下一个end，如果end坐标元素小于轴点元素，则将end元素赋值给begin坐标（因为之前pivot已经备份了，所以不会造成数据丢失），然后让begin++，开始从左向右检索
  5. 从左向右开始检索。如果begin坐标的元素小于轴点元素，则不用动，begin++；检索下一个begin，如果begin坐标元素大于轴点元素，则将begin元素赋值给end坐标，然后让end–，开始从右向左检索
  6. 重复 4、5 操作直到begin==end
  7. 最后找到的轴点下标就是begin

代码实现

  1. package 排序算法;
  3. public class 快速排序 {
  4.     public static void main(String[] args) {
  5.         int[] arr = {0,9,8,6,5,7,3,1,2,4,0,10,11,12,13,15};
  6.         System.out.println("排序前：");
  7.         for(int i: arr){
  8.             System.out.print(i+" ");
  9.         }
  10.         sort(arr, 0, arr.length-1);
  11.         System.out.println();
  12.         System.out.println("排序后：");
  13.         for(int i: arr){
  14.             System.out.print(i+" ");
  15.         }
  16.     }
  18.     /** * 快速排序算法 （sort + pivotIndex） * @param arr * @param begin * @param end */
  19.     // 核心逻辑
  20.     public static void sort(int[] arr, int begin, int end) {
  21.         if (end - begin <= 0) return; // 终止条件是，序列只剩下一个元素
  22.         // 确定轴点的位置
  23.         int mid = pivotIndex(arr, begin, end);
  24.         // 对子序列进行排序
  25.         sort(arr, begin, mid-1);
  26.         sort(arr, mid+1, end);
  28.     }
  29.     // 找到中心轴
  30.     public static int pivotIndex(int[] arr, int begin, int end) {
  31.         // 备份begin下标的元素，作为中心轴元素
  32.         int pivot = arr[begin];
  33.         while (begin<end) { // 循环条件是begin<end,如果begin=end说明找到了中心轴，退出循环
  34.             /** * 从右向左开始检索 */
  35.             while (begin<end && arr[end]>pivot) { // 如果begin<end且end下标的值大于pivot，则不发生交换，用下个end与pivot比较
  36.                 end--;
  37.             }
  38.             if (begin<end) { // 进入这个代码块说明 arr[end]<=pivot
  39.                 arr[begin] = arr[end];  // 让end元素赋值给begin元素（初始时，已经备份了arr[begin],因此不会造成数据丢失）
  40.                 begin++; // 勿忘让begin++，开始从左向右检索
  41.             }
  42.             /** * 从左向右开始检索，这里逻辑跟上面类似，我就不做注释了 */
  43.             while (begin<end && arr[begin]<pivot) {
  44.                 begin++;
  45.             }
  46.             if (begin<end) {
  47.                 arr[end] = arr[begin];
  48.                 end--;
  49.             }
  50.             /** * 如果begin=end说明找到了中心轴，退出循环 */
  51.             if (begin==end) {
  52.                 arr[begin] = pivot;
  53.             }
  54.         }
  55.         return begin; // 返回中心轴坐标
  56.     }
  57. }

堆排序

有待总结。。。

桶排序

动画排序过程

概述

桶排序（Bucket sort）或所谓的箱排序，工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后依次把各个桶中的记录列出来既得到有序序列。

思想：
桶排序采用的是分治的思想

桶排序假设待排序的一组数均匀独立的分布在一个范围中，并将这一范围划分成几个子范围（桶）。
然后基于某种映射函数f ，将待排序列的关键字 k 映射到第i个桶中 (即桶数组B 的下标i) ，那么该关键字k 就作为 B[i]中的元素

接着将各个桶中的数据有序的合并起来 : 对每个桶B[i] 中的所有元素进行比较排序 (插入、快速、归并排序都可以)。然后依次枚举输出 B[0]….B[M] 中的全部内容即是一个有序序列。

注意：

  • 尽可能保证最后的数据均匀分布在桶中，与你的映射函数f(重要的一步)有关
  • 理论上区分区间越小，即桶分的越多，整体时间复杂度越接近于线性，但对应的空间复杂度就大了(空间换时间)。当区间只有一个大小，就变成相当于计数排序了
  • 时间复杂度也和每个桶用的排序算法有关

执行流程

  1. 创建桶
  2. 将数据根据映射函数放到对应的桶中，并保持有序
  3. 然后再按顺序将数据取出

代码实现

桶排序最重要的是它里面分治思想。这里代码我就举一个简单的例子，输入0-99之间的随机整数，0-9放入0号桶，10-19放到1号桶，20-29放入2号桶…以此类推

  1. import java.util.ArrayList;
  2. import java.util.List;
  4. public class 桶排序 {
  5.     public static void main(String[] args) {
  6.         int[] arr = new int[100];
  7.         for (int i=0; i<100; i++) arr[i] = (int)(Math.random()*100);
  8.         System.out.println("排序前的数据：");
  9.         for (int i=0; i<arr.length; i++)
  10.             System.out.print(arr[i]+" ");
  12.         sort(arr, 10);
  14.         System.out.println("排序后的数据：");
  15.         for (int i=0; i<arr.length; i++)
  16.             System.out.print(arr[i]+" ");
  17.     }
  19.     /** * 桶排序 * @param arr：待排序数组 * @param bucketNum：桶的个数 */
  20.     public static void sort(int[] arr, int bucketNum) {
  21.         // 创建一个桶的集合
  22.         ArrayList<ArrayList<Integer>> buckets = new ArrayList<>();
  23.         for (int i=0; i<bucketNum; i++) {
  24.             // 分别创建 bucketNum 个桶 然后放入到桶集合中
  25.             buckets.add(new ArrayList<>());
  26.         }
  28.         // 将数组的每个数据都放入到对应的桶中，并保证桶内数据有序
  29.         for (int i=0; i<arr.length; i++) {
  30.             // 算出该数据应该放入桶的下标
  31.             int bucketIndex = getBucketIndex(arr[i], bucketNum);
  32.             // 将数据插入到对应的桶中并保持桶内数据有序
  33.             insertSort(buckets.get(bucketIndex), arr[i]);
  34.         }
  36.         // 将各个桶的数据合并到原始数组中
  37.         int arrIndex = 0;
  38.         for (int i=0; i<buckets.size(); i++) {
  39.             for (int j=0; j<buckets.get(i).size(); j++) {
  40.                 arr[arrIndex] = buckets.get(i).get(j);
  41.                 arrIndex++;
  42.             }
  43.         }
  44.     }
  46.     /** * 计算得到输入元素应该放到哪个桶内 * @param data：放入的数据 * @param bucketNum：桶的个数 * @return */
  47.     public static int getBucketIndex(int data, int bucketNum) {
  48.         return (int)data/bucketNum;
  49.     }
  51.     /** * 将数据插入到桶中，并保持有序（这里我使用的排序算法是插入排序） * @param bucket: 要插入的桶 * @param data：要插入的数据 */
  52.     public static void insertSort(List<Integer> bucket, int data) {
  53.         bucket.add(data);
  54.         int cur = bucket.size()-1;  // 当前数据的下标
  55.         while (cur-1>=0 && bucket.get(cur-1)>data) { // 如果当前数据小于前面那个数据
  56.             bucket.set(cur, bucket.get(cur-1));    // 前面那个数据后移
  57.             cur--;      // 当前下标前移
  58.         }
  59.         bucket.set(cur, data);  // 将数据插入到合适的位置
  60.     }
  61. }

这里因为每个桶的大小是不确定的，因此每个桶容器我使用的是一个ArrayList集合来表示。
里面每个桶的排序算法我使用的是插入排序算法，不熟悉插入排序的话可以看看上面总结的插入排序。

总结

桶排序中很重要的一步就是桶的设定了，我们必须根据输入元素的情况，使得输入元素能够正确的放入对应的桶内，且保证输入数据能够尽量均匀的放入不同的桶内。

其次，我们可以发现，区间划分的越细，即桶的数量越多，理论上分到每个桶中的元素就越少，桶内数据的排序就越简单，其时间复杂度就越接近于线性。

极端情况下，就是区间小到只有1，即桶内只存放一种元素，桶内的元素不再需要排序，因为它们都是相同的元素，这时桶排序差不多就和计数排序一样了。

借鉴的优秀博文

https://blog.csdn.net/l_ppp/article/details/108855298
https://blog.csdn.net/meibenxiang/article/details/92796909

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/qq_45464560/article/details/120916211

内容来源于网络，如有侵权，请联系作者删除！

Java算法排序算法

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com