Common Sort - 排序 - Java

转x33g5p2x  于2022-03-07 转载在 Java  
字(20.7k)|赞(0)|评价(0)|浏览(461)

排序

概念

排序，就是使一串记录，按照其中的某个 或 某些关键字的大小，递增 或 递减 的 排列起来的操作。
平时的上下文中，如果提到排序，通常指的是 排升序（非降序）。
通常意义上的排序，都是指的原地排序（in place sort）
原地排序：就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序。

稳定性（重要）

两个相等的数据，如果经过排序后，排序算法能保证其相对位置不发生变化，则我们称该算法是具备稳定性的排序算法。

应用 - 举例

1.、各大商城的价格从低到高等

2、中国大学排名

常见的排序算法（8 种）- 总览

直接插入排序

插入排序：非常简单！仅次于冒泡排序。

根据这个思维：第一个数据是有序的，也就是说：在我们遍历的时候，是从下标1 开始的。
具体的操作见下图：

模拟实现 - 插入排序

  1. import java.util.Arrays;
  3. public class DirectInsertionSort {
  4.     /*
  5.     * 时间复杂度： O(N^2)
  6.     * 最好情况： O(N) 数组有序的情况
  7.     * 空间复杂度：O(1)  只有 一个 tmp 变量是常驻的
  8.     * 稳定性：稳定
  9.     * */
  10.     public static void insertionSort(int[] array){
  11.         for(int i = 1;i < array.length;i++){
  12.             int tmp = array[i];
  13.             int j = i - 1;
  14.             for( ; j >= 0;j-- ){
  15.             // 前移
  16.                 if(tmp < array[j]){
  17.                     array[j + 1] = array[j];
  18.                 }else{
  19.                     break;
  20.                 }
  21.             }
  22.             // 插入【无论是找到了合适插入的位置，还是不存在比 tmp更小的值，j自减到 -1.执行的代码都是一样的】
  23.             array[j+1] = tmp;
  24.         }
  25.     }
  27.     public static void main(String[] args) {
  28.         int[] array = {23,45,56,68,8,9};
  29.         insertionSort(array);
  30.         System.out.println(Arrays.toString(array));
  31.     }
  33. }

稳定性分析

结论

