devbox
Li_阴宅
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构之八大排序（下）

作者：Li_阴宅 | 2024-08-04 08:07:21

赞

踩

数据结构之八大排序（下）

找往期文章包括但不限于本期文章中不懂的知识点：

个人主页：我要学编程(ಥ_ಥ)-CSDN博客

所属专栏：数据结构（Java版） 

数据结构之八大排序（上）-CSDN博客 

上面博客讲述了另外六中排序算法。

目录

快速排序 

归并排序 

快速排序 

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

总共有三个实现版本：

1、Hoare法版：

思路：取key作为基准，右边找比基准小的，左边找比基准大的，进行交换，一直重复上述步骤，直至两者相遇，相遇后再交换相遇值和基准值，接着就以相遇的值为界，划分为左右两边，继续重复上述步骤。

代码实现： 

  1.     public static void quickSort(int[] array) {
  2.         quick_sort(array, 0, array.length-1);
  3.     }
  4.  
  5.     private static void quick_sort(int[] array, int start, int end) {
  6.         // 限制条件
  7.         if (start >= end) {
  8.             return;
  9.         }
  10.         // 分区并进行交换
  11.         int div = partion(array, start, end);
  12.         // 递归左子树
  13.         quick_sort(array, start, div-1);
  14.         // 递归右子树
  15.         quick_sort(array, div+1, end);
  16.     }
  17.  
  18.     private static int partion(int[] array, int left, int right) {
  19.         int key = array[left]; // 指定基准
  20.         int keyIndex = left; // 记录基准的下标，用于交换
  21.         while (left < right) {
  22.             // 右边找到比基准小的
  23.             while (left < right && array[right] >= key) {
  24.                 right--;
  25.             }
  26.             // 左边找到比基准大的
  27.             while (left < right && array[left] <= key) {
  28.                 left++;
  29.             }
  30.             swap(array, left, right);
  31.         }
  32.         // 相遇后交换
  33.         swap(array, left, keyIndex);
  34.         // 返回相遇点
  35.         return left;
  36.     }

注意： 

1、限制条件。我们在递归的时候，如果只有一个元素时， 说明此时一定是有序的，就不需要再继续进行递归了。即 start == end。如果在递归过程中 start > end了说明也不需要交换了。

2、在左右找比基准大或者小时，一定要先找右边，再找左边。否则达不到我们的目的（左边全小于边界值，右边全大于边界值）。如下图所示：

这样再去交换相遇值和基准值就不能实现相遇值（边界值）全大于其左边，小于其右边。

3、相遇交换基准值和相遇值时，一定要先把基准值对应的下标储存起来。

4、时间复杂度：最坏情况：O(N^2)：当数据已经有序的情况下；最好情况：O(N*logN)：数据刚好可以组成满二叉树，每次都是N个数据，递归了logN层，即N*logN。

5、空间复杂度：最坏情况：O(N)：当数据已经有序的情况下；最好情况：O(logN)：数据刚好可以组成满二叉树，递归了logN层。

6、稳定性：不稳定。

2、挖坑法版： 

思路：同样是取左边的第一个数据为 key，形成一个坑位，在右边找到比key小的放到左边的坑位中（这就意味着右边形成了坑位），再从左边找到比 key 大的放到坑位中。一直重复上面的操作直至两者相遇，就把 key 放到坑位中，那么这个坑位（相遇点）就是划分标准，然后我们继续从两棵子树开始上述操作。

代码实现：

  1.     private static int partion(int[] array, int left, int right) {
  2.         int key = array[left];
  3.         while (left < right) {
  4.             // 右边找小于坑的值
  5.             while (left < right && array[right] >= key) {
  6.                 right--;
  7.             }
  8.             // 开始填坑
  9.             array[left] = array[right];
  10.             // 左边找大于坑的值
  11.             while (left < right && array[left] <= key) {
  12.                 left++;
  13.             }
  14.             // 继续填坑
  15.             array[right] = array[left];
  16.         }
  17.         array[left] = key;
  18.         return left;
  19.     }

