详解面试手撕过的那些排序算法_面试 手撕排序算法

前言

只要去大厂面试，必定有一轮算法面试，而这一轮往往是阻碍程序员面试成功的关键。一个程序员的算法基本功是否扎实能够体现出自身的开发能力，下面我尽可能的把常用的排序算法讲清楚。

排序简介

排序（Sort）是指将数据元素按照指定关键字值的大小递增（或递减）次序重新排列。排序是线性表、二叉树等数据结构的一种基本操作，排序可以提高查找效率。本文讨论线性表的多种排序算法，包括插入排序、交换排序、选择排序和归并排序等算法，重点和难点是希尔排序、快速排序、堆排序和归并排序。每种算法都有自己的特点和巧妙之处，从中我们可以学到一些程序设计思想和技巧。

排序是以关键字为基准进行的。可指定一个数据元素的多个数据项分别作为关键字进行排序，显然排序结果将不同。例如，学号、姓名、成绩等数据项都可作为学生数据元素的关键字，按主关键字（如学号）排序，则结果唯一；按非主关键字（如姓名、成绩等）排序，则结果不唯一，成绩相同的学生次序仍然不能确定，谁在前谁在后都有可能。

插入算法

插入排序（Insertion Sort）算法思想：每趟将一个元素，按其关键字值的大小插入到它前面已排序的子序列中，依此重复，直到插入全部元素。

直接插入排序

1.直接插入排序算法
直接插入排序（Straight Insertion Sort）算法描述如下：
① 第 i（1≤i＜n）趟，线性序列为{a0，a1，…，ai-1，ai，…，an-1}，设前 i 个元素构成的子序列{a0，a1，…，ai-1}是排序的，将元素ai插入到子序列{a0，a1，…，ai-1}的适当位置，使插入后的子序列仍然是排序的，ai的插入位置由关键字比较大小确定。
② 重复执行①，n个元素共需n-1趟，每趟将一个元素ai插入到它前面的子序列中。

关键字序列{32，26，87，72，26*，17}的直接插入排序（升序）过程如下图所示，以“*”区别两个关键字相同元素，{}表示排序子序列。

数组的直接插入算法代码：

public class Insert_Sort {
    public static void main(String[] args) {
        int[] keys = {32, 26, 87, 72, 26, 17};
        insertSort(keys);
    }