一个稳定的排序，可以实现为 不稳定的排序。
但是，一个本身就不稳定的排序是 无法变成 稳定的排序。
直接插入排序 是 有序的。
它的时间复杂度是 O(N^2)；最好情况:O(N【数组有序】
也就是说：对于直接插入排序，数据越有序越快！
由此，不难联想到：直接插入排序 有时候 会用于 优化 排序。
【假设：假设我们有一百万个数据需要排序，在排序的过程中，区间越来越小，数据越来越有序。直接插入排序的时间复杂度为 O(N),N 越来越小，那么，使用 直接插入排序是不是越来越快！也就是说：直接插入排序 有时候会 用于 排序优化】
直接插入排序经常使用在 数据量不多，且整体数据趋于有序的。

  1. import java.util.Random;
  3. public class DirectInsertionSort {
  4.     /*
  5.     * 时间复杂度： O(N^2)
  6.     * 空间复杂度：O(1)  只有 一个 tmp 变量是常驻的
  7.     * 稳定性：稳定
  8.     * */
  9.     public static void insertionSort(int[] array){
  10.         for(int i = 1;i < array.length;i++){
  11.             int tmp = array[i];
  12.             int j = i - 1;
  13.             for( ; j >= 0;j-- ){
  14.                 if(tmp < array[j]){
  15.                     array[j + 1] = array[j];
  16.                 }else{
  17.                     break;
  18.                 }
  19.             }
  20.             array[j+1] = tmp;
  21.         }
  22.     }
  23.     // 有序
  24.     public static void test1(int capacity){
  25.         int[] array = new int[capacity];
  26.         for (int i = 0; i < capacity; i++) {
  27.             array[i] = i;
  28.         }
  29.         // 记录开始排序开始时间
  30.         long start = System.currentTimeMillis();
  31.         insertionSort(array);
  32.          // 记录开始排序结束时间
  33.         long end = System.currentTimeMillis();
  34.          // 输出 整个排序过程的时间
  35.         System.out.println(end - start);
  36.     }
  37.     // 无序
  38.     public static void test2(int capacity){
  39.         int[] array = new int[capacity];
  40.         Random random = new Random();
  41.         for (int i = 0; i < capacity; i++) {
  42.             array[i] = random.nextInt(capacity);
  43.         }
  44.         // 记录开始排序开始时间
  45.         long start = System.currentTimeMillis();
  46.         insertionSort(array);
  47.          // 记录开始排序结束时间
  48.         long end = System.currentTimeMillis();
  49.          // 输出 整个排序过程的时间
  50.         System.out.println(end - start);
  51.     }
  53.     public static void main(String[] args) {
  54.         test1(10000);
  55.         test2(10000);
  56.     }
  57. }

希尔排序

思考

假设，现有 1 00 00 个 数据，如果对着组数据进行排序，使用插入排序。
时间复杂度为 O(N^2)【最坏情况：逆序的情况】
故 1 00 00 * 1 00 00 == 1 亿（量化）
它不是 1 万个数据嘛。那么，我们可以不可以这么去想：将这 一万个数据拆分成 100 组【每组100个数据】，对其中一组进行直接插入排序的时间复杂度为 100*100 ==1 00 00（量化），这样的分组还有99个，也就是将这一百组使用直接插入排序的时间复杂度为 1 00 00 * 1 00 = 1 百万（量化）。
有没有发现，分组过后，时间复杂度效率 提高很多，由1亿 变成了 1百万。
也就是说：如果采用分组的思想，我们会发现 时间复杂度会有一个很大的改变。
而这种分组的思想 就是 希尔排序。

原理

希尔排序又称缩小增量法。希尔排序法的基本思想是：先选定一个整数 n，把待排序文件中所有数据分成 n 组，所有距离为 数据量 / n 的 分在同一组。并且对每一组内的数据进行排序。然后，重复上述 分组 和 排序工作。当分组的组数为 1 是，所有数据 在进行 一个排序。

1、希尔排序 是对直接插入排序的优化。
2、当 group > 1 时都是预排序，目的是让数组更接近于有序。当 group == 1时，数组已经接近有序了，这样就会更快。对于整体而言，可以达到优化的效果。
那么，问题来了！我们怎去确定分多少组，而且越分越少。
【取自清华大学出版的一本书《数据结构》】

科学家的分组思维

现在这组数据，我们相当于只排序了一组数据，就走人了。数组整体还不是有序的。那么，我们该怎么解决这个问题？往下看！

模拟实现 - 希尔排序

  1. import java.util.Arrays;
  3. public class ShellSort {
  4.     /*
  5.     * 时间复杂度和增量有关系，所以无法得出准确的时间复杂度
  6.     * 但只需要记住：在一定的范围里，希尔排序的时间复杂度为 O(N^1.3 ~ N^1.5)
  7.     * 空间复杂度为 O(1)
  8.     * 稳定性：不稳定
  9.     * 判断稳定性的技巧：如果在比较的过程中 发生了 跳跃式交换。那么，就是不稳定的排序。
  10.     * */
  11.     public static void shell(int[] array,int group){
  12.         for (int i = group; i < array.length; i += 1) {
  13.             int tmp = array[i];
  14.             int j = i-group;
  15.             for (; j >= 0; j-=group) {
  16.                 if(tmp < array[j]){
  17.                     array[j+group] = array[j];
  18.                 }else{
  19.                     break;
  20.                 }
  21.             }
  22.             array[j+group] = tmp;
  23.         }
  24.     }
  25.     public static void shellSort(int[] array){
  26.         int group = array.length;
  27.         // 预排序
  28.         while(group > 1){
  29.             // 第一次分组委 数组的长度，即 头尾判断。
  30.             // 其后，每次分组个数，缩小一倍。
  31.             shell(array,group);
  32.             group /= 2;
  33.         }
  34.         // 最后调整
  35.         shell(array,1);
  36.     }
  38.     public static void main(String[] args) {
  39.         int[] array ={12,5,9,34,6,8,33,56,89,0,7,4,22,55,77};
  40.         shellSort(array);
  41.         System.out.println(Arrays.toString(array));
  42.     }
  43. }

总结

其实 希尔排序就是一个直接插入排序。

选择排序

直接选择排序 - 原理

优化

定义 一个 变量， 用来记录 此时的 i 后面最小值的下标。等 j 遍历完了，最小值的下标也就拿到了。此时，再进行交换。
这样就不必让上面那样，遇到比 i下标元素 小的，就交换。

代码如下

  1. import java.util.Arrays;
  3. public class SelectSort {
  4.     /*
  5.     * 稳定性： 不稳定 见附图
  6.     * 时间复杂度：O(N^2) 》》 外层循环 n -1，内层循环 n -1
  7.     * 空间复杂度：O(1)
  8.     * */
  9.     public static void selectSort(int[] array){
  10.         for (int i = 0; i < array.length-1; i++) {
  11.             int index = i;
  12.             for (int j = i + 1; j < array.length; j++) {
  13.                 if(array[index] > array[j]){
  14.                     index = j;
  15.                 }
  16.             }
  17.             int tmp = array[i];
  18.             array[i] = array[index];
  19.             array[index] = tmp;
  20.         }
  21.     }
  23.     public static void main(String[] args) {
  24.         int[] array = {12,6,10,3,5};
  25.         selectSort(array);
  26.         System.out.println(Arrays.toString(array));
  27.     }
  28. }

附图

双向选择排序 （了解）

每一次从无序区间选出最小 + 最大的元素，存放在无序区间的最前和最后，直到全部待排序的数据元素排完 。

代码如下

  1. import java.util.Arrays;
  3. public class SelectSortOP {
  4.     public static void selectSortOP(int[] array){
  5.         int low = 0;
  6.         int high = array.length - 1;
  7.         // [low,high] 表示整个无序区间
  8.         while(low < high){
  9.             int min = low;
  10.             int max = low;
  11.             for (int i = low+1; i <= high; i++) {
  12.                 if(array[i] < array[min]){
  13.                     min = i;
  14.                 }
  15.                 if(array[i] > array[max]){
  16.                     max = i;
  17.                 }
  18.             }
  19.             swap(array,min,low);
  20.             if(max == low){
  21.                 max = min;
  22.             }
  23.             swap(array,max,high);
  24.             low++;
  25.             high--;
  26.         }
  28.     }
  29.     public static void swap(int[] array,int x,int y){
  30.         int tmp = array[x];
  31.         array[x] = array[y];
  32.         array[y] = tmp;
  33.     }
  35.     public static void main(String[] args) {
  36.         int[] array = {9, 5, 2, 7, 3, 6, 8 };
  37.         selectSortOP(array);
  38.         System.out.println(Arrays.toString(array));
  39.     }
  40. }

堆排序

基本原理也是选择排序，只是不在使用遍历的方式查找无序区间的最大的数，而是通过堆来选择无序区间的最大的数。
注意： 排升序要建大堆；排降序要建小堆.
这个我就不讲，因为我在堆/优先级中讲的很清楚！
有兴趣的，可以点击 链接关键字 ，跳转到该文章，该内容在 文章目录最后面。
这里我们就直接上代码。

代码

  1. import java.util.Arrays;
  3. public class HeapSort {
  4.     public static void main(String[] args) {
  5.         int[] array = {12,8,5,4,10,15};
  6.         creationHeap(array);// 建堆的时间复杂度：O(N)
  7.         System.out.println(Arrays.toString(array));
  8.         heapSort(array);// 堆排序的时间复杂度：O(N * log2 N)
  9.         // 空间复杂度：O(1)
  10.         System.out.println(Arrays.toString(array));
  11.     }
  12.     // 创建一个大根堆
  13.     public static void creationHeap(int[] array){
  14.         for (int parent = (array.length-1-1)/2; parent >= 0; parent--) {
  15.             shiftDown(array,parent,array.length);
  16.         }
  17.     }
  18.     public static void heapSort(int[] array){
  19.         /*
  20.         * 时间复杂度：O(N * log2 N)
  21.         * 空间复杂度：O(1)
  22.         * 稳定性：不稳定
  23.         * */
  24.         int end = array.length - 1;
  25.         while(end>0){
  26.             int tmp = array[end];
  27.             array[end] = array[0];
  28.             array[0] = tmp;
  29.             shiftDown(array,0,end);
  30.             end--;
  31.         }
  32.     }
  33.     // 向下调整
  34.     public static void shiftDown(int[] array,int parent,int len){
  35.         int child = parent * 2 + 1;// 做孩纸
  36.         while(child < len){
  37.             // 获取左右子树最大值的下标
  38.             if(child+1 < len && (array[child] < array[child+1])){
  39.                 child++;
  40.             }
  41.             if(array[child] > array[parent]){
  42.                 int tmp = array[child];
  43.                 array[child] = array[parent];
  44.                 array[parent] = tmp;
  45.                 parent = child;
  46.                 child = parent * 2 + 1;
  47.             }else{
  48.                 break;
  49.             }
  50.         }
  51.     }
  52. }

冒泡排序

代码如下 - 未优化

  1. import java.util.Arrays;
  2.     /*
  3.      * 时间复杂度：O(N^2) 【无论是最好情况，还是最坏情况，时间复杂度都不变】
  4.      * 空间复杂度：O(1)
  5.      * 稳定性：稳定【未发生跳跃式交换】
  6.      * */
  7. public class BubbleSort {
  8.     public static void bubbleSort(int[] array){
  9.         // 比较的趟数 = 数组的长度 - 1 【 0 ~ 3 一共 4趟】
  10.         for (int i = 0; i < array.length-1; i++) {
  11.             // 比较完一趟后，可以比较的元素个数减一。【因为靠后的数据已经有序】
  12.             // 内循环中，之所以要减一个 1，是因为防止 下面的if语句 发生 数组越界异常
  13.             for(int j = 0;j< array.length-1-i;j++){
  14.                 if(array[j] > array[j+1]){
  15.                     int tmp = array[j];
  16.                     array[j] = array[j+1];
  17.                     array[j+1] = tmp;
  18.                 }
  19.             }
  20.         }
  21.     }
  23.     public static void main(String[] args) {
  24.         int[] array = {12,6,10,3,5};
  25.         bubbleSort(array);
  26.         System.out.println(Arrays.toString(array));
  27.     }
  28. }

代码优化思维

代码如下 - 优化

  1. import java.util.Arrays;
  3. public class BubbleSort {
  4.     /*
  5.     * 时间复杂度：O(N^2)
  6.     * 最好情况【数组有序】可以达到 O(N)
  7.     * 空间复杂度：O(1)
  8.     * 稳定性：稳定【未发生跳跃式交换】
  9.     * */
  10.     public static void bubbleSort(int[] array){
  11.         for (int i = 0; i < array.length-1; i++) {
  12.             boolean flag = true;
  13.             for(int j = 0;j< array.length-1-i;j++){
  14.                 if(array[j] > array[j+1]){
  15.                     int tmp = array[j];
  16.                     array[j] = array[j+1];
  17.                     array[j+1] = tmp;
  18.                     flag = false;// 表示这一趟比较，数组是无序的
  19.                 }
  20.             }
  21.             // flag == true
  22.             if(flag){
  23.                 break;
  24.             }
  25.         }
  26.     }
  28.     public static void main(String[] args) {
  29.     // 前半段无序，后半段有序
  30.         int[] array = {2,3,1,4,5};
  31.         bubbleSort(array);
  32.         System.out.println(Arrays.toString(array));
  33.     }
  34. }

未优化 和 优化代码 运行速度比较

  1. public class BubbleSort {
  2.     // 优化
  3.     public static void bubbleSort2(int[] array){
  4.         for (int i = 0; i < array.length-1; i++) {
  5.             boolean flag = true;
  6.             for(int j = 0;j< array.length-1-i;j++){
  7.                 if(array[j] > array[j+1]){
  8.                     int tmp = array[j];
  9.                     array[j] = array[j+1];
  10.                     array[j+1] = tmp;
  11.                     flag = false;
  12.                 }
  13.             }
  14.             // flag == true
  15.             if(flag){
  16.                 break;
  17.             }
  18.         }
  19.     }
  20.     // 未优化
  21.     public static void bubbleSort1(int[] array){
  22.         for (int i = 0; i < array.length-1; i++) {
  23.             for(int j = 0;j< array.length-1-i;j++){
  24.                 if(array[j] > array[j+1]){
  25.                     int tmp = array[j];
  26.                     array[j] = array[j+1];
  27.                     array[j+1] = tmp;
  28.                 }
  29.             }
  30.         }
  31.     }
  33.     public static void main(String[] args) {
  34.         int[] array = new int[10000];
  35.         for (int i = 0; i < array.length; i++) {
  36.             array[i] = i;
  37.         }
  38.         long start = System.currentTimeMillis();
  39.         bubbleSort2(array);// 优化
  40.         long end = System.currentTimeMillis();
  41.         System.out.println(end - start);// 输出排序所需时间
  42.         
  43.         start = System.currentTimeMillis();
  44.         bubbleSort1(array);// 未优化
  45.         end = System.currentTimeMillis();
  46.         System.out.println(end - start);//输出排序所需时间
  47.     }
  48. }

快速排序 - 重点

原理

1、从待排序区间选择一个数，作为基准值（pivot）
2、Partition（分割）：遍历整个待排序区间，将比基准值小的（可以包含相等的）放到基准值的左边，将比基准值大的（可以包含相等的）放到基准值的右边。
3、采用分治思想，对左右两个小区间按照同样的方式处理，直到小区间的长度 == 1.代表已经有序，或者小区间的长度 == 0，代表没有数据。

总结

快速排序，其实说白了 和二叉树]很像，先根，再左，后右。利用递归去实现！