注意：整体代码和上述代码一致，只是改变了partion的代码部分，也就是划分标准改变了。 

3、前后指针法版：

思路：定义一个指针 prev 和一个指针 cur，分别指向 start 和 start+1 的位置，开始遍历数组，如果 cur指向的数据小于 left 指向的数据，并且prev指向的下一个数据不是 cur 指向的数据，那么就交换两者的值，并同时往后走；如果 cur指向的数据大于 left 指向的数据，就让 cur 继续往后走，直至cur 遇到end就停止。并交换prev和left的值。

代码实现：

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

上面遇到了是单分支的树的情况，就导致快速排序变得类似冒泡排序一样了。针对上述情况，我们就要来优化代码。

思路一：既然我们拿到的数组是单分支的情况，那么我们只要把这棵树的中间节点（就是类似这组数据的中位数）的给找出来，然后再交换0位置的值即可，这就铸造了最开始的情况（图中数据所示）。

找根节点这里用到的是：三数取中法。即得到 left 、left+right 和 right 的中位数。

代码实现：

  1.     // 三数取中法找到key，使单分支的树接近满二叉树
  2.     private static int getIndex(int[] array, int left, int right) {
  3.         int mid = (left+right) / 2;
  4.         if (array[left] < array[right]) {
  5.             if (array[mid] < array[left]) {
  6.                 return left;
  7.             } else if (array[mid] > array[right]){
  8.                 return right;
  9.             } else {
  10.                 return mid;
  11.             }
  12.         } else {
  13.             if (array[mid] < array[right]) {
  14.                 return right;
  15.             } else if (array[mid] > array[left]) {
  16.                 return left;
  17.             } else {
  18.                 return mid;
  19.             }
  20.         }
  21.     }

注意：这里得到的只是一个近似值，不一定是准确的中位数。

思路二：二叉树的节点主要是集中在接近叶子结点的层数。既然如此，那直接把接近叶子节点的层树的节点全部采用直接插入排序即可。

直接插入排序部分的代码实现：

  1.     private static void insertSortRange(int[] array, int start, int end) {
  2.         for (int i = start+1; i <= end; i++) {
  3.             int tmp = array[i];
  4.             int j = i-1;
  5.             while (j >= 0) {
  6.                 if (array[j] > tmp) {
  7.                     array[j+1] = array[j];
  8.                     j--;
  9.                 } else {
  10.                     break;
  11.                 }
  12.             }
  13.             array[j+1] = tmp;
  14.         }
  15.     }

核心代码部分：

  1. // 递归到接近叶子结点时，采用直接插入排序更有效
  2. if (end - start <= 7) { //这个数是随机取的，只要是接近叶子节点层树即可
  3.     insertSortRange(array, start, end);
  4.     return;
  5. }

前面都是递归实现的代码，下面我们就来学习使用迭代的方式实现快速排序：

  1.     private static void quickSortNor(int[] array, int start, int end) {
  2.         Stack<Integer> stack = new Stack<>();
  3.         stack.push(start);
  4.         stack.push(end);
  5.         while (!stack.isEmpty()) {
  6.             end = stack.pop();
  7.             start = stack.pop();
  8.             int div = partion(array, start, end);
  9.             // 判断是否区间中是否只剩下一个元素
  10.             if (div > start+1) {
  11.                 stack.push(start);
  12.                 stack.push(div-1);
  13.             }
  14.             if (div < end-1) {
  15.                 stack.push(div+1);
  16.                 stack.push(end);
  17.             }
  18.         }
  19.     }

 其实非递归也就是大体结构发生了变化，在核心代码部分还是并未发生变化（交换数据）。

总结：虽然快速排序在不优化的情况下，时间复杂度确实能够达到O(N^2)，但是我们平时都是说优化情况下的时间复杂度，即O(N*logN)。

归并排序 

归并排序 是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序核心步骤: 第一步分解数据，第二步分组进行合并。

思路：先将一组数据进行分解，分解成只有一组数据的时候，就可以开始合并了。

