高级排序
在Java数据结构和算法（三）——冒泡、选择、插入排序算法中我们介绍了三种简单的排序算法，它们的时间复杂
度大O表示法都是O(N2)，如果数据量少，我们还能忍受，但是数据量大，那么这三种简单的排序所需要的时间则
是我们所不能接受的。接着我们在讲解递归 的时候，介绍了归并排序，归并排序需要O(NlogN)，这比简单排序要
快了很多，但是归并排序有个缺点，它需要的空间是原始数组空间的两倍，当我们需要排序的数据占据了整个内存
的一半以上的空间，那么是不能使用归并排序的。
本篇博客将介绍几种高级的排序算法：希尔排序和快速排序。
1希尔排序
希尔排序是基于直接插入排序的，它在直接插入排序中增加了一个新特性，大大的提高了插入排序的执行效率。所
以在讲解希尔排序之前，我们先回顾一下直接插入排序。
1.1直接插入排序
直接插入排序基本思想是每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素
为止。
实现代码为：
public static int[] InsertSort(int[] array){
int j;
//从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
for(int i = 1 ; i < array.length ; i++){
int tmp = array[i];//记录要插入的数据
j = i;
while(j > 0 && tmp < array[j-1]){
//从已经排序的序列最右边的开始比较，找到比其小的数
array[j] = array[j-1];
//向后挪动
j--;
}
array[j] = tmp;//存在比其小的数，插入
}
return array;
}
我们可以分析一下这个直接插入排序，首先我们将需要插入的数放在一个临时变量中，这也是一个标记符，标记符
左边的数是已经排好序的，标记符右边的数是需要排序的。接着将标记的数和左边排好序的数进行比较，假如比目
标数大则将左边排好序的数向右边移动一位，直到找到比其小的位置进行插入。
这里就存在一个效率问题了，如果一个很小的数在很靠近右边的位置，比如上图右边待排序的数据 1 ，那么想
让这个很小的数 1 插入到左边排好序的位置，那么左边排好序的数据项都必须向右移动一位，这个步骤就是将近执
行了N次复制，虽然不是每个数据项都必须移动N个位置，但是每个数据项平均移动了N/2次，总共就是N2/2，因
此插入排序的效率是O(N2)。
那么如果以某种方式不必一个一个移动中间所有的数据项，就能把较小的数据项移动到左边，那么这个算法的执行效率会有很大的改进。
1.2希尔排序
希尔排序应运而生了，希尔排序通过加大插入排序中元素的间隔，并在这些有间隔的元素中进行插入排序，从而使数据项能够大跨度的移动。当这些数据项排过一趟序后，希尔排序算法减小数据项的间隔再进行排序，依次进行下去，最后间隔为1时，就是我们上面说的简单的直接插入排序。
1.3knuth间隔序列的希尔排序算法实现
//希尔排序 knuth 间隔序列 3h+1
public static void shellKnuthSort(int[] array){
System.out.println("原数组为"+ Arrays.toString(array));
int step = 1 ;
int len = array.length;
while(step <= len/3){
step = step*3 + 1;//1,4,13,40......
}
while(step > 0){
//分别对每个增量间隔进行排序
for(int i = step ; i < len ; i++){
int temp = array[i];
int j = i;
while(j > step-1 && temp <= array[j-step]){
array[j] = array[j-step];
j -= step;
}
array[j] = temp;
}//end for
System.out.println("间隔为"+step+"的排序结果为"+Arrays.toString(array));
step = (step-1)/3;
}//end while(step>0)
System.out.println("最终排序："+Arrays.toString(array));
}
测试用例：
public static void main(String[] args) {
int[] array = {4,2,8,9,5,7,6,1,3,10};
shellKnuthSort(array);
}
测试结果：
原数组为[4, 2, 8, 9, 5, 7, 6, 1, 3, 10]
间隔为4的排序结果为[3, 2, 6, 1, 4, 7, 8, 9, 5, 10]
间隔为1的排序结果为[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
最终排序：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
1.4间隔为2h的希尔排序
//希尔排序 间隔序列2h
public static void shellSort(int[] array){
System.out.println("原数组为"+Arrays.toString(array));
int step;
int len = array.length;
for(step = len/2 ;step > 0 ; step /= 2){
//分别对每个增量间隔进行排序
for(int i = step ; i < array.length ; i++){
int j = i;
int temp = array[j];
if(array[j] < array[j-step]){
while(j-step >=0 && temp < array[j-step]){
array[j] = array[j-step];
j -= step;
}
array[j] = temp;
}
}
System.out.println("间隔为"+step+"的排序结果为"+Arrays.toString(array));
}
}
测试结果：
原数组为[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
间隔为5的排序结果为[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
间隔为2的排序结果为[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
间隔为1的排序结果为[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
2快速排序
快速排序是对冒泡排序的一种改进，由C. A. R. Hoare在1962年提出的一种划分交换排序，采用的是分治策略（一
般与递归结合使用），以减少排序过程中的比较次数。
2.1快速排序的基本思路
- 先通过第一趟排序，将数组原地划分为两部分，其中一部分的所有数据都小于另一部分的所有数据。原数组被
划分为2份 - 通过递归的处理，再对原数组分割的两部分分别划分为两部分，同样是使得其中一部分的所有数据都小于
另一部分的所有数据。这个时候原数组被划分为了4份 - 就1,2被划分后的最小单元子数组来看，它们仍然是无序的，但是！ 它们所组成的原数组却逐渐向有序的
方向前进。 - 这样不断划分到最后，数组就被划分为多个由一个元素或多个相同元素组成的单元，这样数组就有序了。
2.2快速排序的算法实现
我们用[6,1,2,7,9,3,4,5,10,8]表示的是一个无序数组，选取第一个元素 6 作为基准元素。左游标是 i 哨兵，右游标是 j 哨兵。然后左游标向
右移动，右游标向左移动，它们遵循的规则如下：
- 左游标向右扫描，跨过所有小于基准元素的数组元素, 直到遇到一个大于或等于基准元素的数组元素，在那个位置停下。
- 右游标向左扫描，跨过所有大于基准元素的数组元素, 直到遇到一个小于或等于基准元素的数组元素，在那个位置停下。
第一步：哨兵 j 先开始出动。因为此处设置的基准数是最左边的数，所以需要让哨兵 j 先开始出动，哨兵 j 一
步一步的向左挪动，直到找到一个小于 6 的元素停下来。接下来，哨兵 i 再一步一步的向右挪动，直到找到一个大
于 6 的元素停下来。最后哨兵 i 停在了数字 7 面前，哨兵 j 停在了数字 5 面前。
交换i和j的值，即交换5和7
此时数组为[6,1,2,5,9,3,4,7,10,8], i哨兵指向5的位置，j哨兵指向7的位置。
到此，第一次交换结束，接着哨兵 j 继续向左移动，它发现 4 比基准数 6 要小，那么在数字4面前停下来。哨兵 i
也接着向右移动，然后在数字 9 面前停下来，然后哨兵 i 和 哨兵 j 再次进行交换。
此时数组为[6,1,2,5,4,3,9,7,10,8], i哨兵指向4的位置，j哨兵指向9的位置。
第二次交换结束，哨兵 j 继续向左移动，然后在数字 3 面前停下来；哨兵 i 继续向右移动，但是它发现和哨兵 j 相
遇了。那么此时说明探测结束，将数字 3 和基准数字 6 进行交换.
此时数组为[3,1,2,5,4,6,9,7,10,8], i哨兵和j哨兵指向6的位置。
到此，第一次探测真正结束，此时已基准点 6 为分界线，6 左边的数组元素都小于等于6,6右边的数组元素都大于
等于6。
左边序列为【3,1,2,5,4】,右边序列为【9,7,10,8】。接着对于左边序列而言，以数字 3 为基准元素，重复上面
的探测操作，探测完毕之后的序列为【2,1,3,5,4】；对于右边序列而言，以数字 9 位基准元素，也重复上面的探测
操作。然后一步一步的划分，最后排序完全结束。
通过这一步一步的分解，我们发现快速排序的每一轮操作就是将基准数字归位，知道所有的数都归位完成，排序就结束了。
2.3快速排序完整代码
public class QuickSort {
//数组array中下标为i和j位置的元素进行交换
private static void swap(int[] array , int i , int j){
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
private static void recQuickSort(int[] array,int left,int right){
if(right <= left){
return;//终止递归
}else{
int partition = partitionIt(array,left,right);
recQuickSort(array,left,partition-1);// 对上一轮排序(切分)时，基准元素左边的子数组进行递归
recQuickSort(array,partition+1,right);// 对上一轮排序(切分)时，基准元素右边的子数组进行递归
}
}
private static int partitionIt(int[] array,int left,int right) {
//为什么 j加一个1，而i没有加1,是因为下面的循环判断是从‐‐j和++i开始的.
//而基准元素选的array[left],即第一个元素，所以左游标从第二个元素开始比较
int i = left;
int j = right + 1;
int pivot = array[left];// pivot 为选取的基准元素（头元素）
while (true) {
while (i < right && array[++i] < pivot) {
}
while (j > 0 && array[--j] >pivot){
}
if (i >= j) {// 左右游标相遇时候停止， 所以跳出外部while循环
break;
} else {
swap(array, i, j);// 左右游标未相遇时停止, 交换各自所指元素，循环继续
}
}
swap(array, left, j);//基准元素和游标相遇时所指元素交换，为最后一次交换
return j;// 一趟排序完成， 返回基准元素位置(注意这里基准元素已经交换位置了)
}
public static void sort(int[] array){
recQuickSort(array, 0, array.length-1);
}
//测试
public static void main(String[] args) {
int[] array = {9,9,8,7,6,5,4,3,2,1};
sort(array);
for(int i : array){
System.out.print(i+" ");
}
}
}
2.4优化分析
假设我们是对一个逆序数组进行排序，选取第一个元素作为基准点，即最大的元素是基准点，那么第一次循环，左
游标要执行到最右边，而右游标执行一次，然后两者进行交换。这也会划分成很多的子数组。
那么怎么解决呢？理想状态下，应该选择被排序数组的中值数据作为基准，也就是说一半的数大于基准数，一
般的数小于基准数，这样会使得数组被划分为两个大小相等的子数组，对快速排序来说，拥有两个大小相等的子数组是最优的情况。
三项取中划分
为了找到一个数组中的中值数据，一般是取数组中第一个、中间的、最后一个，选择这三个数中位于中间的数。
//取数组下标第一个数、中间的数、最后一个数的中间值
private static int medianOf3(int[] array,int left,int right){
int center = (right-left)/2+left;
if(array[left] > array[right]){ //得到 array[left] < array[right]
swap(array, left, right);
}
if(array[center] > array[right]){ //得到 array[left] array[center] < array[right]
swap(array, center, right);
}
if(array[center] > array[left]){ //得到 array[center] < array[left] < array[right]
swap(array, center, left);
}
return array[left]; //array[left]的值已经被换成三数中的中位数， 将其返回
}
private static int partitionIt(int[] array,int left,int right){
//为什么 j加一个1，而i没有加1,是因为下面的循环判断是从‐‐j和++i开始的.
//而基准元素选的array[left],即第一个元素，所以左游标从第二个元素开始比较
int i = left;
int j = right+1;
int pivot = array[left];// pivot 为选取的基准元素（头元素）
int size = right - left + 1;
if(size >= 3){
pivot = medianOf3(array, left, right); //数组范围大于3，基准元素选择中间值。
}
while(true){
while(i<right && array[++i] < pivot){}
while(j > 0 && array[--j] > pivot){}
if(i >= j){// 左右游标相遇时候停止， 所以跳出外部while循环
break;
}else{
swap(array, i, j);// 左右游标未相遇时停止, 交换各自所指元素，循环继续
}
}
swap(array, left, j);//基准元素和游标相遇时所指元素交换，为最后一次交换
return j;// 一趟排序完成， 返回基准元素位置(注意这里基准元素已经交换位置了)
}
处理小划分
如果使用三数据取中划分方法，则必须遵循快速排序算法不能执行三个或者少于三个的数据，如果大量的子数
组都小于3个，那么使用快速排序是比较耗时的。联想到前面我们讲过简单的排序（冒泡、选择、插入）。
当数组长度小于M的时候（high-low <= M）， 不进行快排，而进行插入排序。转换参数M的最佳值和系统是
相关的，一般来说， 5到15间的任意值在多数情况下都能令人满意。
//插入排序
private static void insertSort(int[] array){
for(int i = 1 ; i < array.length ; i++){
int temp = array[i];
int j = i;
while(j > 0 && array[j-1] > temp){
array[j] = array[j-1];
j--;
}
array[j] = temp;
}
}
联系作者
微信公众号
xiaomingxiaola
（BossLiu）
QQ群
58726094
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 384276224@qq.com
