排序算法

发表于

今天看到一道题：
据说是简单的排序题
一点简单的思路就是二分查找。。但是1e4*1e4。。emmmm不会代码实现
所以还是需要总结一波排序算法的。

常见排序算法分类

我们通常所说的排序算法往往指的是内部排序算法，即数据记录在内存中进行排序。

常见排序算法一般分为以下几种：
（1）非线性时间比较类排序：交换类排序（快速排序和冒泡排序）、插入类排序（简单插入排序和希尔排序）、选择类排序（简单选择排序和堆排序）、归并排序（二路归并排序和多路归并排序）；
（2）线性时间非比较类排序：计数排序、基数排序和桶排序。

总结：
（1）在比较类排序中，归并排序号称最快，其次是快速排序和堆排序，两者不相伯仲，但是有一点需要注意，数据初始排序状态对堆排序不会产生太大的影响，而快速排序却恰恰相反。
（2）线性时间非比较类排序一般要优于非线性时间比较类排序，但前者对待排序元素的要求较为严格，比如计数排序要求待排序数的最大值不能太大，桶排序要求元素按照hash分桶后桶内元素的数量要均匀。线性时间非比较类排序的典型特点是以空间换时间。

　有一点我们很容易忽略的是排序算法的稳定性(腾讯校招2016笔试题曾考过)。
　　排序算法稳定性的简单形式化定义为：如果Ai = Aj，排序前Ai在Aj之前，排序后Ai还在Aj之前，则称这种排序算法是稳定的。通俗地讲就是保证排序前后两个相等的数的相对顺序不变。
　　对于不稳定的排序算法，只要举出一个实例，即可说明它的不稳定性；而对于稳定的排序算法，必须对算法进行分析从而得到稳定的特性。需要注意的是，排序算法是否为稳定的是由具体算法决定的，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。
　　例如，对于冒泡排序，原本是稳定的排序算法，如果将记录交换的条件改成A[i] >= A[i + 1]，则两个相等的记录就会交换位置，从而变成不稳定的排序算法。
　　其次，说一下排序算法稳定性的好处。排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，前一个键排序的结果可以为后一个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位排序后元素的顺序在高位也相同时是不会改变的。

算法描述与实现

一，交换类排序

交换排序的基本方法是：两两比较待排序记录的排序码，交换不满足顺序要求的偶对，直到全部满足位置。常见的冒泡排序和快速排序就属于交换类排序。

1，冒泡排序
　冒泡排序是一种极其简单的排序算法，它重复地走访过要排序的元素，依次比较相邻两个元素，如果他们的顺序错误就把他们调换过来，直到没有元素再需要交换，排序完成。这个算法的名字由来是因为越小(或越大)的元素会经由交换慢慢“浮”到数列的顶端。
　　冒泡排序算法的运作如下：

  • 比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置。
  • 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  • 针对所有的元素重复以上的步骤，除了最后一个。
  • 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

最好的情况：如果待排序数据序列为正序，则一趟冒泡就可完成排序，排序码的比较次数为n-1次。
最坏的情况：如果待排序数据序列为逆序，则冒泡排序需要n-1次趟起泡，每趟进行n-i次排序码的比较和移动，即比较和移动次数均达到最大值： n*(n-1)/2。

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
#include <stdio.h>
// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- 如果能在内部循环第一次运行时,使用一个旗标来表示有无需要交换的可能,可以把最优时间复杂度降低到O(n)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定
void Swap(int A[], int i, int j)
{
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}
void BubbleSort(int A[], int n)
{
    for (int j = 0; j < n - 1; j++)         // 每次最大元素就像气泡一样"浮"到数组的最后
    {
        for (int i = 0; i < n - 1 - j; i++) // 依次比较相邻的两个元素,使较大的那个向后移
        {
            if (A[i] > A[i + 1])            // 如果条件改成A[i] >= A[i + 1],则变为不稳定的排序算法
            {
                Swap(A, i, i + 1);
            }
        }
    }
}
int main()
{
    int A[] = { 6, 5, 3, 1, 8, 7, 2, 4 };    // 从小到大冒泡排序
    int n = sizeof(A) / sizeof(int);
    BubbleSort(A, n);
    printf("冒泡排序结果：");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
    return 0;
}

2，鸡尾酒排序

　　鸡尾酒排序，也叫定向冒泡排序，是冒泡排序的一种改进。此算法与冒泡排序的不同处在于从低到高然后从高到低，而冒泡排序则仅从低到高去比较序列里的每个元素。他可以得到比冒泡排序稍微好一点的效能。
　　鸡尾酒排序的代码如下：

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
#include <stdio.h>
// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- 如果序列在一开始已经大部分排序过的话,会接近O(n)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定
void Swap(int A[], int i, int j)
{
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}
void CocktailSort(int A[], int n)
{
    int left = 0;                            // 初始化边界
    int right = n - 1;
    while (left < right)
    {
        for (int i = left; i < right; i++)   // 前半轮,将最大元素放到后面
        {
            if (A[i] > A[i + 1])
            {
                Swap(A, i, i + 1);
            }
        }
        right--;
        for (int i = right; i > left; i--)   // 后半轮,将最小元素放到前面
        {
            if (A[i - 1] > A[i])
            {
                Swap(A, i - 1, i);
            }
        }
        left++;
    }
}
int main()
{
    int A[] = { 6, 5, 3, 1, 8, 7, 2, 4 };   // 从小到大定向冒泡排序
    int n = sizeof(A) / sizeof(int);
    CocktailSort(A, n);
    printf("鸡尾酒排序结果：");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
    return 0;
}