分解代码实现：

  1.     public static void mergeSort(int[] array) {
  2.         merge_sort(array, 0, array.length-1);
  3.     }
  4.  
  5.     private static void merge_sort(int[] array, int start, int end) {
  6.         // 限制条件
  7.         if (start >= end) {
  8.             return;
  9.         }
  10.         int mid = (start+end)/2;
  11.         // 分解
  12.         merge_sort(array, start, mid); // 左子树
  13.         merge_sort(array, mid+1, end); // 右子树
  14.         // 合并(类似合并两个有序数组)
  15.         merge(array, start, mid, end);
  16.     }

合并的思路：类似合并两个数组。

代码实现：

  1.     private static void merge(int[] array, int start, int mid, int end) {
  2.         int s1 = start;
  3.         int e1 = mid;
  4.         int s2 = mid+1;
  5.         int e2 = end;
  6.         // 申请一个新的数组来排序数据
  7.         int[] tmp = new int[end-start+1];
  8.         int k = 0;
  9.         while (s1 <= e1 && s2 <= e2) {
  10.             if (array[s1] < array[s2]) {
  11.                 tmp[k++] = array[s1++];
  12.             } else {
  13.                 tmp[k++] = array[s2++];
  14.             }
  15.         }
  16.         // 把剩下的数据全部放到数组中
  17.         while (s1 <= e1) {
  18.             tmp[k++] = array[s1++];
  19.         }
  20.         while (s2 <= e2) {
  21.             tmp[k++] = array[s2++];
  22.         }
  23.         // 把排好序的数组数据存放到原数组中
  24.         for (int i = start; i < start+k; i++) {
  25.             array[i] = tmp[i-start];
  26.         }
  27.         /*// 或者写成下面这样
  28.         for (int i = 0; i < k; i++) {
  29.             array[i+start] = tmp[i];
  30.         }*/
  31.     }

注意：

1、时间复杂度：O(N*logN)：每次进行分解的数据都是N个，总共会递归logN次，即N*logN。

2、空间复杂度：O(N)：最后在合并的时候，会申请一个大小为N的数组，即N。

3、稳定性：稳定。既可以实现为稳定的排序，也可以实现为不稳定的排序。

同样归并排序也有非递归的实现方式。

思路：类似希尔排序的逆过程。就是把数据一个一个分成一组，使其有序，再把数据两个两个分成一组使其有序。直至一组的个数等于数据长度时，这个数据就有序了。

代码实现：

  1.     public static void mergeSortNor(int[] array, int start, int end) {
  2.         // 把数据每次分为两组，进行比较-排序
  3.         int gap = 1;
  4.         while (gap < array.length) {
  5.             // 每次排序两组有效数据（因此i每次要跳过两组）
  6.             for (int i = 0; i < array.length; i+=gap*2) {
  7.                 int left = i;
  8.                 int mid = left+gap-1;
  9.                 int right = mid+gap;
  10.                 // 要确保，mid和right是有效的
  11.                 if (mid >= array.length) {
  12.                     mid = array.length-1;
  13.                 }
  14.                 if (right >= array.length) {
  15.                     right = array.length-1;
  16.                 }
  17.                 merge(array, left, mid, right);
  18.             }
  19.             gap *= 2;
  20.         }
  21.     }

由于归并排序需要O(N)的空间复杂度，因此其主要是解决外部排序的问题。 

外部排序：排序过程需要在磁盘等外部存储进行的排序

前提：内存只有 1G，需要排序的数据有 100G  

因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序： 1. 先把文件切分成 200 份，每个 512 M

2. 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以

3. 进行 2路归并，同时对 200 份有序文件做归并过程，最终结果就有序了。

注意：归并是下面这样处理的。

总结：常见的八大排序的情况：

这里的希尔排序可以是1.3-1.5，也可以是1-2。由于没有研究证明因此不能得出确切的答案。

好啦！本期 数据结构之八大排序（下）的学习之旅就到此结束啦！我们下一期再一起学习吧！

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号