程序框架

  1. public class QuickSort {
  2.     public static void quickSort(int[] array){
  3.         quick(array,0, array.length);
  4.     }
  5.     public static void quick(int[] array,int start,int end){
  6.         if(start >= end){
  7.             return;
  8.         }
  9.         int pivot = partiton(array,start,end);
  10.         quick(array,start,pivot-1);// 递归左边
  11.         quick(array,pivot+1,end);// 递归右边
  12.     }
  13.     // 分割 - 找基准
  14.     private static int partiton(int[] array,int start,int end){
  16.     }
  17. }

完善 partition 部分

  1. // 分割 - 找基准
  2.     private static int partiton(int[] array,int start,int end){
  3.         int tmp = array[start];
  4.         while(start < end){
  5.             while(start < end && array[end] >= tmp){
  6.                 end--;
  7.             }
  8.             // 此时 end 下标 元素的值 是 小于 tmp的。
  9.             array[start] = array[end];
  10.             while(start<end && array[start] <= tmp){
  11.                 start++;
  12.             }
  13.             //此时 start 下标元素的值 是 大于 tmp的。
  14.             array[end] = array[start];
  15.         }
  16.         // start 和 end 相遇了，将 tmp 赋予 它们相遇下标指向的空间
  17.         array[start] = tmp;
  18.         return start;
  19.     }

