经典排序算法总结（java实现）

迈不过友情╰ 2023-09-27 14:05 202阅读 0赞

排序的相关概念

排序：

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

稳定性：

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

82358aad3da54f059a737aae02df4ace.png

内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

一、插入类排序

基本思想：

插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入

1.直接插入排序

算法描述

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。

（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

步骤：

  1. 把要比较的元素单独存（tmp）；

  2. 外层循环挨个遍历（i）

  3. 内层循环（j）判断tmp和j的值，并交换位置；

4.j—，倒着检查j重复步骤3,；

动图演示

747526387275184cd7ca47ed271544c1.gif

直接插入排序总结

  1. 元素集合越接近有序，直接插入排序算法的时间效率越高
  2. 时间复杂度：O(N^2)
  3. 空间复杂度：O(1)，它是一种稳定的排序算法
  4. 稳定性：稳定

代码实现

  1. public static void insertSort(int[] array) {
  2.         for (int i = 1; i < array.length; i++) {
  3.             int tmp = array[i];
  4.             int j = i -1;
  5.             for (; j >= 0  ; j--) {
  6.                 if (array[j] > tmp){
  7.                     array[j+1] = array [j];
  8.                 }else {
  9.                     break;
  10.                 }
  12.             }
  13.             array[j+1 ] = tmp;
  14.         }
  15.     }

2.希尔排序

希尔排序法又称缩小增量法

基本思想

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录”基本有序”时，再对全体记录进行依次直接插入排序。

算法描述

步骤：

  1. 把数据分组，每组元素个数为gap，在组内进行排序；

  2. 再次分组，每组元素个数为gap/2，再进行排序；

  3. 以此重复分组，排序，直到组内元素个数为1 ，进行整体排序。

图示

91d169e1243b4e1782dc872dfe90afa6.png

特性总结：

  1. 希尔排序是对直接插入排序的优化。
  2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。
  3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定。

  4. 稳定性：不稳定

  5. 时间复杂度：O(N^1.3) - O(N^1.5)

  6. 空间复杂度：O(1)

代码实现

  1. /*
  2. 希尔排序
  3. gap 是分组
  4.      */
  5.     public static void shellSort(int[] array){
  6.         int gap = array.length;     //
  7.         while (gap > 1){
  8.             shell(array,gap);
  9.             gap /= 2;
  10.                     }
  11. //进行整体排序
  12.         shell(array,1);
  15.     }
  16. //组内插入排序
  17.     public static void shell(int[] array,int gap){
  18.         for (int i = gap; i < array.length; i++) {
  19.             int tmp = array[i];
  20.             int j = i-gap;
  21.             for (; j >= 0; j-= gap) {   j逆序往前找
  22.                 if (array[j] > tmp) {     //这里加不加 = ，可以决定排序稳不稳定
  23.                     array[j + gap] = array[j];
  24.                 } else {
  25.                     break;
  26.                 }
  27.             }
  28.             array[j + gap] = tmp;
  29.         }
  31.     }

#

二、选择类排序

基本思想：
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元
素排完 。

直接选择排序

算法步骤

  1. 把第一个元素的索引暂定为最小索引（minIndex），遍历元素，找到比minIndex的元素还小的值的索引，把minIndex变成当前索引，再继续本次遍历，改变minIndex，一次遍历结束minIndex的值就是最小的。

2.再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

3.重复第二步，直到所有元素均排序完毕。

动图演示

bb66b163e9795d7b3322c7f9aa638a79.gif

特性总结

  1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
  2. 时间复杂度：O(N^2)
  3. 空间复杂度：O(1)
  4. 稳定性：不稳定