    public static void insertSort(int[] keys)              //直接插入排序（升序）
    {
        System.out.println("直接插入排序（升序）");
        for (int i = 1; i < keys.length; i++)                  //n-1趟扫描，依次向前插入n-1个数
        {
            int temp = keys[i], j;                           //每趟将keys[i]插入到前面排序子序列中
            for (j = i - 1; j >= 0 && temp < keys[j]; j--) {
                keys[j + 1] = keys[j];  //将前面较大元素向后移动
            }        //升序

            keys[j + 1] = temp;                              //temp值到达插入位置
            System.out.print("第" + i + "趟 temp=" + temp + "\t");
            //输出排序中间结果，可省略
            System.out.println("\n" + "输出第" + i + "趟排序后的结果:");
            for (int key : keys) {
                System.out.print(key + "\t");
            }
            System.out.println();
        }

        System.out.println("\n" + "最终排序的结果:");
        for (int key : keys) {
            System.out.print(key + "\t");
        }
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

结果：

直接插入排序（升序）
第1趟 temp=26	
输出第1趟排序后的结果:
26	32	87	72	26	17	
第2趟 temp=87	
输出第2趟排序后的结果:
26	32	87	72	26	17	
第3趟 temp=72	
输出第3趟排序后的结果:
26	32	72	87	26	17	
第4趟 temp=26	
输出第4趟排序后的结果:
26	26	32	72	87	17	
第5趟 temp=17	
输出第5趟排序后的结果:
17	26	26	32	72	87	

最终排序的结果:
17	26	26	32	72	87	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.直接插入排序算法分析
衡量排序算法性能的重要指标是排序算法的时间复杂度和空间复杂度，排序算法的时间复杂度由算法执行中的元素比较次数和移动次数确定。

设数据序列有n个元素，直接插入排序算法执行n-1趟，每趟的比较次数和移动次数与数据序列的初始排列有关。以下3种情况分析直接插入排序算法的时间复杂度。

① 最好情况，一个排序的数据序列，如{1，2，3，4，5，6}，每趟元素ai与ai-1比较1次，移动2次（keys[i]到temp再返回）。直接插入排序算法比较次数为n-1，移动次数为2（n-1），时间复杂度为O（n）。
② 最坏情况，一个反序排列的数据序列，如{6，5，4，3，2，1}，第i趟插入元素ai比较i次，移动i+2次。直接插入排序算法比较次数C和移动次数M计算如下，时间复杂度为O（n2）。

③ 随机排列，一个随机排列的数据序列，第 i 趟插入元素 ai，等概率情况下，在子序列{a0，a1，…，ai-1}中查找ai平均比较（i+1）/2次，插入ai平均移动i/2次。直接插入排序算法比较次数C和移动次数M计算如下，时间复杂度为O（n2）。

总之，直接插入排序算法的时间效率在O（n）到O（n2）之间。数据序列的初始排列越接近有序，直接插入排序的时间效率越高。

直接插入排序算法中的temp占用一个存储单元，空间复杂度为O（1）。

3.排序算法的稳定性
排序算法的稳定性指关键字重复情况下的排序性能。设两个元素ai和aj（i<j），ai位于aj之前，它们的关键字相等ki=kj；排序后，如果ai仍在aj之前，则称该排序算法稳定（Stable）。

例如，对于上图（直接插入排序图），排序前后，关键字26与26*的次序没有改变。在直接插入排序算法中，关键字相等的元素会相遇进行比较，算法不改变它们的原有次序。因此，直接插入排序算法是稳定的。但是，如果直接插入排序算法中内层for语句写成以下，则改变了关键字相等元素的次序，将导致排序算法不稳定。

希尔排序
希尔排序（Shell Sort）是D.L.Shell在1959年提出的，又称为缩小增量排序（Diminishing Increment Sort），基本思想是分组的直接插入排序。

由直接插入排序算法分析可知，若数据序列越接近有序，则时间效率越高；再者，当n较小时，时间效率也较高。希尔排序正是基于这两点对直接插入排序算法进行改进。

希尔排序算法描述如下：

① 将一个数据序列分成若干组，每组由若干相隔一段距离（称为增量）的元素组成，在一个组内采用直接插入排序算法进行排序。
② 增量初值通常为数据序列长度的一半，以后每趟增量减半，最后值为1。随着增量逐渐减小，组数也减少，组内元素个数增加，数据序列接近有序。

关键字序列{38，55，65，97，27，76，27，13，19}的希尔排序（升序）过程如图9.2所示，序列长度为9，增量delta初值为4，序列分为4组进行直接插入排序，之后每趟增量以减半规律变化，经过3趟完成排序。

希尔排序算法实现如下：

希尔排序代码：

public class Shell_Sort {
    public static void main(String[] args) {
        int[] keys = {38, 55, 65, 97, 27, 76,27,13,19};
        shellSort(keys);
    }

    public static void shellSort(int[] keys)               //希尔排序（升序，增量减半）
    {
        System.out.println("排序前的数据:");
        for (int key : keys) {
            System.out.print(key + "\t");
        }
        System.out.println("\n"+"希尔排序（升序）");
        for (int delta = keys.length / 2; delta > 0; delta /= 2) {  //若干趟，控制增量每趟减半

            for (int i = delta; i < keys.length; i++) {         //一趟分若干组，每组直接插入排序

                int temp = keys[i], j;                       //keys[i]是当前待插入元素
                for (j = i - delta; j >= 0 && temp < keys[j]; j -= delta) { //组内直接插入排序（升序），寻找插入位置

                    keys[j + delta] = keys[j];//每组元素相距delta远
                }
                keys[j + delta] = temp;                      //插入元素
            }
            System.out.print("delta=" + delta + "  ");

            for (int key : keys) {
                System.out.print(key + "\t");
            }
            System.out.println();

        }
        System.out.println("\n" + "最终排序的结果:");
        for (int key : keys) {
            System.out.print(key + "\t");
        }
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

结果：

排序前的数据:
38	55	65	97	27	76	27	13	19	
希尔排序（升序）
delta=4  19	55	27	13	27	76	65	97	38	
delta=2  19	13	27	55	27	76	38	97	65	
delta=1  13	19	27	27	38	55	65	76	97	

最终排序的结果:
13	19	27	27	38	55	65	76	97	
1
2
3
4
5
6
7
8
9

希尔排序算法共有三重循环：
① 最外层循环for语句以增量delta变化控制进行若干趟扫描，delta初值为序列长度n/2，以后每趟减半，直至1。
② 中间循环for语句进行一趟扫描，序列分为delta组，每组由相距delta远的n/delta个元素组成，每组元素分别进行直接插入排序。
③ 最内层循环for语句进行一组直接插入排序，将一个元素keys[i]插入到其所在组前面的排序子序列中。

希尔排序算法增量的变化规律有多种方案。上述增量减半是一种可行方案。一旦确定增量的变化规律，则一个数据序列的排序趟数就确定了。初始当增量较大时，一个元素与较远的另一个元素进行比较，移动距离较远；当增量逐渐减小时，元素比较和移动距离较近，数据序列则接近有序。最后一次，再与相邻位置元素比较，决定排序的最终位置。

希尔排序算法的时间复杂度分析比较复杂，实际所需的时间取决于具体的增量序列。希尔排序算法的空间复杂度为O（1）。

希尔排序算法在比较过程中，会错过关键字相等元素的比较，如上面希尔排序图中的第1趟，将27*插入到前面的子序列中，则跳过关键字相等元素27，两者没有机会比较，算法不能控制稳定。因此，希尔排序算法不稳定。

交换排序

基于交换的排序算法有两种：冒泡排序和快速排序。

冒泡排序

1.冒泡排序算法
冒泡排序（Bubble Sort）算法描述：比较相邻两个元素大小，如果反序，则交换。若按升序排序，每趟将数据序列中的最大元素交换到最后位置，就像气泡从水里冒出一样。

关键字序列{32，26，87，72，26*，17}的冒泡排序（升序）过程如下图所示，{}表示排序子序列。

冒泡排序算法实现如下，两重循环，外层for循环控制最多n-1趟扫描，内层for循环进行一趟扫描的比较和交换。

public class Bubble_Sort {
    public static void main(String[] args) {
        int[] keys = {32, 26, 87, 72, 26, 17};
        System.out.println("排序前的数据:");
        for (int key : keys) {
            System.out.print(key + "\t");
        }
        bubbleSort(keys);
    }

    // 冒泡排序
    private static void swap(int[] keys, int i, int j)     //交换keys[i]与keys[j]元素，i、j范围由调用者控制
    {
        int temp = keys[j];
        keys[j] = keys[i];
        keys[i] = temp;
    }

    public static void bubbleSort(int[] keys)              //冒泡排序（升序）
    {
        bubbleSort(keys, true);
    }

    public static void bubbleSort(int[] keys, boolean asc) //冒泡排序，asc取值true（升序）、false（降序）
    {

        System.out.println();
        System.out.println("冒泡排序（" + (asc ? "升" : "降") + "序）");
        boolean exchange = true;                             //是否交换的标记
        for (int i = 1; i < keys.length && exchange; i++)      //有交换时再进行下一趟，最多n-1趟
        {
            exchange = false;                                //假定元素未交换
            for (int j = 0; j < keys.length - i; j++)            //一趟比较、交换
                if (asc ? keys[j] > keys[j + 1] : keys[j] < keys[j + 1])//相邻元素比较，若反序，则交换
                {
                    swap(keys, j, j + 1);
                    exchange = true;                         //有交换
                }
            System.out.print("第" + i + "趟，下标0～" + (keys.length - i) + "，");

            for (int key : keys) {
                System.out.print(key + "\t");
            }
            System.out.println();
        }

        System.out.println("最终排序的结果:");
        for (int key : keys) {
            System.out.print(key + "\t");
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

结果：

排序前的数据:
32	26	87	72	26	17	
冒泡排序（升序）
第1趟，下标0～5，26	32	72	26	17	87	
第2趟，下标0～4，26	32	26	17	72	87	
第3趟，下标0～3，26	26	17	32	72	87	
第4趟，下标0～2，26	17	26	32	72	87	
第5趟，下标0～1，17	26	26	32	72	87	
最终排序的结果:
17	26	26	32	72	87	
1
2
3
4
5
6
7
8
9
10

① 其中，布尔变量exchange用做本趟扫描是否交换的标记。如果一趟扫描没有数据交换，则排序完成，不必进行下一趟。例如，下图所示关键字序列的冒泡排序过程少于n-1趟。

② 冒泡排序算法是如何保证排序算法的稳定性的？如果冒泡排序算法中判断元素大小的条件语句写成如下，执行结果将会怎样？

2.冒泡排序算法分析

冒泡排序算法分析如下：
① 最好情况，数据序列排序，只需一趟扫描，比较n次，没有数据移动，时间复杂度为O（n）。
② 最坏情况，数据序列随机排列和反序排列，需要n-1趟扫描，比较次数和移动次数都是O（n2），时间复杂度为O（n2）。

总之，数据序列越接近有序，冒泡排序算法时间效率越高，在O（n）到O（n2）之间。

冒泡排序需要一个辅助空间用于交换两个元素，空间复杂度为O（1）。

冒泡排序算法是稳定的。

快速排序
快速排序是一种分区交换排序算法。
1.快速排序算法
首先进一步分析冒泡排序。冒泡排序第1趟扫描，元素87在相邻位置间经过若干次连续的交换到达最终位置的过程如下图所示。

已知一次交换需要3次赋值，元素87从keys[2]经过temp到达keys[3]，再从keys[3]经过temp到达keys[4]，…，直到keys[5]，其间多次到达temp再离开，因此存在重复的数据移动。快速排序算法希望尽可能地减少这样重复的数据移动。

快速排序（Quick Sort）算法描述：在数据序列中选择一个元素作为基准值，每趟从数据序列的两端开始交替进行，将小于基准值的元素交换到序列前端，将大于基准值的元素交换到序列后端，介于两者之间的位置则成为基准值的最终位置。同时，序列被划分成两个子序列，再分别对两个子序列进行快速排序，直到子序列长度为1，则完成排序。

关键字序列{38，38*，97，75，61，19，26，49}快速排序（升序）一趟划分过程如图9.6所示，{}表示待排序子序列。

对存于keys数组begin～end之间的子序列进行一趟快速排序，设i、j下标分别从子序列的前后两端开始，i=begin，j=end，划分算法描述如下：

① 选取子序列第一个元素keys[i]38作为基准值vot，空出keys[i]元素位置。
② 在子序列后端寻找小于基准值的元素，交换到序列前端。即比较keys[j]元素26与基准值，若小则将keys[j]元素26移动到序列前端keys[i]位置，i++，此时keys[j]位置空出。
③ 在子序列前端寻找大于基准值的元素，交换到序列后端。再比较keys[i]元素与基准值，若大则将keys[i]元素97移动到序列后端的keys[j]位置，j-，keys[i]位置空出。不移动与基准值相等元素。
④ 重复执行②③，直到i==j，表示子序列中的每个元素都与基准值比较过了，并已将小于基准值的元素移动到前端，将大于基准值的元素移动到后端，当前i（j）位置则是基准值的最终位置。观察图9.6的数据移动情况，一趟划分过程中，只用6次赋值，就使5个元素移动位置。
⑤ 一趟快速排序将数据序列划分成两个子序列，范围分别为begin～j-1、i+1～end。每个子序列均较短，再对两个子序列分别进行快速排序，直到子序列长度为1。

上述数据序列的快速排序（升序）过程如下图所示，{}表示待排序子序列。

快速排序算法采用分治策略对两个子序列再分别进行快速排序，因此，快速排序是递归算法。快速排序算法实现如下：

public class Quick_Sort {
    public static void main(String[] args) {
        int[] keys = {38, 38, 97, 75, 61, 19, 26, 49};
        quickSort(keys);
    }

    //9.2.2   快速排序
    public static void quickSort(int[] keys)               //快速排序（升序）
    {
        System.out.println("排序前的数据:");
        for (int key : keys) {
            System.out.print(key + "\t");
        }
        System.out.println();
        System.out.println("快速排序（升序）");
        quickSort(keys, 0, keys.length - 1);
        System.out.println("最终排序的结果:");
        for (int key : keys) {
            System.out.print(key + "\t");
        }
    }

    //对存于keys数组begin～end之间的子序列进行一趟快速排序，递归算法
    private static void quickSort(int[] keys, int begin, int end) {
        if (begin >= 0 && end >= 0 && end < keys.length && begin < end)//序列有效
        {
            int i = begin, j = end;                            //i、j下标分别从子序列的前后两端开始
            int vot = keys[i];                               //子序列第一个值作为基准值
            while (i != j) {
                while (i < j && keys[j] >= vot)                //（升序）从后向前寻找较小值，不移动与基准值相等元素
//                while (i<j && vot>=keys[j])                //（降序）从后向前寻找较大值，不移动与基准值相等元素
                {
                    j--;
                }
                if (i < j) {
                    keys[i++] = keys[j];                     //子序列后端较小元素向前移动
                }
                while (i < j && keys[i] <= vot)                //（升序）从前向后寻找较大值，不移动与基准值相等元素
//                while (i<j && keys[i]>=vot)                //（降序）从前向后寻找较小值，不移动与基准值相等元素
                {
                    i++;
                }
                if (i < j) {
                    keys[j--] = keys[i];                     //子序列前端较大元素向后移动
                }

            }
            keys[i] = vot;                                   //基准值到达最终位置
            System.out.print("下标" + begin + "～" + end + "， vot=" + vot + "，  ");
            for (int key : keys) {
                System.out.print(key + "\t");
            }
            System.out.println();
            quickSort(keys, begin, j - 1);                   //前端子序列再排序，递归调用
            quickSort(keys, i + 1, end);                     //后端子序列再排序，递归调用
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

结果：

排序前的数据:
38	38	97	75	61	19	26	49	
快速排序（升序）
下标0～7， vot=38，  26	38	19	38	61	75	97	49	
下标0～2， vot=26，  19	26	38	38	61	75	97	49	
下标4～7， vot=61，  19	26	38	38	49	61	97	75	
下标6～7， vot=97，  19	26	38	38	49	61	75	97	
最终排序的结果:
19	26	38	38	49	61	75	97	
1
2
3
4
5
6
7
8
9

2.快速排序算法分析

快速排序的执行时间与数据序列的初始排列及基准值的选取有关，分析如下:
① 最好情况，每趟排序将序列分成长度相近的两个子序列，时间复杂度为O（n×log2n）。
② 最坏情况，每趟将序列分成长度差异很大的两个子序列，时间复杂度为O（n2）。例如，设一个排序数据序列有n个元素，若选取序列的第一个值作为基准值，则第一趟得到的两个子序列长度分别为0和n-1：

这样必须经过n-1趟才能完成排序，因此，比较次数:

快速排序选择基准值还有其他多种方法，如可以选取序列的中间值等。但由于序列的初始排列是随机的，不管如何选择基准值，总会存在最坏情况。

此外，快速排序还要在执行递归函数过程中花费一定的时间和空间，使用栈保存参数，栈所占用的空间与递归调用的次数有关，空间复杂度为O（log2n）～O（n）。

总之，当n较大且数据序列随机排列时，快速排序是“快速”的；当n很小或基准值选取不合适时，快速排序则较慢。快速排序算法是不稳定的。

选择排序

直接选择排序
1.直接选择排序算法
直接选择排序（Straight Select Sort）算法思想：第一趟从n个元素的数据序列中选出关键字最小/大的元素并放到最前/后位置，下一趟再从n-1个元素中选出最小/大的元素并放到次前/后位置，以此类推，经过n-1趟完成排序。
关键字序列{38，97，26，19，38*，15}的直接选择排序（升序）过程如下图所示，其中，i表示子序列起始位置，min表示最小元素位置，一趟扫描后将min位置元素交换到i位置，{}表示排序子序列。

直接选择排序算法实现如下：

public class Select_Sort {
    public static void main(String[] args) {
        int[] keys = {38, 97, 26, 19, 38, 15};
        selectSort(keys);
    }

    private static void swap(int[] keys, int i, int j)     //交换keys[i]与keys[j]元素，i、j范围由调用者控制
    {
        int temp = keys[j];
        keys[j] = keys[i];
        keys[i] = temp;
    }

    public static void selectSort(int[] keys)              //直接选择排序（升序）
    {
        System.out.println("直接选择排序（升序）");
        for (int i = 0; i < keys.length - 1; i++)                //n-1趟排序
        {
            int min = i;
            for (int j = i + 1; j < keys.length; j++)            //每趟在从keys[i]开始的子序列中寻找最小元素
                if (keys[j] < keys[min])                     //（升序）
//                if (keys[j]>keys[min])                     //（降序）
                    min = j;                              //min记住本趟最小元素下标
            System.out.print("第" + (i + 1) + "趟，下标" + i + "～" + (keys.length - 1) + "，min=" + min + "，");
            if (min != i)                                    //将本趟最小元素交换到前边
            {
                swap(keys, i, min);
            }

            for (int key : keys) {
                System.out.print(key + "\t");
            }
            System.out.println();
        }
        System.out.println("最终排序的结果:");
        for (int key : keys) {
            System.out.print(key + "\t");
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

结果：

直接选择排序（升序）
第1趟，下标0～5，min=5，15	97	26	19	38	38	
第2趟，下标1～5，min=3，15	19	26	97	38	38	
第3趟，下标2～5，min=2，15	19	26	97	38	38	
第4趟，下标3～5，min=4，15	19	26	38	97	38	
第5趟，下标4～5，min=5，15	19	26	38	38	97	
最终排序的结果:
15	19	26	38	38	97
1
2
3
4
5
6
7
8

2.直接选择排序算法分析
直接选择排序的比较次数与数据序列的初始排列无关，第i趟排序的比较次数是n-i；移动次数与初始排列有关，排序序列移动0次；反序排列的数据序列，每趟排序都要交换，移动3（n-1）次。算法总比较次数:

时间复杂度为O（n2）。

直接选择排序的空间复杂度为O（1）。直接选择排序算法是不稳定的。

堆排序

堆排序（Heap Sort）是利用完全二叉树特性的一种选择排序。

1.堆的定义

设n个元素的数据序列{k0，k1，…，kn-1}，当且仅当满足下列关系时，称为最小/大堆。

换言之，将{{k0，k1，…，kn-1}}序列看成是一棵完全二叉树的层次遍历序列，如果任意一个结点元素≤/≥其孩子结点元素，则称该序列为最小/大堆，根结点值最小/大。

根据二叉树性质，完全二叉树中的第i（0≤i<n）个结点，如果有孩子，则左孩子为第2i+1个结点，右孩子为第2i+2个结点。

最小/大堆及其完全二叉树如下图所示：

2.堆的应用

最小/大堆用于求最小/大值，堆序列用于多次求极值的应用问题。

在直接选择排序算法中，求一个数据序列的最小值，必须遍历序列，在比较了所有元素后才能确定最小值，时间复杂度是O（n），效率较低。

如果将该数据序列“堆”成树状，约定父母结点值比孩子结点值小/大，则根结点值最小/大，那么，求最小/大值的时间复杂度是O（1），效率明显提高。堆的树状结构只能是完全二叉树，因为只有完全二叉树才能顺序存储，二叉树的性质5将一个数据序列映射到唯一的一棵完全二叉树。

由关键字序列{81，49，19，38，97，76，13，19*}创建最小堆过程如下图所示：

① 将一个关键字序列看成是一棵完全二叉树的层次遍历序列，此时它不是堆序列。将这棵完全二叉树最深的一棵子树调整成最小堆，该子树的根是序列第parent（=n/2-1）个元素；在根的两个孩子中选出较小值（由child记得）并上移到子树的根。
② 重复①，从下向上依次将每棵子树调整成最小堆。如果一棵子树的根值较大，根值可能下移几层。最后得到该完全二叉树的层次遍历序列是一个最小堆序列。
创建了最小堆，不仅确定了一个最小值，求最小值的时间是O（1），而且还调整了其他元素；下一次只要比较根的两个孩子结点值，就能确定次小值。因此，提高了多次求最小值的算法效率。

堆序列不仅可用于排序算法，还可用于其他频繁选择极值的问题，如优先队列、Huffman、Prim、Kruskal、Dijkstra、Floyd等算法。

3.堆排序算法描述
直接选择排序算法有两个缺点，① 选择最小值效率低，必须遍历子序列，比较了所有元素后才能选出最小值；② 每趟将最小值交换到前面，其余元素原地不动，下一趟没有利用前一趟的比较结果，需要再次比较这些元素，重复比较很多。

堆排序改进了直接选择排序，采用最小/大堆选择最小/大值。堆排序分以下两个阶段：

① 将一个数据序列建成最小/大堆，则根结点值最小/大；
② 进行选择排序，每趟将最小值（根结点值）交换到后面，再将其余值调整成堆，依此重复，直到子序列长度为1，排序完成。使用最小/大堆，得到排序结果是降/升序的。

以最小堆进行选择排序，上述数据序列前两趟堆排序（降序）过程如下图所示：

① 最小堆的根值13最小，将13交换到最后，13不参加下一趟排序，子序列右边界减1；再将以49为根的子序列调整成最小堆，只要比较根的两个孩子结点值27与19，就能确定次小值。将根值49向下调整，经过从根到叶子结点（最远）的一条路径。
② 重复①，将根值与keys[n-i]（0≤i<n）元素交换，再调整成最小堆，直到子序列长度为1，排序完成。

上述数据序列的堆排序（降序）结果如下，{}表示最小堆序列。

4.堆排序算法实现

堆排序算法实现如下，包括两个方法，heapSort（）实现堆排序，sift（）调整为最小/大堆。

public class Heap_Sort {
    public static void main(String[] args) {
        int[] keys = {81, 49, 19, 38, 97, 76, 13, 19};
        heapSort(keys);
    }

    private static void swap(int[] keys, int i, int j)     //交换keys[i]与keys[j]元素，i、j范围由调用者控制
    {
        int temp = keys[j];
        keys[j] = keys[i];
        keys[i] = temp;
    }

    public static void heapSort(int[] keys)                //堆排序（升序），最大堆
    {
        System.out.println("排序前的数据:");
        for (int key : keys) {
            System.out.print(key + "\t");
        }
        System.out.println();
        heapSort(keys, true);
    }

    //堆排序，若asc取值为true，升序排序，创建最大堆；否则降序，创建最小堆
    public static void heapSort(int[] keys, boolean asc) {
        for (int i = keys.length / 2 - 1; i >= 0; i--)             //创建最小/大堆，根结点值最小/大
            sift(keys, i, keys.length - 1, !asc);
        System.out.print("最" + ((!asc) ? "小" : "大") + "堆：");
        // Array1.print(keys);
        System.out.println("非递归算法，最小堆？ " + isHeap(keys, true) + "，最大堆？ " + isHeap(keys, false));
        System.out.print("堆排序（" + ((!asc) ? "降" : "升") + "序）：");
        for (int i = keys.length - 1; i > 0; i--)                //每趟将最小/大值交换到后面，再调整成最小/大堆
        {
            swap(keys, 0, i);                              //交换keys[0]与keys[i]
            sift(keys, 0, i - 1, !asc);
        }
        for (int key : keys) {
            System.out.print(key + "\t");
        }
        System.out.println();
    }

    //将keys数组中以parent为根的子树调整成最小/大堆，子序列范围为parent～end。
    private static void sift(int[] keys, int parent, int end, boolean minheap) {
//        System.out.print("sift  "+parent+".."+end+"  ");
        int child = 2 * parent + 1;                              //child是parent的左孩子
        int value = keys[parent];
        while (child <= end)                                 //沿较小/大值孩子结点向下筛选
        {
            if (child < end && (minheap ? keys[child] > keys[child + 1] : keys[child] < keys[child + 1]))
                child++;                               //child记住孩子值较小/大者
            if (minheap ? value > keys[child] : value < keys[child])   //若父母结点值较小/大
            {
                keys[parent] = keys[child];                //将较小/大孩子结点值上移
                parent = child;                            //parent、child两者都向下一层
                child = 2 * parent + 1;
            } else break;
        }
        keys[parent] = value;                              //当前子树的原根值调整后的位置
    }

    //判断value指定数据序列是否为堆，若minheap取值为true，则最小堆；否则最大堆。非递归算法
    public static boolean isHeap(int[] value, boolean minheap) {
        if (value.length == 0)                               //空序列不是堆。若无此句，则空序列是堆，定义不同
            return false;
        for (int i = value.length / 2 - 1; i >= 0; i--)            //i从最深一棵子树的根结点开始
        {
            int left = 2 * i + 1;                                //left是i的左孩子，肯定存在
            if (minheap ? (value[i] > value[left] || left + 1 < value.length && value[i] > value[left + 1])
                    : (value[i] < value[left] || left + 1 < value.length && value[i] < value[left + 1]))
                return false;                              //根值较大/小时，肯定不是最小/大堆
        }
        return true;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

结果：

排序前的数据:
81	49	19	38	97	76	13	19	
最大堆：非递归算法，最小堆？ false，最大堆？ true
堆排序（升序）：13	19	19	38	49	76	81	97	
1
2
3
4

5.堆排序算法分析
将一个数据序列调整为堆的时间复杂度为O（log2n），因此堆排序的时间复杂度为O（n×log2n）。堆排序的空间复杂度为O（1）。堆排序算法是不稳定的。

归并排序

归并排序是将两个排序的子序列合并，形成一个排序数据序列，又称两路归并排序。

1.归并排序算法描述
关键字序列{97，82，75，53，17，61，70，12，61*，58，26}的归并排序（升序）过程如下图所示，{}表示排序子序列。将n个元素的数据序列看成是由n个长度为1的排序子序列组成，反复将相邻的两个子序列归并成一个排序子序列，直到合并成一个序列，则排序完成。

2.归并排序算法实现

两路归并排序包括3个函数。

（1）一次归并

核心操作是一次归并，声明 merge（）方法如下，将 X 数组中相邻的两个排序子序列{xbegin1，…，xbegin1+n-1}和{xbegin2，…，xbegin2+n-1}归并（升序）到 Y 数组中，成为{ybegin1，…，ybegin2+n-1}子序列，如下图所示：

（2）一趟归并

声明mergepass（）方法如下，实现一趟归并。

（3）归并排序

声明mergeSort（X[]）方法如下，将X数组中的数据序列进行两路归并排序。其中，Y是辅助数组，长度同数组X；子序列长度n初值为1，每趟归并后n加倍。一次while循环完成两趟归并，数据序列从X到Y，再从Y到X，这样使排序后的数据序列仍在X数组中。

整个代码如下：

public class Merge_Sort {
    public static void main(String[] args) {
        int[] keys = {97, 82, 75, 53, 17, 61, 70, 12, 61, 58, 26};
        System.out.println("排序前的数据:");
        for (int key : keys) {
            System.out.print(key + "\t");
        }
        mergeSort(keys);
    }

    public static void mergeSort(int[] X)                  //归并排序（升序）
    {
        System.out.println("\n" + "归并排序（升序）");
        int[] Y = new int[X.length];                       //Y数组长度同X数组
        int n = 1;                                           //排序子序列长度，初值为1
        while (n < X.length) {
            mergepass(X, Y, n);                            //一趟归并，将X中若干相邻子序列归并到Y
            n *= 2;                                          //子序列长度加倍
            if (n < X.length) {
                mergepass(Y, X, n);                        //一趟归并，将Y中若干相邻子序列再归并到X
                n *= 2;
            }
        }

        System.out.println("最终排序的结果:");
        for (int key : X) {
            System.out.print(key + "\t");
        }
    }

    //一趟归并，将X中若干相邻子序列两两归并到Y中，子序列长度为n
    private static void mergepass(int[] X, int[] Y, int n) {
        System.out.print("子序列长度n=" + n + "  ");
        for (int i = 0; i < X.length; i += 2 * n)                //将X中若干相邻子序列归并到Y中
        {
            merge(X, Y, i, i + n, n); //一次归并
        }
        for (int key : Y) {
            System.out.print(key + "\t");
        }
        System.out.println();
    }

    //一次归并（升序）
    //将X中分别以begin1、begin2开始的两个相邻子序列归并（升序）到Y中，子序列长度为n
    private static void merge(int[] X, int[] Y, int begin1, int begin2, int n) {
        int i = begin1, j = begin2, k = begin1;
        while (i < begin1 + n && j < begin2 + n && j < X.length)     //将X中两个相邻子序列归并到Y中
            if (X[i] < X[j])                                 //（升序）将较小值复制到Y中
//            if (X[i]>X[j])                                 //（降序）将较大值复制到Y中
                Y[k++] = X[i++];
            else
                Y[k++] = X[j++];

        while (i < begin1 + n && i < X.length)                   //将前一个子序列剩余元素复制到Y中，子序列长度可能不足n
            Y[k++] = X[i++];
        while (j < begin2 + n && j < X.length)                   //将后一个子序列剩余元素复制到Y中
            Y[k++] = X[j++];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

结果：

排序前的数据:
97	82	75	53	17	61	70	12	61	58	26	
归并排序（升序）
子序列长度n=1  82	97	53	75	17	61	12	70	58	61	26	
子序列长度n=2  53	75	82	97	12	17	61	70	26	58	61	
子序列长度n=4  12	17	53	61	70	75	82	97	26	58	61	
子序列长度n=8  12	17	26	53	58	61	61	70	75	82	97	
最终排序的结果:
12	17	26	53	58	61	61	70	75	82	97	
1
2
3
4
5
6
7
8
9

3.归并排序算法分析
n 个元素归并排序，每趟比较 n-1 次，数据移动 n-1 次，进行:

趟，时间复杂度为O（n×log2n）。

归并排序需要O（n）容量的附加空间，与数据序列的存储容量相等，空间复杂度为O（n）。

归并排序算法是稳定的。

各个排序算法性能对比

各种排序算法性能比较如下表所示，排序算法的时间复杂度为O（n×log2n）～O（n2）。

以上介绍了插入、交换、选择和归并等7个排序算法，其中直接插入排序、冒泡排序、直接选择排序等算法的时间复杂度为O（n2），这些排序算法简单易懂，思路清楚，算法结构为两重循环，共进行n-1趟，每趟排序将一个元素移动到排序后的位置。数据比较和移动在相邻两个元素之间进行，每趟排序与上一趟之间存在较多重复的比较、移动和交换，因此排序效率较低。

另一类较快的排序算法有希尔排序、快速排序、堆排序及归并排序，这些算法设计各有巧妙之处，它们共同的特点是：与相距较远的元素进行比较，数据移动距离较远，跳跃式地向目的地前进，避免了许多重复的比较和数据移动。

后记

这几种常考的排序算法，原理看起来简单，但真正要手撕出来，其实并不容易。尤其是对于指针的控制时机，很难把握。我的原则是，掌握原理，然后试着去写，不会的就抄，总之，无论抄写多少遍，最后要永远刻在脑子里。

关于排序算法也可参考这个博客。