代码细节部分

总程序 - 未优化

  1. import java.util.Arrays;
  3. public class QuickSort {
  4.     /*
  5.     * 时间复杂度：O(N^2) 【数据有序或者逆序的情况】
  6.     * 最好情况【每次可以均匀的分割待排序序列】：O(N * log2 N)
  7.     * 空间复杂度：O(N)[单分支的一棵树]
  8.     * 最好：log2 N
  9.     * 稳定性：不稳定
  10.     * */
  11.     public static void quickSort(int[] array){
  12.         quick(array,0, array.length-1);
  13.     }
  14.     public static void quick(int[] array,int start,int end){
  15.         if(start >= end){
  16.             return;
  17.         }
  18.         int pivot = partiton(array,start,end);
  19.         quick(array,start,pivot-1);// 递归左边
  20.         quick(array,pivot+1,end);// 递归右边
  21.     }
  22.     // 分割 - 找基准
  23.     private static int partiton(int[] array,int start,int end){
  24.         int tmp = array[start];
  25.         while(start < end){
  26.             while(start < end && array[end] >= tmp){
  27.                 end--;
  28.             }
  29.             // 此时 end 下标 元素的值 是 小于 tmp的。
  30.             array[start] = array[end];
  31.             while(start<end && array[start] <= tmp){
  32.                 start++;
  33.             }
  34.             array[end] = array[start];
  35.         }
  36.         array[start] = tmp;
  37.         return start;
  38.     }
  40.     public static void main(String[] args) {
  41.         int[] array = {6,1,2,7,9,3,4,5,10,8};
  42.         quickSort(array);
  43.         System.out.println(Arrays.toString(array));
  44.     }
  45. }

快速排序 的 时间 与 空间复杂度分析

堆排序 与 快排 的区别

细心的朋友会发现 堆排序 和 快排 的 时间复杂度在最好情况下 都是N* log2 N。
那么，两者又有什么区别？
堆排序，无论最好还是最坏情况，时间复杂度都是N* log2 N。空间复杂度 O(1)
那么，又为什么快排 比 堆排序 要快？
其实再细一点说 ：在两个排序的时间复杂度都为 N* log2 N时，其实连着前面还有 一个 k【K * N* log2 N 】，只不过快排前面的K要小一点。所以快排要快一点。
在对空间复杂度没有要求的情况： 快排
对空间复杂度有要求的情况，或者说对数据的序列也要要求： 堆排

细节拓展

if语句中 比较大小的代码中 等号是不能省略的

当 下面框选的代码 没有等号时，会造成死循环。

我就改了一下，末尾元素的值。

那么，问题来了：为什么没有等号就死循环了？

所以，在 写快排的时候，比较大小的代码，记住一定要加上等号！！！！！

目前版本的 快排代码 不支持 大量数据进行排序 - 会导致栈溢出。

这是因为 我们递归的太深了，1百万数据，4百万字节。
1TB等于1024GB;1GB等于1024MB;1MB等于1024KB;1KB等于1024Byte(字节);1Byte等于8bit(位);

有的朋友会说：这才多大啊？栈怎么会被挤爆？
这是因为在递归的时候，开辟的栈帧【函数的信息，参数等等等…都有】，所以，每次开辟的栈帧不止 4byte。故栈被挤爆了。