3，快速排序
　　快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序n个元素要O(nlogn)次比较。在最坏状况下则需要O(n^2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他O(nlogn)算法更快，因为它的内部循环可以在大部分的架构上很有效率地被实现出来。
　　快速排序使用分治策略(Divide and Conquer)来把一个序列分为两个子序列。步骤为：
从序列中挑出一个元素，作为”基准”(pivot).
把所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准的后面（相同的数可以到任一边），这个称为分区(partition)操作。
对每个分区递归地进行步骤1~2，递归的结束条件是序列的大小是0或1，这时整体已经被排好序了。
最好的情况：是每趟排序结束后，每次划分使两个子文件的长度大致相等，时间复杂度为
nlog2n。
最坏的情况：是待排序记录已经排好序，第一趟经过n-1次比较后第一个记录保持位置不变，并得到一个n-1个元素的子记录；第二趟经过n-2次比较，将第二个记录定位在原来的位置上，并得到一个包括n-2个记录的子文件，依次类推，这样总的比较次数是：n(n-1)/2。
快速排序是不稳定的排序算法，不稳定发生在基准元素与A[tail+1]交换的时刻。
　　快速排序的代码如下：

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
#include <stdio.h>
// 分类 ------------ 内部比较排序
// 数据结构 --------- 数组
// 最差时间复杂度 ---- 每次选取的基准都是最大（或最小）的元素，导致每次只划分出了一个分区，需要进行n-1次划分才能结束递归，时间复杂度为O(n^2)
// 最优时间复杂度 ---- 每次选取的基准都是中位数，这样每次都均匀的划分出两个分区，只需要logn次划分就能结束递归，时间复杂度为O(nlogn)
// 平均时间复杂度 ---- O(nlogn)
// 所需辅助空间 ------ 主要是递归造成的栈空间的使用(用来保存left和right等局部变量)，取决于递归树的深度，一般为O(logn)，最差为O(n)       
// 稳定性 ---------- 不稳定
void Swap(int A[], int i, int j)
{
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}
int Partition(int A[], int left, int right)  // 划分函数
{
    int pivot = A[right];               // 这里每次都选择最后一个元素作为基准
    int tail = left - 1;                // tail为小于基准的子数组最后一个元素的索引
    for (int i = left; i < right; i++)  // 遍历基准以外的其他元素
    {
        if (A[i] <= pivot)              // 把小于等于基准的元素放到前一个子数组末尾
        {
            Swap(A, ++tail, i);
        }
    }
    Swap(A, tail + 1, right);           // 最后把基准放到前一个子数组的后边，剩下的子数组既是大于基准的子数组
                                        // 该操作很有可能把后面元素的稳定性打乱，所以快速排序是不稳定的排序算法
    return tail + 1;                    // 返回基准的索引
}
void QuickSort(int A[], int left, int right)
{
    if (left >= right)
        return;
    int pivot_index = Partition(A, left, right); // 基准的索引
    QuickSort(A, left, pivot_index - 1);
    QuickSort(A, pivot_index + 1, right);
}
int main()
{
    int A[] = { 5, 2, 9, 4, 7, 6, 1, 3, 8 }; // 从小到大快速排序
    int n = sizeof(A) / sizeof(int);
    QuickSort(A, 0, n - 1);
    printf("快速排序结果：");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
    return 0;
}

二，插入类排序

1，直接插入排序
插入排序是一种简单直观的排序算法。它的工作原理非常类似于我们抓扑克牌。　对于未排序数据(右手抓到的牌)，在已排序序列(左手已经排好序的手牌)中从后向前扫描，找到相应位置并插入。
　　插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
　　具体算法描述如下： 　　

  • 从第一个元素开始，该元素可以认为已经被排序
  • 取出下一个元素，在已经排序的元素序列中从后向前扫描
  • 如果该元素（已排序）大于新元素，将该元素移到下一位置
  • 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
  • 将新元素插入到该位置后

  • 重复步骤2~5

    最好情况：当待排序记录已经有序，这时需要比较的次数是n-1；
    最坏情况：如果待排序记录为逆序，则最多的比较次数为n*(n-1)/2;
    插入排序的代码如下：

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
#include <stdio.h>
// 分类 ------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- 最坏情况为输入序列是降序排列的,此时时间复杂度O(n^2)
// 最优时间复杂度 ---- 最好情况为输入序列是升序排列的,此时时间复杂度O(n)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定
void InsertionSort(int A[], int n)
{
    for (int i = 1; i < n; i++)         // 类似抓扑克牌排序
    {
        int get = A[i];                 // 右手抓到一张扑克牌
        int j = i - 1;                  // 拿在左手上的牌总是排序好的
        while (j >= 0 && A[j] > get)    // 将抓到的牌与手牌从右向左进行比较
        {
            A[j + 1] = A[j];            // 如果该手牌比抓到的牌大，就将其右移
            j--;
        }
        A[j + 1] = get; // 直到该手牌比抓到的牌小(或二者相等)，将抓到的牌插入到该手牌右边(相等元素的相对次序未变，所以插入排序是稳定的)
    }
}
int main()
{
    int A[] = { 6, 5, 3, 1, 8, 7, 2, 4 };// 从小到大插入排序
    int n = sizeof(A) / sizeof(int);
    InsertionSort(A, n);
    printf("插入排序结果：");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
    return 0;
}

　　插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，比如量级小于千，那么插入排序还是一个不错的选择。 插入排序在工业级库中也有着广泛的应用，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序（通常为8个或以下）。

2,二分插入排序
对于插入排序，如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的次数，我们称为二分插入排序，代码如下：

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
#include <stdio.h>
// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- O(nlogn)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定
void InsertionSortDichotomy(int A[], int n)
{
    for (int i = 1; i < n; i++)
    {
        int get = A[i];                    // 右手抓到一张扑克牌
        int left = 0;                    // 拿在左手上的牌总是排序好的，所以可以用二分法
        int right = i - 1;                // 手牌左右边界进行初始化
        while (left <= right)            // 采用二分法定位新牌的位置
        {
            int mid = (left + right) / 2;
            if (A[mid] > get)
                right = mid - 1;
            else
                left = mid + 1;
        }
        for (int j = i - 1; j >= left; j--)    // 将欲插入新牌位置右边的牌整体向右移动一个单位
        {
            A[j + 1] = A[j];
        }
        A[left] = get;                    // 将抓到的牌插入手牌
    }
}
int main()
{
    int A[] = { 5, 2, 9, 4, 7, 6, 1, 3, 8 };// 从小到大二分插入排序
    int n = sizeof(A) / sizeof(int);
    InsertionSortDichotomy(A, n);
    printf("二分插入排序结果：");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
    return 0;
}

　　当n较大时，二分插入排序的比较次数比直接插入排序的最差情况好得多，但比直接插入排序的最好情况要差，所当以元素初始序列已经接近升序时，直接插入排序比二分插入排序比较次数少。二分插入排序元素移动次数与直接插入排序相同，依赖于元素初始序列。

3，Shell排序

　　希尔排序，也叫递减增量排序，是插入排序的一种更高效的改进版本。希尔排序是不稳定的排序算法。
　　Shell排序法是对相邻指定距离(称为增量)的元素进行比较，并不断把增量缩小至1，完成排序。Shell排序开始时增量较大，分组较多，每组的记录数目较少，故在各组内采用直接插入排序较快，后来增量di逐渐缩小，分组数减少，各组的记录数增多，但由于已经按d(i−1)分组排序，文件接近于有序状态，所以新的一趟排序过程较快。因此Shell排序在效率上比直接插入排序有较大的改进。
在直接插入排序的基础上，将直接插入排序中的1全部改变成增量d即可，因为Shell排序最后一轮的增量d就为1。
　　希尔排序是基于插入排序的以下两点性质而提出改进方法的：

  • 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率

  • 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

    　　希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。
    　　假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为O(n^2)的排序（冒泡排序或直接插入排序），可能会进行n次的比较和交换才能将该数据移至正确位置。而希尔排序会用较大的步长移动数据，所以小数据只需进行少数比较和交换即可到正确位置。
    　　希尔排序是不稳定的排序算法，虽然一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱。
    　　Shell排序算法的时间复杂度分析比较复杂，实际所需的时间取决于各次排序时增量的个数和增量的取值。研究证明，若增量的取值比较合理，Shell排序算法的时间复杂度约为n^1.3。
    　　对于增量的选择，Shell 最初建议增量选择为n/2，并且对增量取半直到 1；D. Knuth教授建议d(i+1)=[d(i-1)/3]序列。
    　　希尔排序的代码如下： 　　

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
#include <stdio.h>  
// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- 根据步长序列的不同而不同。已知最好的为O(n(logn)^2)
// 最优时间复杂度 ---- O(n)
// 平均时间复杂度 ---- 根据步长序列的不同而不同。
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 不稳定
void ShellSort(int A[], int n)
{
    int h = 0;
    while (h <= n)                          // 生成初始增量
    {
        h = 3 * h + 1;
    }
    while (h >= 1)
    {
        for (int i = h; i < n; i++)
        {
            int j = i - h;
            int get = A[i];
            while (j >= 0 && A[j] > get)
            {
                A[j + h] = A[j];
                j = j - h;
            }
            A[j + h] = get;
        }
        h = (h - 1) / 3;                    // 递减增量
    }
}
int main()
{
    int A[] = { 5, 2, 9, 4, 7, 6, 1, 3, 8 };// 从小到大希尔排序
    int n = sizeof(A) / sizeof(int);
    ShellSort(A, n);
    printf("希尔排序结果：");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
    return 0;
}

三，选择类排序

选择类排序的基本方法是：每步从待排序记录中选出排序码最小的记录，顺序放在已排序的记录序列的后面，知道全部排完。
1，简单选择排序
　　选择排序也是一种简单直观的排序算法。它的工作原理很容易理解：初始时在序列中找到最小（大）元素，放到序列的起始位置作为已排序序列；然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
　　注意选择排序与冒泡排序的区别：冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小（大）元素放到合适的位置；而选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置。
　　因简单选择排序也是常见排序算法中性能最差的排序算法。简单选择排序的比较次数与文件的初始状态没有关系，在第i趟排序中选出最小排序码的记录，需要做n-i次比较，因此总的比较次数是n(n-1)/2。
　　*选择排序是不稳定的排序算法，不稳定发生在最小元素与A[i]交换的时刻。

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
#include <stdio.h>
// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- O(n^2)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 不稳定
void Swap(int A[], int i, int j)
{
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}
void SelectionSort(int A[], int n)
{
    for (int i = 0; i < n - 1; i++)         // i为已排序序列的末尾
    {
        int min = i;
        for (int j = i + 1; j < n; j++)     // 未排序序列
        {
            if (A[j] < A[min])              // 找出未排序序列中的最小值
            {
                min = j;
            }
        }
        if (min != i)
        {
            Swap(A, min, i);    // 放到已排序序列的末尾，该操作很有可能把稳定性打乱，所以选择排序是不稳定的排序算法
        }
    }
}
int main()
{
    int A[] = { 8, 5, 2, 6, 9, 3, 1, 4, 0, 7 }; // 从小到大选择排序
    int n = sizeof(A) / sizeof(int);
    SelectionSort(A, n);
    printf("选择排序结果：");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
    return 0;
}

2，堆排序
　　鉴于。。我们都不怎么熟悉堆，先来讨论一下堆：
　
　　关于堆：
　　（1）性质：完全二叉树或者是近似完全二叉树；
　　（2）分类：大顶堆：父节点不小于子节点键值，小顶堆：父节点不大于子节点键值；
　　（3）左右孩子：没有大小的顺序。
　　（4）堆的存储 ：一般都用数组来存储堆，i结点的父结点下标就为(i–1)/2。它的左右子结点下标分别为 2\∗i+1和 2\∗i+2。
　　（5）堆的操作

　　<1>插入： 将一个新元素插入到表尾，即数组末尾时，如果新构成的二叉树不满足堆的性质，需要重新排列元素。
　　每次插入都是将新数据放在数组最后。可以发现从这个新数据的父结点到根结点必然为一个有序的数列，现在的任务是将这个新数据插入到这个有序数据中，这就类似于直接插入排序中将一个数据并入到有序区间中，这是节点“上浮”调整。不难写出插入一个新数据时堆的调整代码： 　　

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//新加入i结点,其父结点为(i-1)/2
//参数：a：数组，i：新插入元素在数组中的下标  
void minHeapFixUp(int a[], int i)  
{  
    int j, temp;  
    temp = a[i];  
    j = (i-1)/2;      //父结点  
    while (j >= 0 && i != 0)  
    {  
        if (a[j] <= temp)//如果父节点不大于新插入的元素，停止寻找  
            break;  
        a[i]=a[j];     //把较大的子结点往下移动,替换它的子结点  
        i = j;  
        j = (i-1)/2;  
    }  
    a[i] = temp;  
}

因此，插入数据到最小堆时：

1
2
3
4
5
6
7
//在最小堆中加入新的数据data  
//a：数组，index：插入的下标，
void minHeapAddNumber(int a[], int index, int data)  
{  
    a[index] = data;  
    minHeapFixUp(a, index);  
}

　　<2>删除：
　　堆排序中，删除一个元素总是发生在堆顶，因为堆顶的元素是最小的（小顶堆中）。表中最后一个元素用来填补空缺位置，结果树被更新以满足堆条件。

　　按定义，堆中每次都只能删除第0个数据。为了便于重建堆，实际的操作是将数组最后一个数据与根结点，然后再从根结点开始进行一次从上向下的调整。
　　调整时先在左右儿子结点中找最小的，如果父结点不大于这个最小的子结点说明不需要调整了，反之将最小的子节点换到父结点的位置。此时父节点实际上并不需要换到最小子节点的位置，因为这不是父节点的最终位置。但逻辑上父节点替换了最小的子节点，然后再考虑父节点对后面的结点的影响。相当于从根结点将一个数据的“下沉”过程。下面给出代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//a为数组，从index节点开始调整,len为节点总数 从0开始计算index节点的子节点为 2*index+1, 2*index+2,len/2-1为最后一个非叶子节点  
void minHeapFixDown(int a[],int len,int index){
    if(index>(len/2-1))//index为叶子节点不用调整
        return;
    int tmp=a[index];
    int lastIndex=index;
    while(index<=(len/2-1)){ //当下沉到叶子节点时，就不用调整了
        if(a[2*index+1]<tmp) //如果左子节点大于该节点
            lastIndex = 2*index+1;
        //如果存在右子节点且大于左子节点和该节点
        if(2*index+2<len && a[2*index+2]<a[2*index+1]&& a[2*index+2]<tmp)
            lastIndex = 2*index+2;
        if(lastIndex!=index){  //如果左右子节点有一个小于该节点则设置该节点的下沉位置
            a[index]=a[lastIndex];
            index=lastIndex;
        }else break;  //否则该节点不用下沉调整
    }
    a[lastIndex]=tmp;//将该节点放到最后的位置
}

　　<3>建堆：
　　有了堆的插入和删除后，再考虑下如何对一个数据进行堆化操作。要一个一个的从数组中取出数据来建立堆吧，不用！ 　　

1
2
3
4
5
6
7
//建立最小堆
//a:数组，n：数组长度
void makeMinHeap(int a[], int n)  
{  
    for (int i = n/2-1; i >= 0; i--)  
        minHeapFixDown(a, i, n);  
}

　　堆排序是指利用堆这种数据结构所设计的一种选择排序算法。堆是一种近似完全二叉树的结构（通常堆是通过一维数组来实现的），并满足性质：以最大堆（也叫大根堆、大顶堆）为例，其中父结点的值总是大于它的孩子节点。
　　我们可以很容易的定义堆排序的过程： 　　

  • 由输入的无序数组构造一个最大堆，作为初始的无序区
  • 把堆顶元素（最大值）和堆尾元素互换
  • 把堆（无序区）的尺寸缩小1，并调用heapify(A, 0)从新的堆顶元素开始进行堆调整

  • 重复步骤2，直到堆的尺寸为1

    堆排序是不稳定的排序算法，不稳定发生在堆顶元素与A[i]交换的时刻。

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
#include <stdio.h>
// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(nlogn)
// 最优时间复杂度 ---- O(nlogn)
// 平均时间复杂度 ---- O(nlogn)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 不稳定
void Swap(int A[], int i, int j)
{
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}
void Heapify(int A[], int i, int size)  // 从A[i]向下进行堆调整
{
    int left_child = 2 * i + 1;         // 左孩子索引
    int right_child = 2 * i + 2;        // 右孩子索引
    int max = i;                        // 选出当前结点与其左右孩子三者之中的最大值
    if (left_child < size && A[left_child] > A[max])
        max = left_child;
    if (right_child < size && A[right_child] > A[max])
        max = right_child;
    if (max != i)
    {
        Swap(A, i, max);                // 把当前结点和它的最大(直接)子节点进行交换
        Heapify(A, max, size);          // 递归调用，继续从当前结点向下进行堆调整
    }
}
int BuildHeap(int A[], int n)           // 建堆，时间复杂度O(n)
{
    int heap_size = n;
    for (int i = heap_size / 2 - 1; i >= 0; i--) // 从每一个非叶结点开始向下进行堆调整
        Heapify(A, i, heap_size);
    return heap_size;
}
void HeapSort(int A[], int n)
{
    int heap_size = BuildHeap(A, n);    // 建立一个最大堆
    while (heap_size > 1)    　　　　　　 // 堆（无序区）元素个数大于1，未完成排序
    {
        // 将堆顶元素与堆的最后一个元素互换，并从堆中去掉最后一个元素
        // 此处交换操作很有可能把后面元素的稳定性打乱，所以堆排序是不稳定的排序算法
        Swap(A, 0, --heap_size);
        Heapify(A, 0, heap_size);     // 从新的堆顶元素开始向下进行堆调整，时间复杂度O(logn)
    }
}
int main()
{
    int A[] = { 5, 2, 9, 4, 7, 6, 1, 3, 8 };// 从小到大堆排序
    int n = sizeof(A) / sizeof(int);
    HeapSort(A, n);
    printf("堆排序结果：");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
    return 0;
}

　　堆排序的性能分析
由于每次重新恢复堆的时间复杂度为O(logN)，共N - 1次堆调整操作，再加上前面建立堆时N / 2次向下调整，每次调整时间复杂度也为O(logN)。两次次操作时间相加还是O(N * logN)。故堆排序的时间复杂度为O(N * logN)。
最坏情况：如果待排序数组是有序的，仍然需要O(N * logN)复杂度的比较操作，只是少了移动的操作；
最好情况：如果待排序数组是逆序的，不仅需要O(N * logN)复杂度的比较操作，而且需要O(N * logN)复杂度的交换操作。总的时间复杂度还是O(N * logN)。
因此，堆排序和快速排序在效率上是差不多的，但是堆排序一般优于快速排序的重要一点是，数据的初始分布情况对堆排序的效率没有大的影响。

四，归并排序

　　归并排序是创建在归并操作上的一种有效的排序算法，效率为O(nlogn)，1945年由冯·诺伊曼首次提出。
　　归并排序的实现分为递归实现与非递归(迭代)实现。递归实现的归并排序是算法设计中分治策略的典型应用，我们将一个大问题分割成小问题分别解决，然后用所有小问题的答案来解决整个大问题。非递归(迭代)实现的归并排序首先进行是两两归并，然后四四归并，然后是八八归并，一直下去直到归并了整个数组。
　　归并排序算法主要依赖归并(Merge)操作。归并操作指的是将两个已经排序的序列合并成一个序列的操作，归并操作步骤如下： 　　

  • 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
  • 设定两个指针，最初位置分别为两个已经排序序列的起始位置
  • 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
  • 重复步骤3直到某一指针到达序列尾
  • 将另一序列剩下的所有元素直接复制到合并序列尾
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
77
78
79
80
81
82
83
84
85
#include <stdio.h>
#include <limits.h>
// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(nlogn)
// 最优时间复杂度 ---- O(nlogn)
// 平均时间复杂度 ---- O(nlogn)
// 所需辅助空间 ------ O(n)
// 稳定性 ------------ 稳定
void Merge(int A[], int left, int mid, int right)// 合并两个已排好序的数组A[left...mid]和A[mid+1...right]
{
    int len = right - left + 1;
    int *temp = new int[len];       // 辅助空间O(n)
    int index = 0;
    int i = left;                   // 前一数组的起始元素
    int j = mid + 1;                // 后一数组的起始元素
    while (i <= mid && j <= right)
    {
        temp[index++] = A[i] <= A[j] ? A[i++] : A[j++];  // 带等号保证归并排序的稳定性
    }
    while (i <= mid)
    {
        temp[index++] = A[i++];
    }
    while (j <= right)
    {
        temp[index++] = A[j++];
    }
    for (int k = 0; k < len; k++)
    {
        A[left++] = temp[k];
    }
}
void MergeSortRecursion(int A[], int left, int right)    // 递归实现的归并排序(自顶向下)
{
    if (left == right)    // 当待排序的序列长度为1时，递归开始回溯，进行merge操作
        return;
    int mid = (left + right) / 2;
    MergeSortRecursion(A, left, mid);
    MergeSortRecursion(A, mid + 1, right);
    Merge(A, left, mid, right);
}
void MergeSortIteration(int A[], int len)    // 非递归(迭代)实现的归并排序(自底向上)
{
    int left, mid, right;// 子数组索引,前一个为A[left...mid]，后一个子数组为A[mid+1...right]
    for (int i = 1; i < len; i *= 2)        // 子数组的大小i初始为1，每轮翻倍
    {
        left = 0;
        while (left + i < len)              // 后一个子数组存在(需要归并)
        {
            mid = left + i - 1;
            right = mid + i < len ? mid + i : len - 1;// 后一个子数组大小可能不够
            Merge(A, left, mid, right);
            left = right + 1;               // 前一个子数组索引向后移动
        }
    }
}
int main()
{
    int A1[] = { 6, 5, 3, 1, 8, 7, 2, 4 };      // 从小到大归并排序
    int A2[] = { 6, 5, 3, 1, 8, 7, 2, 4 };
    int n1 = sizeof(A1) / sizeof(int);
    int n2 = sizeof(A2) / sizeof(int);
    MergeSortRecursion(A1, 0, n1 - 1);          // 递归实现
    MergeSortIteration(A2, n2);                 // 非递归实现
    printf("递归实现的归并排序结果：");
    for (int i = 0; i < n1; i++)
    {
        printf("%d ", A1[i]);
    }
    printf("\n");
    printf("非递归实现的归并排序结果：");
    for (int i = 0; i < n2; i++)
    {
        printf("%d ", A2[i]);
    }
    printf("\n");
    return 0;
}

五，非比较排序

1.计数排序
计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出，它的优势在于在对于较小范围内的整数排序。它的复杂度为Ο(n+k)（其中k是待排序数的范围），快于任何比较排序算法，缺点就是非常消耗空间。很明显，如果而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序，比如堆排序和归并排序和快速排序。
算法原理：
基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。例如，如果输入序列中只有17个元素的值小于x的值，则x可以直接存放在输出序列的第18个位置上。当然，如果有多个元素具有相同的值时，我们不能将这些元素放在输出序列的同一个位置上，在代码中作适当的修改即可。
算法步骤：
（1）找出待排序的数组中最大的元素；
（2）统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
（3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
（4）反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
时间复杂度：Ο(n+k)。
空间复杂度：Ο(k)。
要求：待排序数中最大数值不能太大。
稳定性：稳定。
代码示例：

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
#define MAXNUM 20    //待排序数的最大个数
#define MAX    100   //待排序数的最大值
int sorted_arr[MAXNUM]={0};
//计算排序
//arr:待排序数组，sorted_arr：排好序的数组，n：待排序数组长度
void countSort(int *arr, int *sorted_arr, int n)  
{   
    int i;   
    int *count_arr = (int *)malloc(sizeof(int) * (MAX+1));  
    //初始化计数数组   
    memset(count_arr,0,sizeof(int) * (MAX+1));
    //统计i的次数   
    for(i = 0;i<n;i++)  
        count_arr[arr[i]]++;  
    //对所有的计数累加，作用是统计arr数组值和小于小于arr数组值出现的个数
    for(i = 1; i<=MAX; i++)  
        count_arr[i] += count_arr[i-1];   
    //逆向遍历源数组（保证稳定性），根据计数数组中对应的值填充到新的数组中   
    for(i = n-1; i>=0; i--)  
    {  
        //count_arr[arr[i]]表示arr数组中包括arr[i]和小于arr[i]的总数
        sorted_arr[count_arr[arr[i]]-1] = arr[i];  
        //如果arr数组中有相同的数，arr[i]的下标减一
        count_arr[arr[i]]--;    
    }
    free(count_arr);
}

注意：计数排序是典型的以空间换时间的排序算法，对待排序的数据有严格的要求，比如待排序的数值中不能包含负数，最大值也有限制，请谨慎使用。
2.基数排序
基数排序属于“分配式排序”（distribution sort），是非比较类线性时间排序的一种，又称“桶子法”（bucket sort）。顾名思义，它是透过键值的部分信息，将要排序的元素分配至某些“桶”中，藉以达到排序的作用。
基数排序（以整形为例），将整形10进制按每位拆分，然后从低位到高位依次比较各个位。主要分为两个过程：
　　(1)分配，先从个位开始，根据位值(0-9)分别放到0~9号桶中（比如６4，个位为４，则放入４号桶中）；
　　(2)收集，再将放置在0~9号桶中的数据按顺序放到数组中；
　　重复(1)(2)过程，从个位到最高位（比如32位无符号整形最大数4294967296，最高位为第10位）。基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。
　　平均时间复杂度：O(dn)(d即表示整形的最高位数)。
　　空间复杂度：O(10n) （10表示0~9，用于存储临时的序列） 。
　　稳定性：稳定。
　
（1）MSD法实现
最高位优先法通常是一个递归的过程：

<1>先根据最高位关键码K1排序，得到若干对象组，对象组中每个对象都有相同关键码K1。

<2>再分别对每组中对象根据关键码K2进行排序，按K2值的不同，再分成若干个更小的子组，每个子组中的对象具有相同的K1和K2值。

<3>依此重复，直到对关键码Kd完成排序为止。

<4> 最后，把所有子组中的对象依次连接起来，就得到一个有序的对象序列。

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
77
78
79
80
81
#include<iostream>
#include<malloc.h>
using namespace std;
int getdigit(int x,int d)  
{   
    int a[] = {1, 1, 10};     //因为待排数据最大数据也只是两位数，所以在此只需要到十位就满足
    return ((x / a[d]) % 10);    //确定桶号
}  
void  PrintArr(int ar[],int n)
{
    for(int i = 0; i < n; ++i)
        cout<<ar[i]<<" ";
    cout<<endl;
}
void msdradix_sort(int arr[],int begin,int end,int d)  
{     
    const int radix = 10;   
    int count[radix], i, j; 
    //置空
    for(i = 0; i < radix; ++i)   
    {
        count[i] = 0;   
    }
    //分配桶存储空间
    int *bucket = (int *) malloc((end-begin+1) * sizeof(int));    
    //统计各桶需要装的元素的个数  
    for(i = begin;i <= end; ++i)   
    {
        count[getdigit(arr[i], d)]++;   
    }
    //求出桶的边界索引，count[i]值为第i个桶的右边界索引+1
    for(i = 1; i < radix; ++i)   
    {
        count[i] = count[i] + count[i-1];    
    }
    //这里要从右向左扫描，保证排序稳定性 
    for(i = end;i >= begin; --i)          
    {    
        j = getdigit(arr[i], d);      //求出关键码的第d位的数字， 例如：576的第3位是5   
        bucket[count[j]-1] = arr[i];   //放入对应的桶中，count[j]-1是第j个桶的右边界索引   
        --count[j];                    //第j个桶放下一个元素的位置(右边界索引+1)   
    }   
    //注意：此时count[i]为第i个桶左边界    
    //从各个桶中收集数据  
    for(i = begin, j = 0;i <= end; ++i, ++j)  
    {
        arr[i] = bucket[j]; 
    }       
    //释放存储空间
    free(bucket);   
    //对各桶中数据进行再排序
    for(i = 0;i < radix; i++)  
    {   
        int p1 = begin + count[i];         //第i个桶的左边界   
        int p2 = begin + count[i+1]-1;     //第i个桶的右边界   
        if(p1 < p2 && d > 1)  
        {
            msdradix_sort(arr, p1, p2, d-1);  //对第i个桶递归调用，进行基数排序，数位降 1    
        }
    }  
} 
void  main()
{
    int  ar[] = {12, 14, 54, 5, 6, 3, 9, 8, 47, 89};
    int len = sizeof(ar)/sizeof(int);
    cout<<"排序前数据如下："<<endl;
    PrintArr(ar, len);
    msdradix_sort(ar, 0, len-1, 2);
    cout<<"排序后结果如下："<<endl;
    PrintArr(ar, len);
} 
/*
排序前数据如下：
12 14 54 5 6 3 9 8 47 89
排序后结果如下：
3 5 6 8 9 12 14 47 54 89
 */

（2）LSD法实现
最低位优先法首先依据最低位关键码Kd对所有对象进行一趟排序，
再依据次低位关键码Kd-1对上一趟排序的结果再排序，
依次重复，直到依据关键码K1最后一趟排序完成，就可以得到一个有序的序列。
使用这种排序方法对每一个关键码进行排序时，不需要再分组，而是整个对象组。

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
77
78
#include<iostream>
#include<malloc.h>
using namespace std;
#define   MAXSIZE   10000
int getdigit(int x,int d)  
{   
    int a[] = {1, 1, 10, 100};   //最大三位数，所以这里只要百位就满足了。
    return (x/a[d]) % 10;  
}  
void  PrintArr(int ar[],int n)
{
    for(int i = 0;i < n; ++i)
    {
        cout<<ar[i]<<" ";
    }
    cout<<endl;
}  
void lsdradix_sort(int arr[],int begin,int end,int d)  
{    
    const int radix = 10;   
    int count[radix], i, j; 
    int *bucket = (int*)malloc((end-begin+1)*sizeof(int));  //所有桶的空间开辟   
   
    //按照分配标准依次进行排序过程
    for(int k = 1; k <= d; ++k)  
    {  
        //置空
        for(i = 0; i < radix; i++)  
        {
            count[i] = 0;        
        }               
        //统计各个桶中所盛数据个数
        for(i = begin; i <= end; i++) 
        {
           count[getdigit(arr[i], k)]++;
        }
        //count[i]表示第i个桶的右边界索引
        for(i = 1; i < radix; i++) 
        {
            count[i] = count[i] + count[i-1];
        }
        //把数据依次装入桶(注意装入时候的分配技巧)
        for(i = end;i >= begin; --i)        //这里要从右向左扫描，保证排序稳定性   
        {    
            j = getdigit(arr[i], k);        //求出关键码的第k位的数字， 例如：576的第3位是5   
            bucket[count[j]-1] = arr[i]; //放入对应的桶中，count[j]-1是第j个桶的右边界索引 
            --count[j];               //对应桶的装入数据索引减一  
        } 
        //注意：此时count[i]为第i个桶左边界  
        
        //从各个桶中收集数据
        for(i = begin,j = 0; i <= end; ++i, ++j)  
        {
            arr[i] = bucket[j];    
        }        
    }     
    free(bucket);   
}  
void  main()
{
    int  br[10] = {20, 80, 90, 589, 998, 965, 852, 123, 456, 789};
    cout<<"原数据如下："<<endl;
    PrintArr(br,10);
    lsdradix_sort(br, 0, 9, 3);
    cout<<"排序后数据如下："<<endl;
    PrintArr(br, 10);
}
/*
原数据如下：
20 80 90 589 998 965 852 123 456 789
排序后数据如下：
20 80 90 123 456 589 789 852 965 998
*/

3.桶排序
桶排序也是分配排序的一种，但其是基于比较排序的，这也是与基数排序最大的区别所在。
思想：桶排序算法想法类似于散列表。首先要假设待排序的元素输入符合某种均匀分布，例如数据均匀分布在[ 0,1）区间上，则可将此区间划分为10个小区间，称为桶，对散布到同一个桶中的元素再排序。
要求：待排序数长度一致。
排序过程：
（1）设置一个定量的数组当作空桶子；
（2）寻访序列，并且把记录一个一个放到对应的桶子去；
（3）对每个不是空的桶子进行排序。
（4）从不是空的桶子里把项目再放回原来的序列中。
时间复杂度：
对N个关键字进行桶排序的时间复杂度分为两个部分：
(1) 循环计算每个关键字的桶映射函数，这个时间复杂度是O(N)。
(2) 利用先进的比较排序算法对每个桶内的所有数据进行排序，对于N个待排数据，M个桶，平均每个桶[N/M]个数据，则桶内排序的时间复杂度为O(N*log2(N/M))。
因此，平均时间复杂度为线性的O(N+C)，C为桶内排序所花费的时间。当每个桶只有一个数，则最好的时间复杂度为：O(N)。

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
typedef struct node
 { 
     int keyNum;//桶中数的数量
     int key;   //存储的元素
     struct node * next;  
 }KeyNode;    
 //keys待排序数组，size数组长度，bucket_size桶的数量
 void inc_sort(int keys[],int size,int bucket_size)
 { 
     KeyNode* k=(KeyNode *)malloc(sizeof(KeyNode)); //用于控制打印
     int i,j,b;
     KeyNode **bucket_table=(KeyNode **)malloc(bucket_size*sizeof(KeyNode *)); 
     for(i=0;i<bucket_size;i++)
     {  
         bucket_table[i]=(KeyNode *)malloc(sizeof(KeyNode)); 
         bucket_table[i]->keyNum=0;//记录当前桶中是否有数据
         bucket_table[i]->key=0;   //记录当前桶中的数据  
         bucket_table[i]->next=NULL; 
     }    
     for(j=0;j<size;j++)
     {   
         int index;
         KeyNode *p;
         KeyNode *node=(KeyNode *)malloc(sizeof(KeyNode));   
         node->key=keys[j];  
         node->next=NULL;  
         index=keys[j]/10;        //映射函数计算桶号  
         p=bucket_table[index];   //初始化P成为桶中数据链表的头指针  
         if(p->keyNum==0)//该桶中还没有数据 
         {    
             bucket_table[index]->next=node;    
             (bucket_table[index]->keyNum)++;  //桶的头结点记录桶内元素各数，此处加一
         }
         else//该桶中已有数据 
         {   
             //链表结构的插入排序 
             while(p->next!=NULL&&p->next->key<=node->key)   
                 p=p->next;    
             node->next=p->next;     
             p->next=node;      
             (bucket_table[index]->keyNum)++;   
         }
     }
     //打印结果
     for(b=0;b<bucket_size;b++)   
         //判断条件是跳过桶的头结点，桶的下个节点为元素节点不为空
         for(k=bucket_table[b];k->next!=NULL;k=k->next)  
         {
             printf("%d ",k->next->key);
         }
 }

番外

开头那道题的题解。。

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
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 10005;
#define ll long long
int a[maxn];
int b[maxn];
int m, n, k;
int getsum(int x)
{
    int l = 0, r = n - 1;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (b[mid] <= x)
            l = mid + 1;
        else
            r = mid - 1;
    }
    return l;
}
bool check(int x)
{
    ll ans = 0;
    for (int i = 0; i < m; i++)
    {
            if (!a[i])// 如果a[i] 是0的话 那么这一排m必取
            {
                ans += n;
                continue;
            }
            int cnt = x / a[i];//a[i]* cnt=x; 求最大的cnt 其他比
            //cnt小的 都要加起来
            ans += getsum(cnt);//在b里找 比cnt小的
    }
     return ans >= k;
}
int main()
{
    scanf("%d %d %d",&m,&n,&k);
    for(int i=0;i<m;i++) scanf("%d",&a[i]);
    for(int i=0;i<n;i++) scanf("%d",&b[i]);
    sort(a,a+m);
    sort(b,b+n);
    int l = 0;
    int r = a[m-1]*b[n-1];
    while(l<=r)
    {
        int mid = (l+r)>>1;
        if(check(mid)) r = mid-1;
        else l = mid+1;
    }
    cout << l << endl;
}

另外，在C++的STL中封装了一个叫优先队列的东西，它的实现原理和堆非常类似，可以直接使用。
优先队列：
顾名思义，首先它是一个队列，但是它强调了“优先”二字，所以，已经不能算是一般意义上的队列了，它的“优先”意指取队首元素时，有一定的选择性，即根据元素的属性选择某一项值最优的出队~
百度百科上这样描述的：
　　优先级队列 是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素
　　优先队列的类定义　　
　　优先队列是0个或多个元素的集合,每个元素都有一个优先权或值,对优先队列执行的操作有1) 查找;2) 插入一个新元素;3) 删除.在最小优先队列(min priorityq u e u e)中,查找操作用来搜索优先权最小的元素,删除操作用来删除该元素;对于最大优先队列(max priority queue),查找操作用来搜索优先权最大的元素,删除操作用来删除该元素.优先权队列中的元素可以有相同的优先权,查找与删除操作可根据任意优先权进行.
其声明格式为：priority_queue ans;//声明一个名为ans的整形的优先队列
基本操作有：
empty( ) //判断一个队列是否为空
pop( ) //删除队顶元素
push( ) //加入一个元素
size( ) //返回优先队列中拥有的元素个数
top( ) //返回优先队列的队顶元素