代码实现

  1. public static void selectSort(int[] array){
  2.         for (int i = 0; i < array.length; i++) {
  3.             int minIndex = i;
  4.             int j = i+1;
  5.             for (; j < array.length ; j++){
  6.                 //寻找最小值
  7.                 if (array[minIndex] > array[j]){
  8.                     minIndex= j;
  9.                 }
  10.             }
  11.             //交换本次遍历找到的的最小值和array[i]的值
  12.             swap(array,i,minIndex);
  14.         }
  15.     }
  16.     private static void swap(int[] array,int i,int j) {
  17.         int tmp = array[i];
  18.         array[i] = array[j];
  19.         array[j] = tmp;
  20.     }
  23. //写法二，最大最小值一起找
  25.     public static void selectSort2(int[] array) {
  26.         int left = 0;
  27.         int right = array.length-1;
  28.         while (left < right) {
  29.             int minIndex = left;
  30.             int maxIndex = left;
  32.             for (int i = left + 1; i < right; i++) {
  33.                 if (array[maxIndex] < array[i]) {
  34.                     maxIndex = i;
  35.                 }
  36.                 if (array[minIndex] > array[i]) {
  37.                     minIndex = i;
  38.                 }
  40.             }
  41.       //如果出现left位置的元素值最大，则，
  42.         //先交换left和minIndex,这样最大值的下标就变成minIndex了
  43.        //接下来 maxIndex = minIndex，就把最大值当前的下标确定了，再进行交换right就是最大的
  44.             swap(array, minIndex, left);
  45.             if (maxIndex == left) {
  46.                 maxIndex = minIndex;
  47.             }
  48.             swap(array, maxIndex, right);
  49.             left++;
  50.             right--;
  51.         }

堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

  1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
  2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

算法步骤

  1. 创建一个堆 H[0……n-1]；
  2. 把堆顶（最大值）和堆尾互换；
  3. 把堆的大小缩小 1，并调用 shiftdown(0)（向下调整方法），目的是把新的数组顶端数据调整到相应位置；
  4. 重复步骤 2，直到堆的尺寸为 1。

动图演示

79453a58b9c744f08d8f1ea9754f0f79.png

特性总结

  1. 堆排序使用堆来选数，效率就高了很多。
  2. 时间复杂度：O(N*logN)
  3. 空间复杂度：O(1)
  4. 稳定性：不稳定

代码实现

  1. public static void heapSort(int[] array) {
  2.         //调用方法建堆
  3.         createBigHeap(array);
  4.         //定义堆尾，然后堆顶和堆尾交换
  5.         int end = array.length-1;
  6.         //向下调整
  7.         while (end > 0){
  8.             swap(array,0,end)
  9.             shiftDown(array,0, end);
  10.             end--;
  11.         }
  13.     }
  14.     //建堆
  15.     private static void createBigHeap(int[] array) {
  16.         for (int parent = (array.length-1-1)/2;parent > = 0; parent--){
  17.             shiftDown(array,parent,array.length);
  18.         }
  20.     }
  21.     //向下调整
  22.     private static void shiftDown(int[] array,int parent,int len) {
  23.         int child = 2*parent+1;
  24.         //判断左孩子是否存在
  25.         while (child < len){
  26.             //判断右孩子是否存在，并且让最小的还孩子==child
  27.            if (child + 1 < len && array[child]< array[child+1]) {
  28.                 child ++;
  29.             }
  30. //判断孩子和父母结点的大小，向下调整
  31.             if (array[child] > array[parent]) {
  32.                 swap(array,parent,child);
  33.                 parent = child;
  34.                 child = 2*parent+1;
  35.             }else {
  36.                 break;
  37.             }
  38.             }
  40.         }

三、交换类排序

基本思想

所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动

冒泡排序

算法步骤

1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

3.针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。（最多排n-1趟）

（也可以逆序排序，第一个比第二个小，就交换他们两个，第二步最后最后的元素会是最小的数，这样排序完成以后是从大到小有序的）

动图演示

5a96590adea7bf378c1a334d07d48ff7.gif

特性总结

  1. 冒泡排序是一种非常容易理解的排序
  2. 时间复杂度：O(N^2)
  3. 空间复杂度：O(1)

  4. 稳定性：稳定

  5. 最好情况 (有序) ：只需要一趟排序，比较次数=n-1，交换次数=0，最好时间复杂度=O(n)

  6. 最坏情况 (逆序) ：比较次数 = (n-1)+(n-2)+…+1 = n(n-1)/2 = 交换次数

最坏时间复杂度 = O(n²)，平均时间复杂度 = O(n²)

  1. 冒泡排序可以用于链表、顺序表

代码实现

  1. public static void bubbleSort(int[] array) {
  2.             for (int i = 0; i < array.length-1; i++) {
  3.                 boolean flg = false;
  4.                 for (int j = 0; j < array.length-1-i; j++) {
  5.                     if(array[j] < array[j+1]){
  6.                         swap(array,j,j+1 );
  7.                         flg = true;
  8.                     }
  10.                 }
  11.                 if (flg = false){
  12.                     return;//break;
  14.                 }
  16.             }
  17.         }

快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

快速排序又是一种分而治之思想在排序算法上的典型应用

#

1d43762b58681c0ace7caa3fa93b33da.gif

// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int[] array, int left, int right)
{
if(right - left <= 1)
return;
// 按照基准值对array数组的 [left, right)区间中的元素进行划分
int div = partion(array, left, right);
// 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
// 递归排[left, div)
QuickSort(array, left, div);
// 递归排[div+1, right)
QuickSort(array, div+1, right);
}

将区间按照基准值划分为左右两半部分的常见方式：

1、Hoare版

Hoare法是以快排的创始人Hoare命名的，也是快排最初的实现版本。其基本思想就是用两个指针分别指向待排序数组的开头和结尾。

227955f80c724ce7aad1735cb77d6c82.png

过程描述：

  • 如图，我们取头结点的值为key
  • 先将left作为基准，开始移动
  • right指针移动，当找到小于key的值停止移动
  • left指针移动，当找到大于key的值停止移动
  • 将left和right所对应的值进行交换。重复上述过程直到两者相遇（right == left）
  • 此时相遇处就是基准
  • 相遇后，将key的值与相遇处的值交换（pivot）

注意：

  • 如果我们取头值作为我们的key值，那么我们一定要让右指针先移动
  • 如果我们取尾值作为我们的key值，那么我们一定要让左指针先移动

动图演示：

76415113b43b495c92c421d9a52692c7.gif

代码实现：

  1. private static int partition2(int[] array,int left,int right) {
  2.         int tmp = array[left];
  3.         int i = left;
  4.         while (left < right) {
  5.               //right移动
  6.             while (left< right && array[right] >= tmp) {
  7.                 right--;
  8.             }
  9.              //left移动
  10.             while (left< right && array[left] <= tmp) {
  11.                 left++;
  12.             }
  13.              //right，left交换位置
  14.             swap(array,left,right);
  15.         }
  16. //最开始的left（基准）和现在的left换
  17.         swap(array,left,i);
  18.         return left;
  19.     }

2.挖坑法

我们需要在key处挖一个坑（把6拿出来存在一个tmp变量里），形成一个坑位，然后R向左找比6小的放进坑里，就又形成了一个新的坑，然后L向右找，找到比6大的，放进新的坑

我们还是用动图演绎

4a1cb0aa5a6248aaad769c5b5be9a410.gif

  1. private static int partition(int[] array,int left,int right) {
  2.         int tmp = array[left];
  3.         while (left < right) {
  4.             while (left< right && array[right] >= tmp) {
  5.                 right--;
  6.             }
  7.             array[left] = array[right];
  8.             while (left< right && array[left] <= tmp) {
  9.                 left++;
  10.             }
  11.             array[right] = array[left];
  12.         }
  13.         array[left] = tmp;
  14.         return left;
  15.     }

3、前后指针法

需要两个指针，一个在前一个在后，分别用cur表示前指针，prev表示后指针，

过程描述：

初始时，我们规定cur在prev的后一个位置，这里我们还是选择第一个数为基准值

prev每次都需要指向从左到它本身之间最后一个小于基准值的数
如果cur的值大于基准值，这时只让cur左移
如果cur指向的位置小于基准值，次时我们让prev向左移动
判断prev左移后是否与cur的位置相等 ，若不相等，则交换cur和prev的值，否则cur左移
直到cur > R后，我们再交换prev和key，这样基准值的位置也就确定了

e035da9fb07e48cda20f4ad02b1fb064.gif

代码实现：

  1. private static int partition3(int[] array,int left,int right) {
  2.         int prev = left ;
  3.         int cur = left+1;
  4.         while (cur <= right) {
  5.             if(array[cur] < array[left] && array[++prev] != array[cur]) {
  6.                 swap(array,cur,prev);
  7.             }
  8.             cur++;
  9.         }
  10.         swap(array,prev,left);
  11.         return prev;
  12.     }

快速排序的优化

1. 递归到小的子区间时，可以考虑使用插入排序

每次递归的时候，越到后面递归的次数越多 而且，数据都是再慢慢变成有序的

所以我们可以在最后基几层使用插入排序来提高排序效率

2. 三数取中法选key

排序的过程中如果遇到数据有序，则有可能出现递归单分支二叉树的情况，这样递归的深度会太深，出现溢出的情况，所以需要尽量让每次划分更均匀

我们用 三数取中法 选key

  • 三数取中：头，尾，中间元素中 大小居中 的那一个
  • 再把这个元素和队头元素互换，作为key

代码实现：

  1. public static void quickSort1(int[] array) {
  2.         quick(array,0,array.length-1);
  3.     }
  4.     private static void quick(int[] array,int start,int end) {
  5.         //为什么取大于号  ： 1 2 3 4 5 6
  6.         if(start >= end) {
  7.             return;
  8.         }
  9.         //使用这个优化 主要解决 减少递归的次数
  10.         if(end - start + 1 <= 14) {
  11.             //插入排序
  12.             insertSort2(array,start,end);
  13.             return;
  14.         }
  15.         //System.out.println("start:"+start+"  end: "+end);
  16.         //三数取中法
  17.         int index = midThree(array, start,end);
  18.         swap(array,index,start);
  19.         int pivot = partition(array,start,end);//划分
  20.         quick(array,start,pivot-1);
  21.         quick(array,pivot+1,end);
  22.     }
  23.     private static void insertSort2(int[] array,int left,int right) {
  24.         for (int i = left+1; i <= right; i++) {
  25.             int tmp = array[i];
  26.             int j = i-1;
  27.             for (; j >= left ; j--) {
  28.                 if(array[j] > tmp) {
  29.                     array[j+1] = array[j];
  30.                 }else {
  31.                     break;
  32.                 }
  33.             }
  34.             array[j+1] = tmp;
  35.         }
  36.     }
  37. //三位数取中法
  38.     private static int midThree(int[] array,int left,int right) {
  39.         int mid = (left+right) / 2;
  40.         if(array[left] < array[right]) {
  41.             if(array[mid] < array[left]) {
  42.                 return left;
  43.             }else if(array[mid] > array[right]) {
  44.                 return right;
  45.             }else {
  46.                 return mid;
  47.             }
  48.         }else {
  49.             if(array[mid] < array[right]) {
  50.                 return right;
  51.             }else if(array[mid] > array[left]) {
  52.                 return left;
  53.             }else {
  54.                 return mid;
  55.             }
  56.         }
  58.     }

非递归实现快速排序

我们需要用到栈

我们之前是在已经确定基准点之后，对剩余的区间递归进行同样的操作

我们现在创建一个栈，把剩余区间的左、右位置的下标分别放入栈中，如图是已经找到一个基准6的情况

657678aa47904b139ae2f177a006b9b5.png

然后弹出栈顶一个元素9给H，再弹出一个栈顶元素6给L，根据新的L和H找到新的基准，再重复上面的操作

e66dbb654ebf43c99a64cc4acb151f0b.png

代码实现：

  1. /**
  2.      * 非递归实现快速排序
  3.      *
  4.      * @param array
  5.      */
  6.     public static void quickSort(int[] array) {
  7.         Deque<Integer> stack = new LinkedList<>();
  8.         int left = 0;
  9.         int right = array.length-1;
  10.         int pivot = partition(array,left,right);
  11.         if(pivot > left+1) {
  12.             stack.push(left);
  13.             stack.push(pivot-1);
  14.         }
  15.         if(pivot < right-1) {
  16.             stack.push(pivot+1);
  17.             stack.push(right);
  18.         }
  20.         while (!stack.isEmpty()) {
  21.             right= stack.pop();
  22.             left = stack.pop();
  23.             pivot = partition(array,left,right);
  24.             if(pivot > left+1) {
  25.                 stack.push(left);
  26.                 stack.push(pivot-1);
  27.             }
  28.             if(pivot < right-1) {
  29.                 stack.push(pivot+1);
  30.                 stack.push(right);
  31.             }
  32.         }
  34.     }

快速排序总结

  1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
  2. 时间复杂度：O(N*logN)
  3. 空间复杂度：O(logN)—O（N）(取决于递归的深度，如果数据是有序的，则深度为N，非顺序的深度为二叉树的高度logN。）
  4. 稳定性：不稳定

#

归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；

算法步骤

即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

图示

344a6e5b3bea4081a3b1765b33e8b4a4.png

7392be673359dcbb2ba6fb6c8d58f93b.gif

特性总结

  1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
  2. 时间复杂度：O(N*logN)
  3. 空间复杂度：O(N)

  4. 稳定性：稳定

  5. 时间复杂度和数据有没有序无关

代码实现

  1. public static void mergeSort(int []arr ,boolean ascending){        
  2.         int gap = 1;
  3.         while (gap < array.length) {
  4.             // i += gap * 2 当前gap组的时候，去排序下一组
  5.             for (int i = 0; i < array.length; i += gap * 2) {
  6.                 int left = i;
  7.                 int mid = left+gap-1;//有可能会越界
  8.                 if(mid >= array.length) {
  9.                     mid = array.length-1;
  10.                 }
  11.                 int right = mid+gap;//有可能会越界
  12.                 if(right>= array.length) {
  13.                     right = array.length-1;
  14.                 }
  15.                 merge(array,left,right,mid);
  16.             }
  17.             //当前为2组有序  下次变成4组有序
  18.             gap *= 2;
  19.         }
  21.             return nums;
  22.     }
  23.      private static void merge(int[] array,int start,int end,int mid) {
  24.         int s1 = start;
  25.         //int e1 = mid;
  26.         int s2 = mid+1;
  27.         //int e2 = end;
  28.         int[] tmp = new int[end-start+1];
  29.         int k = 0;//tmp数组的下标
  30.         while (s1 <= mid && s2 <= end) {
  31.             if(array[s1] <= array[s2]) {
  32.                 tmp[k++] = array[s1++];
  33.             }else {
  34.                 tmp[k++] = array[s2++];
  35.             }
  36.         }
  37.         while (s1 <= mid) {
  38.             tmp[k++] = array[s1++];
  39.         }
  40.         while (s2 <= end) {
  41.             tmp[k++] = array[s2++];
  42.         }
  44.         for (int i = 0; i < tmp.length; i++) {
  45.            array[i+start] = tmp[i];
  46.         }
  48.     }
  49.         private static void swap(int[] nums,int i,int j) {
  50.             int tmp = array[i];
  51.             narray[i] = array[j];
  52.             array[j] = tmp;
  53.         }

其他排序

计数排序

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。

操作步骤：

  1. 统计相同元素出现次数
  2. 根据统计的结果将序列回收到原来的序列中

图示

57815a78dc474c75b45f4c24a12ebb6a.png

特性总结

  1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
  2. 时间复杂度：O(MAX(N,范围))
  3. 空间复杂度：O(范围)
  4. 稳定性：稳定

代码实现

  1. public static void countSort(int[] array) {
  2.         //1. 遍历数组 找到最大值 和 最小值
  3.    int max = array[0];
  4.    int min = array[0];
  5.         for (int i = 0; i < array.length; i++) {
  6.             if (max < array[i]){
  7.                 max = array[i];
  8.             }
  9.             if (min > array[i]){
  10.                 min = array[i];
  11.             }
  12.         }
  13.         //2. 根据范围 定义计数数组的长度
  14.         int len = max -min +1;
  15.        int[] count = new int[len];
  17.         //3.遍历数组，在计数数组当中 记录每个数字出现的次数 O(N)
  18.         for (int i = 0; i < array.length; i++) {
  19.             count[array[i]-min ] ++;
  21.         }
  22.         //4.遍历计数数组
  23.         int index = 0;
  24.         for (int i = 0; i < count.length; i++) {
  25.             while (count[i] > 0 ){
  26.                 array[index] = i+min;  //+min是为了把真实的值放进去
  27.                 index++;
  28.                 count[i]--;//因为有多个相同的数，要输出多次
  29.             }
  31.         }
  32.     }

基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

动图演示

afb526d9f4714b68b3db1fe5efabc06a.gif

代码实现

  1. public static void radixSort(int[] arr){
  2.         radixSort(arr,true);
  3.     }
  4.     public static void radixSort(int[]arr,boolean ascending) {
  5.         int max = Integer.MIN_VALUE;
  6.         int min = Integer.MAX_VALUE;
  7.         //求出最大值、最小值
  8.         for (int i = 0; i < arr.length; i++) {
  9.             max = Math.max(max, arr[i]);
  10.             min = Math.min(min, arr[i]);
  11.         }
  12.         if (min < 0) {    //如果最小值小于0，那么把每个数都减去最小值，这样可以保证最小的数是0
  13.             for (int i = 0; i < arr.length; i++) {
  14.                 arr[i] -= min;
  15.             }
  16.             max -= min; //max也要处理！
  17.         }
  18.         //很巧妙求出最大的数有多少位
  19.         int maxLength = (max + "").length();
  20.         int[][] bucket = new int[10][arr.length]; //建一个二维数组，一维代表0到9，二维存放符合数
  21.         int[] bucketElementCount = new int[10]; // 用于记录0到9某位存在数字的个数
  22.         //循环次数等于最大数的位数
  23.         for (int i = 0, n = 1; i < maxLength; i++, n *= 10) { //个位 十位 百位 这样遍历
  24.             for (int j = 0; j < arr.length; j++) {
  25.                 int value = arr[j] / n % 10;//求末位
  26.                 bucket[value][bucketElementCount[value]] = arr[j];
  27.                 bucketElementCount[value]++;
  28.             }
  29.             //升序
  30.             if (ascending) {
  31.                 int index = 0;
  32.                 //从左到右，从下到上取出每个数
  33.                 for (int j = 0; j < bucketElementCount.length; j++) {
  34.                     if (bucketElementCount[j] != 0) {
  35.                         for (int k = 0; k < bucketElementCount[j]; k++) {
  36.                             arr[index] = bucket[j][k];
  37.                             index++;
  38.                         }
  39.                     }
  40.                     bucketElementCount[j] = 0;
  41.                 }
  42.             } else { // 降序
  43.                 int index = 0;
  44.                 //从右到左，从下到上取出每个数
  45.                 for (int j = bucketElementCount.length - 1; j >= 0; j--) {
  46.                     if (bucketElementCount[j] != 0) {
  47.                         for (int k = 0; k < bucketElementCount[j]; k++) {
  48.                             arr[index] = bucket[j][k];
  49.                             index++;
  50.                         }
  51.                     }
  52.                     bucketElementCount[j] = 0;
  53.                 }
  54.             }
  55.         }
  57.             if (min < 0) {
  58.                 for (int i = 0; i < arr.length; i++) {
  59.                     arr[i] += min;
  60.                 }
  61.             }
  62.         }

桶排序

划分多个范围相同的区间，每个子区间自排序，最后合并

图示

20190219081232815.png

代码实现

  1. public static void bucketSort(int[] arr){
  3.             // 计算最大值与最小值
  4.             int max = Integer.MIN_VALUE;
  5.             int min = Integer.MAX_VALUE;
  6.             for(int i = 0; i < arr.length; i++){
  7.                 max = Math.max(max, arr[i]);
  8.                 min = Math.min(min, arr[i]);
  9.             }
  11.             // 计算桶的数量
  12.             int bucketNum = (max - min) / arr.length + 1;
  13.             ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
  14.             for(int i = 0; i < bucketNum; i++){
  15.                 bucketArr.add(new ArrayList<Integer>());
  16.             }
  18.             // 将每个元素放入桶
  19.             for(int i = 0; i < arr.length; i++){
  20.                 int num = (arr[i] - min) / (arr.length);
  21.                 bucketArr.get(num).add(arr[i]);
  22.             }
  24.             // 对每个桶进行排序
  25.             for(int i = 0; i < bucketArr.size(); i++){
  26.                 Collections.sort(bucketArr.get(i));
  27.             }
  29.             // 将桶中的元素赋值到原序列
  30.             int index = 0;
  31.             for(int i = 0; i < bucketArr.size(); i++){
  32.                 for(int j = 0; j < bucketArr.get(i).size(); j++){
  33.                     arr[index++] = bucketArr.get(i).get(j);
  34.                 }
  35.             }
  36.         }

总结

fcbb47c65c864a3dad6705763bc86647.png




































































排序方法 最好 平均 最坏 空间复杂度 稳定性
冒泡排序 O(n) O(n^2) O(n^2) O(1) 稳定
插入排序 O(n) O(n^2) O(n^2) O(1) 稳定
选择排序 O(n^2) O(n^2) O(n^2) O(1) 不稳定
希尔排序 O(n) O(n^1.3) O(n^2) O(1) 不稳定
堆排序 O(n log(n)) O(n log(n)) O(n log(n)) O(1) 不稳定
快速排序 O(n log(n)) O(n log(n)) O(n^2) O(log(n)) ~ O(n) 不稳定
归并排序 O(n log(n)) O(n log(n)) O(n log(n)) O(n) 稳定

【注意：希尔排序暂时不能准确得出最好、最坏的时间复杂度，大量的研究得出的局部结论是O(N^1.3)】

说明：本文部分图片来源于网络，如有侵权请联系我删除。本文仅作为个人学习分享，如有错误欢迎小伙伴们留言讨论。

发表评论

表情：
评论列表 （有 0 条评论，202人围观）

还没有评论，来说两句吧...

相关阅读

    相关 十大经典排序算法总结

    十种常见排序算法可以分为两大类： > 非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。 >

    忘是亡心i忘是亡心i/ 0 赞/ 282 阅读