所以，我们要优化快排的 代码。【优化：数据有序的情况】

基准值的选择 - 优化前的知识补充

1、选择边上（左或者右） 【重点，上面使用的就是这种方法】
2、随机选择（针对 有序数据）【了解】

3、几数取中（常见的就是三数取中）：array[left]，array[mid] ，array[right]中 大小为 中间值的为基准值【优化的关键】

快速排序（几数取中法 优化）

  1. import java.util.Arrays;
  3. public class QuickSort {
  4.     /*
  5.     * 时间复杂度：O(N^2) 【数据有序或者逆序的情况】
  6.     * 最好情况【每次可以均匀的分割待排序序列】：O(N * log2 N)
  7.     * 空间复杂度：O(N)[单分支情况]
  8.     * 最好：log2 N
  9.     * 稳定性：不稳定
  10.     * */
  11.     public static void quickSort(int[] array){
  12.         quick(array,0, array.length-1);
  13.     }
  14.     public static void quick(int[] array,int start,int end){
  15.         if(start >= end){
  16.             return;
  17.         }
  18.         // 在找基准之前，先确定 start 和 end 的 中间值。[三数取中法]
  19.         int midValIndex = findMidValIndex(array,start,end);
  20.         //将它 与 start 交换。这样后面的程序，就不用改动了。
  21.         swap(array,start,midValIndex);
  22.         int pivot = partiton(array,start,end);
  23.         quick(array,start,pivot-1);// 递归左边
  24.         quick(array,pivot+1,end);// 递归右边
  25.     }
  26.     // 确定基准值下标
  27.     private static int findMidValIndex(int[] array,int start,int end){
  28.         // 确定 start 和 end 的中间下标
  29.         int mid = start + ((end - start)>>>1);// == （start + end）/ 2
  30.         // 确定 mid、start、end 三个下标，谁指向的元素是三个元素中的中间值
  31.         if(array[end] > array[start]){
  32.             if(array[start] > array[mid]){
  33.                 return start;
  34.             }else if(array[mid] > array[end]){
  35.                 return end;
  36.             }else{
  37.                 return mid;
  38.             }
  39.         }else{
  40.             // array[start] >= array[end]
  41.             if(array[end] > array[mid]){
  42.                 return end;
  43.             }else if(array[mid] > array[start]){
  44.                 return start;
  45.             }else {
  46.                 return mid;
  47.             }
  48.         }
  49.     }
  50.     // 交换两个下标元素
  51.     private static void swap(int[] array,int x,int y){
  52.         int tmp = array[x];
  53.         array[x] = array[y];
  54.         array[y] = tmp;
  55.     }
  57.     // 分割 - 找基准
  58.     private static int partiton(int[] array,int start,int end){
  59.         int tmp = array[start];
  60.         while(start < end){
  61.             while(start < end && array[end] >= tmp){
  62.                 end--;
  63.             }
  64.             // 此时 end 下标 元素的值 是 小于 tmp的。
  65.             array[start] = array[end];
  66.             while(start<end && array[start] <= tmp){
  67.                 start++;
  68.             }
  69.             array[end] = array[start];
  70.         }
  71.         array[start] = tmp;
  72.         return start;
  73.     }
  74.     // 有序
  75.     public static void test1(int capacity){
  76.         int[] array = new int[capacity];
  77.         for (int i = 0; i < capacity; i++) {
  78.             array[i] = i;
  79.         }
  80.         long start = System.currentTimeMillis();
  81.         quickSort(array);
  82.         long end = System.currentTimeMillis();
  83.         System.out.println(end - start);
  84.     }
  86.     public static void main(String[] args) {
  87.         test1(100_0000);
  88.         int[] array = {6,1,2,7,9,3,4,5,10,6};
  89.         quickSort(array);
  90.         System.out.println(Arrays.toString(array));
  91.     }
  92. }

优化总结

1、选择基准值很重要，通常使用几数取中法
2、partition 过程中把和基准值相等的数也选择出来

3、待排序区间小于一个阈(yù)值【临界值】
随着不断的划分基准，数组逐渐趋于有序，而区间随着递归也在减小。所以，利用 直接插入排序的特性【越有序越快】，来进一步优化 快排。

拓展 快速排序 - 非递归实现

非递归实现快速排序的思维

代码如下

  1. import java.util.Arrays;
  2. import java.util.Stack;
  4. public class QuickSortNonRecursion {
  5.     public static void quickSort(int[] array){
  6.         Stack<Integer> stack = new Stack<>();
  7.         int left = 0;
  8.         int right = array.length-1;
  9.         int pivot = partiton(array,left,right);
  10.         if(pivot > left+1){
  11.             stack.push(left);
  12.             stack.push(pivot-1);
  13.         }
  14.         if(pivot < right -1){
  15.             stack.push(pivot+1);
  16.             stack.push(right);
  17.         }
  18.         while(!stack.isEmpty()){
  19.             right = stack.pop();
  20.             left = stack.pop();
  21.             pivot = partiton(array,left,right);
  22.             if(pivot>left+1){
  23.                 stack.push(left);
  24.                 stack.push(pivot-1);
  25.             }
  26.             if (pivot<right-1){
  27.                 stack.push(pivot+1);
  28.                 stack.push(right);
  29.             }
  30.         }
  31.     }
  32.     public static int partiton(int[] array,int start,int end){
  33.         int tmp = array[start];
  34.         while(start<end){
  35.             while(start<end && array[end] >=tmp){
  36.                 end--;
  37.             }
  38.             array[start] = array[end];
  39.             while (start<end && array[start] <= tmp){
  40.                 start++;
  41.             }
  42.             array[end] = array[start];
  43.         }
  44.         array[start] = tmp;
  45.         return start;
  46.     }
  48.     public static void main(String[] args) {
  49.         int[] array = {12,5,8,1,10,15};
  50.         quickSort(array);
  51.         System.out.println(Arrays.toString(array));
  52.     }
  53. }