优先队列的时间复杂度为O（logn），n为队列中元素的个数，其存取都需要时间。

在默认的优先队列中，优先级最高的先出队。默认的int类型的优先队列中先出队的为队列中较大的数。

然而更多的情况下，我们是希望可以自定义其优先级的，下面介绍几种常用的定义优先级的操作：

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
/*优先队列的基本使用    2010/7/24    dooder*/  
#include<stdio.h>  
#include<functional>  
#include<queue>  
#include<vector>  
using namespace std;  
//定义结构，使用运算符重载,自定义优先级1  
struct cmp1{  
    bool operator ()(int &a,int &b){  
        return a>b;//最小值优先  
    }  
};  
struct cmp2{  
    bool operator ()(int &a,int &b){  
        return a<b;//最大值优先  
    }  
};  
//定义结构，使用运算符重载,自定义优先级2  
struct number1{  
    int x;  
    bool operator < (const number1 &a) const {  
        return x>a.x;//最小值优先  
    }  
};  
struct number2{  
    int x;  
    bool operator < (const number2 &a) const {  
        return x<a.x;//最大值优先  
    }  
};  
int a[]={14,10,56,7,83,22,36,91,3,47,72,0};  
number1 num1[]={14,10,56,7,83,22,36,91,3,47,72,0};  
number2 num2[]={14,10,56,7,83,22,36,91,3,47,72,0};  
  