归并排序 - 重点

知识铺垫 ： 二路合并

将两个有序表合并成一个有序表，称为二路归并。【简单说就是 将两个有序数组合并为一个有序数组，称为二路合并】

二路合并的代码如下

  1. import java.util.Arrays;
  3. public class MergeSort {
  5. /*
  6. * array1 已有序
  7. * array2 已有序
  8. * */
  9.     public static int[] mergeArrays(int[] array1,int[] array2){
  10.         if(array1 == null || array2 == null){
  11.             return array1 == null ? array2: array1;
  12.         }
  13.         int[] arr = new int[array1.length + array2.length];
  14.         int i = 0;// arr 的 遍历变量
  15.         int s1 = 0;//array1 的 遍历变量
  16.         int s2 = 0;//array2 的 遍历变量
  17.         while(s1 < array1.length && s2 < array2.length){
  18.             if(array1[s1] > array2[s2]){
  19.                 arr[i++] = array2[s2++];
  20. //                s2++;
  21. //                i++;
  22.             }else{
  23.                 arr[i++] = array1[s1++];
  24. //                s1++;
  25. //                i++;
  26.             }
  27.         }
  28.         // 循环结束，有一个数组的元素已经全部存入
  29.         // 接下来就是将另一个数组的元素放入 arr 中
  30.         while (s1 < array1.length){
  31.             arr[i++] = array1[s1++];
  32. //            i++;
  33. //            s1++;
  34.         }
  35.         while (s2 < array2.length){
  36.             arr[i++] = array2[s2++];
  37. //            i++;
  38. //            s2++;
  39.         }
  40.         return arr;
  41.     }
  43.     public static void main(String[] args) {
  44.         int[] array1 = {1,6,7,10};
  45.         int[] array2 = {2,3,4,9};
  46.         int[] mergeArray = mergeArrays(array1,array2);
  47.         System.out.println(Arrays.toString(mergeArray));
  48.     }
  49. }

归并排序 - 原理

归并排序（MERGE - SORT）是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

难点1 - 如何将一个数组拆分成一个个单独数组【每个数组里只包含一个元素】。

难点2 - 合并

归并排序的程序框架

  1. public class MergeSort {
  2.     // 归并排序的调用“接口”
  3.     public static int[] mergeSort(int[] array){
  4.         if(array == null){
  5.             return array;
  6.         }
  7.         mergeSortFunc(array,0,array.length-1);
  8.         return array;
  9.     }
  10.     // 归并排序实现
  11.     private static void mergeSortFunc(int[] array,int low,int high){
  12.         if(low >= high){
  13.             return;
  14.         }
  15.         // 递归分解
  16. //       int mid = (high + low) >>> 1
  17.         int mid = low + ((high - low) >>> 1);
  18.         mergeSortFunc(array,low,mid);// 左边
  19.         mergeSortFunc(array,mid+1,high);// 右边
  21.          // 合并
  22.         merge(array,low,mid,high);
  23.     }
  25.     private static void merge(int[] array,int low,int mid,int high){
  27.     }
  28. }

合并程序的完善

其实这个并不难，跟我前面做的知识铺垫的思路是一样的。
需要注意的是：
1、我们的参数中 只有一个数组
2、数组 arr ，只是一个临时数组，用来存储 合并之后的结果。
3、在将 arr 数组 存储的结果，转移到 原本数组的时候，注意赋值的位置！

  1. private static void merge(int[] array,int low,int mid,int high){
  2.     // 获取 区间之内的元素个数，加一 是因为 零下标元素也算一个元素。
  3.         int[] arr = new int[high - low +1];
  4.         // 左边 区间 【你可以理解为 有序数组 array1的起始与结束下标位置】
  5.         int start1 = low;
  6.         int end1 = mid;
  7.         // 右边 区间【你可以理解为 有序数组 array2的起始与结束下标位置】
  8.         int start2 = mid+1;
  9.         int end2 = high;
  10.         int i = 0;
  11.         while (start1 <= end1 && start2 <= end2){
  12.             if(array[start1] > array[start2]){
  13.                 arr[i++] = array[start2++];
  14.             }else{
  15.                 arr[i++] = array[start1++];
  16.             }
  17.         }
  18.         while(start1 <= end1){
  19.             arr[i++] = array[start1++];
  20.         }
  21.         while(start2 <= end2){
  22.             arr[i++] = array[start2++];
  23.         }
  24.         // 将 arr 存储的 合并数据，转换到原本数组上。
  25.         // 注意 array 数组中括号的下标的位置。
  26.         for (int j = 0; j < arr.length; j++) {
  27.             array[low++] = arr[j];
  28.         }
  29.     }
附图

归并排序 - 总程序

  1. import java.util.Arrays;
  3. public class MergeSort {
  4.     /*
  5.     * 时间复杂度：N * log2 N
  6.     * 空间复杂丢：O(N)
  7.     * 稳定性：稳定
  8.     * */
  9.     public static int[] mergeSort(int[] array){
  10.         if(array == null){
  11.             return array;
  12.         }
  13.         mergeSortFunc(array,0,array.length-1);
  14.         return array;
  15.     }
  16.     private static void mergeSortFunc(int[] array,int low,int high){
  17.         if(low >= high){
  18.             return;
  19.         }
  20. //       int mid = (high + low) >>> 1
  21.         int mid = low + ((high - low) >>> 1);
  22.         mergeSortFunc(array,low,mid);// 左边
  23.         mergeSortFunc(array,mid+1,high);// 右边
  24.         merge(array,low,mid,high);
  25.     }
  27.     private static void merge(int[] array,int low,int mid,int high){
  28.         int[] arr = new int[high - low +1];
  29.         int start1 = low;
  30.         int end1 = mid;
  31.         int start2 = mid+1;
  32.         int end2 = high;
  33.         int i = 0;
  34.         while (start1 <= end1 && start2 <= end2){
  35.             if(array[start1] > array[start2]){
  36.                 arr[i++] = array[start2++];
  37.             }else{
  38.                 arr[i++] = array[start1++];
  39.             }
  40.         }
  41.         while(start1 <= end1){
  42.             arr[i++] = array[start1++];
  43.         }
  44.         while(start2 <= end2){
  45.             arr[i++] = array[start2++];
  46.         }
  47.         for (int j = 0; j < arr.length; j++) {
  48.             array[low++] = arr[j];
  49.         }
  50.     }
  51.     
  52.     public static void main(String[] args) {
  53.         int[] array = {1,6,7,10,2,3,4,9};
  54.         mergeSort(array);
  55.         System.out.println(Arrays.toString(array));
  56.     }
  57. }

归并排序 - 时间与空间复杂度分析、稳定性

归并排序 - 非递归实现

代码如下

  1. import java.util.Arrays;
  3. public class MergeSortNonRecursion {
  4.     public static void mergeSort(int[] array){
  5.         //归并排序非递归实现
  6.         int groupNum = 1;// 每组的数据个数
  7.         while(groupNum < array.length){
  8.             // 无论数组含有几个元素， 数组每次都需要从下标 0位置，开始遍历。
  9.             for(int i = 0;i<array.length;i+= groupNum * 2){
  10.                 int low = i;
  11.                 int mid = low + groupNum -1;
  13.                 // 防止越界【每组的元素个数，超过了数组的长度】
  14.                 if(mid >= array.length){
  15.                     mid = array.length-1;
  16.                 }
  17.                 int high = mid + groupNum;
  19.                 // 防止越界【超过了数组的长度】
  20.                 if(high >= array.length){
  21.                     high = array.length-1;
  22.                 }
  23.                 merge(array,low,mid,high);
  24.             }
  25.             groupNum *= 2;//每组的元素个数扩大到原先的两倍。
  26.         }
  27.     }
  28.     public static void merge(int[] array,int low,int mid,int high){
  29.     // high 与 mid 相遇，说明 此时数组分组只有一组，也就说没有另一组的数组与其合并
  30.     // 即数组已经有序了，程序不用再往下走。
  31.          if(high == mid){
  32.             return;
  33.         }
  34.         int[] arr = new int[high -low + 1];
  35.         int start1 = low;
  36.         int end1 = mid;
  37.         int start2 = mid+1;
  38.         int end2 = high;
  39.         int i = 0;
  40.         while(start1 <= end1 && start2 <= end2){
  41.             if(array[start1]>array[start2]){
  42.                 arr[i++] = array[start2++];
  43.             }else{
  44.                 arr[i++] = array[start1++];
  45.             }
  46.         }
  47.         while (start1 <= end1){
  48.             arr[i++] = array[start1++];
  49.         }
  50.         while(start2 <= end2){
  51.             arr[i++] = array[start2++];
  52.         }
  53.         for (int j = 0; j < arr.length; j++) {
  54.             array[low++] = arr[j];
  55.         }
  56.     }
  58.     public static void main(String[] args) {
  59.         int[] array = {12,5,8,7,3,4,1,10};
  60.         mergeSort(array);
  61.         System.out.println(Arrays.toString(array));
  62.     }
  63. }

海量数据的排序问题

外部排序：排序过程需要在磁盘等外部存储进行的排序
【内部排序：排序过程需要在 内存上进行排序】
前提：内存只有 1G，需要排序的数据有 100G
因为内存中无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序。
1、先把文件切分成 200 份，每个512M

2、分别对 512M 的数据量 进行排序，因为 内存已经被分割了，512M < 1G 内存放得下。所以任何排序方式都可以，
3、进行 200 路归并，同时对 200 份有序文件做归并过程，最终结果就有序了

小总结

目前，我们讲了八种排序：直接插入排序、希尔排序、直接选择排序，双向选择排序、冒泡排序，堆排序、快速排序，归并排序。
其中稳定的排序：插入排序，冒泡排序，归并排序，一共三种。
?
另外，堆排序、归并排序、快速排序的时间复杂度都是 N * log2 N。
如果，你想速度快，就用快排。
如果，你想稳定，就用归并。
如果，你想空间复杂度低，就用堆排。

排序总结

排序方法最好（时间复杂度）平均（时间复杂度）最坏（时间复杂度）空间复杂度稳定性
冒泡排序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 * log2 N)O(N * log2 N)O(N * log2 N)O(1)不稳定
快速排序O(N * log2 N)O(N * log2 N)O(N ^ 2)O(N)不稳定
归并排序O(N * log2 N)O(N * log2 N)O(N * log2 N)O(N)稳定

不常见的排序 - 不基于比较的排序（了解）

基数排序

它的思路：假设待排序的数据类型是 整形/十进制数，每个数据 分别按照 个，百，千，万的大小，放入拿出对应编号空间，其最终的结果就是有序的。
放入拿出的次数 取决于 这组数据中 最大值的位数。