int main()  
{   priority_queue<int>que;//采用默认优先级构造队列  
  
    priority_queue<int,vector<int>,cmp1>que1;//最小值优先  
    priority_queue<int,vector<int>,cmp2>que2;//最大值优先  
  
    priority_queue<int,vector<int>,greater<int> >que3;//注意“>>”会被认为错误，  
                                                      //这是右移运算符，所以这里用空格号隔开  
    priority_queue<int,vector<int>,less<int> >que4;////最大值优先  
  
    priority_queue<number1>que5;  
    priority_queue<number2>que6;  
  
    int i;  
    for(i=0;a[i];i++){  
        que.push(a[i]);  
        que1.push(a[i]);  
        que2.push(a[i]);  
        que3.push(a[i]);  
        que4.push(a[i]);  
    }  
    for(i=0;num1[i].x;i++)  
        que5.push(num1[i]);  
    for(i=0;num2[i].x;i++)  
        que6.push(num2[i]);  
  
  
    printf("采用默认优先关系:\n(priority_queue<int>que;)\n");  
    printf("Queue 0:\n");  
    while(!que.empty()){  
        printf("%3d",que.top());  
        que.pop();  
    }  
    puts("");  
    puts("");  
  
    printf("采用结构体自定义优先级方式一:\n(priority_queue<int,vector<int>,cmp>que;)\n");  
    printf("Queue 1:\n");  
    while(!que1.empty()){  
        printf("%3d",que1.top());  
        que1.pop();  
    }  
    puts("");  
    printf("Queue 2:\n");  
    while(!que2.empty()){  
        printf("%3d",que2.top());  
        que2.pop();  
    }  
    puts("");  
    puts("");  
    printf("采用头文件\"functional\"内定义优先级:\n(priority_queue<int,vector<int>,greater<int>/less<int> >que;)\n");  
    printf("Queue 3:\n");  
    while(!que3.empty()){  
        printf("%3d",que3.top());  
        que3.pop();  
    }  
    puts("");  
    printf("Queue 4:\n");  
    while(!que4.empty()){  
        printf("%3d",que4.top());  
        que4.pop();  
    }  
    puts("");  
    puts("");  
    printf("采用结构体自定义优先级方式二:\n(priority_queue<number>que)\n");  
    printf("Queue 5:\n");  
    while(!que5.empty()){  
        printf("%3d",que5.top());  
        que5.pop();  
    }  
    puts("");  
    printf("Queue 6:\n");  
    while(!que6.empty()){  
        printf("%3d",que6.top());  
        que6.pop();  
    }  
    puts("");  
    return 0;  
}  
/* 
运行结果 ： 
采用默认优先关系: 
(priority_queue<int>que;) 
Queue 0: 
83 72 56 47 36 22 14 10  7  3 
 
采用结构体自定义优先级方式一: 
(priority_queue<int,vector<int>,cmp>que;) 
Queue 1: 
 7 10 14 22 36 47 56 72 83 91 
Queue 2: 
83 72 56 47 36 22 14 10  7  3 
 
采用头文件"functional"内定义优先级: 
(priority_queue<int,vector<int>,greater<int>/less<int> >que;) 
Queue 3: 
 7 10 14 22 36 47 56 72 83 91 
Queue 4: 
83 72 56 47 36 22 14 10  7  3 
 
采用结构体自定义优先级方式二: 
(priority_queue<number>que) 
Queue 5: 
 7 10 14 22 36 47 56 72 83 91 
Queue 6: 
83 72 56 47 36 22 14 10  7  3 
*/  
运行结果：
采用默认优先关系:
(priority_queue<int>que;)
Queue 0:
83 72 56 47 36 22 14 10  7  3
采用结构体自定义优先级方式一:
(priority_queue<int,vector<int>,cmp>que;)
Queue 1:
 7 10 14 22 36 47 56 72 83 91
Queue 2:
83 72 56 47 36 22 14 10  7  3
采用头文件"functional"内定义优先级:
(priority_queue<int,vector<int>,greater<int>/less<int> >que;)
Queue 3:
 7 10 14 22 36 47 56 72 83 91
Queue 4:
83 72 56 47 36 22 14 10  7  3
采用结构体自定义优先级方式二:
(priority_queue<number>que)
Queue 5:
 7 10 14 22 36 47 56 72 83 91
Queue 6:
83 72 56 47 36 22 14 10  7  3

引用：

https://www.cnblogs.com/eniac12/p/5329396.html#s4
http://blog.csdn.net/k346k346/article/details/50791102
https://www.cnblogs.com/Braveliu/archive/2013/01/21/2870201.html
http://blog.csdn.net/qq_36553623/article/details/72809695
http://www.cnblogs.com/heqinghui/archive/2013/07/30/3225407.html