代码如下

  1. import java.util.Arrays;
  3. public class RadixSort {
  4. //  基数排序功能 实际功能实现方法
  5.     private static void radixSortFunc(int[] array,int maxDigit){
  6.         int mode = 10 ; // 十进制
  7.         int divide = 1;// 将 数值上的每个数“分割”，方便获取数据的一个位上的值
  9.         // 每个数据从个位到最大值的最高位，按照其位上的大小 放出 拿出
  10.         for (int i = 0; i < maxDigit; i++,mode *= 10,divide *=10) {
  11.             // 考虑 负数的 情况，0~9 对应负数，10 ~ 19 对应正数
  12.             // 行 对应的是编号， 列 对应的存储的数据
  13.             int[][] counter = new int[mode*2][0];
  15.             for (int j = 0; j < array.length; j++) {
  16.                 int number = ((array[j] % mode)/divide) + mode; /*获取 数据对应 空间的编号 */
  17.                 counter[number] = arrayAppend(counter[number],array[j]);
  18.             }
  19.             int pos = 0;
  20.             for (int[] number:counter) {
  21.                 for (int val:number) {
  22.                     array[pos++] = val;
  23.                 }
  24.             }
  25.         }
  26.     }
  27.     // 添加 元素
  28.     private static int[] arrayAppend(int[] arr,int value){
  29.         arr = Arrays.copyOf(arr,arr.length+1);
  30.         arr[arr.length-1] = value;
  31.         return  arr;
  32.     }
  35.     // 基数排序 功能调用方法“窗口”
  36.     public static void radixSort(int[] array){
  37.         int maxNumLength = getNumLength(array);
  38.         radixSortFunc(array,maxNumLength);
  39.     }
  41.     
  42.     // 获取最大值的位数 - 功能“窗口”
  43.     private static int getNumLength(int[] array){
  44.         int maxVal = getMaxValue(array);
  45.         return getMaxDigit(maxVal);
  46.     }
  47.     
  48.     //获取最大值
  49.     private static int getMaxValue(int[] array){
  50.         int maxValue= array[0];
  51.         for (int value: array) {
  52.             if(value > maxValue){
  53.                 maxValue = value;
  54.             }
  55.         }
  56.         return maxValue;
  57.     }
  58.     
  59.     // 获取最大值的位数 - 执行
  60.     private static int getMaxDigit(int num){
  61.         if(num == 0){
  62.             return 0;
  63.         }
  64.         int len = 0;
  65.         while(num > 0){
  66.             len++;
  67.             num /= 10;
  68.         }
  69.         return len;
  70.     }
  72.        // 程序入口
  73.     public static void main(String[] args) {
  74.         int[] array = {124,366,170,52,200,78,468};
  75.         radixSort(array);
  76.         System.out.println(Arrays.toString(array));
  77.     }
  78. }

捅排序

计数排序

在使用 计数排序时，需注意以下几点：
1、确定基数排序的大小
2、这个计数排序 适用的范围【假设数据中最小值 10000，最大 12000，那么，我们的计数数组容量只需要2001（0 下标也算入） 就够了。不需要创建 12000容量，避免空间浪费】
计数数组 计数也简单，用元素值减去 10000（最小值） 就行了
3、必须找到数据中的最大值 和 最小值，锁定计数数组的长度：max - min + 1
4、 拿出数据的时候，记得将减去的 最小值 加上，再进行对原始数组的覆写。

代码如下

  1. import java.util.Arrays;
  2. /*
  3. * 时间复杂度：O(N)
  4. * 空间复杂度: O(M) : M 表示 当前数据的范围
  5. * 【空间 换 时间】
  6. * 稳定性： 当前代码是不稳定，本质是稳定的。
  7. * 在借助一个 数组来存储 每个元素排序后，最后出现的位置，
  8. * 拿出来的时候，就能确定位置。致使该排序 稳定。 - 见附图
  9. * */
  10. public class CountingSort {
  11.     public static void countingSort(int[] array){
  12.         int maxVal = array[0];
  13.         int minVal = array[0];
  14.         for (int i = 0; i < array.length; i++) {
  15.             if (array[i] > maxVal){
  16.                 maxVal = array[i];
  17.             }
  18.             if(array[i] < minVal){
  19.                 minVal =array[i];
  20.             }
  21.         }
  22.         // 当循环结束，获得了 数据的最大值 和 最小值
  23.         // 可以确定计数数组的容量
  24.         int[] count = new int[maxVal -minVal +1];
  25.         for (int i = 0; i < array.length; i++) {
  26.           // 提高空间利用率
  27.             count[ array[i] - minVal ]++;
  28.         }
  29.         // 此时，计数数组 已经把array数组当中，每个元素的出现次数统计好了
  30.         // 接下来，只需要遍历计数数组，把 数据 覆写 到 array当中。
  31.         int indexArray = 0; // 用于遍历 array数组，标记 覆写的位置。
  32.         for (int i = 0; i < count.length; i++) {
  33.             while(count[i]>0){
  34.                 // 这里一定要加上减去minVal，因为 下标 i 不一定 在 array 数组中出现过。
  35.                 array[indexArray++] = i + minVal;// 拿出来的时候，记得将减去的值加上
  36.                 // indexArray++;
  37.                 count[i]--;
  38.             }
  39.         }
  40.     }
  42.     public static void main(String[] args) {
  43.         int[] array = {5,0,2,3,4,5,2};
  44.         countingSort(array);
  45.         System.out.println(Arrays.toString(array));
  46.     }
  47. }

附图 - 是目前的计数排序稳定

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

原文链接 : https://lebron.blog.csdn.net/article/details/123160730

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

Java数据结构与算法排序算法开发语言java细节

相关文章

    查看更多

    热门标签

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

    最新文章

    更多

    目录

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