void ShellSort(SqList *L)
{
    int i , j;
    int increment = L->length;
    do
    {
        increment = increment / 3 + l;
        for (i = increment + l; i <= L->length; i++)
            if (L->r[i] < L->r[i - increment])
            {
                L->r[0] - L->r[i];
                for (j - (i - increment); j > 0 && L->r[0] < L->r[j]; j <= increment)
                    L->r[j + increment] = L->r[j]; /*记录后移，查找插入位置 */
                L->r[j + increment] = L->r[0];     /* 插入 */
            }
    } while (increment > l);
}

3.5 堆排序

堆排序（Heap Sort）就是利用堆（假设利用大顶堆）进行排序的方法。它的基本思想是，将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根 结点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次小值。如此反复执行，便能得到一个有序序列了。

void HeapSort(SqList *L)
{
    int i;
    for (i = L->length / 2; i > 0; i--)
        HeapAdj ust(L, i, L->length);
    for (i = L->length; i > l; i--)
    {
        swap(L.l, i);
        HeapAdjust(L, lri - 1);
    }
}

3.6 归并排序

归并” 一词的中文含义就是合并、并入的意思，而在数据结构中的定义是将两个 或两个以上的有序表组合成一个新的有序表。

归并排序(Merging Sort)就是利用归并的思想实现的排序方法。它的原理是假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1,然后两两归并，得到[n/2]?(［x］表示不小于x的最小整数)个长度为2或1的有 序子序列；再两两归并，……,如此重复，直至得到一个长度为n的有序序列为止， 这种排序方法称为2路归并排序。

void MSort(int SR[], int TRI[], int s, int t)
{
    int m;
    int TR2[MAXSIZE + 1];
    if (s == t)
        TRl[s] = SR[s];
    else
    {
        m = (s + t) / 2;
        MSort(SR, TR2, s, m);
        MSort(SR, TR2, m + 1, t);
        Merge(TR2, TR1, s, m, t); /*将TR2[s.?m]和TR2[m+1..仁]*/
    }
}

3.7 快速排序

快速排序(Quick Sort)的基本思想是：通过一趟排序将待排记录分割成独立的 两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部 分记录继续进行排序，以达到整个序列有序的目的。

void QSort(SqList *Lr, int low, int high)
{
    int pivot;
    if (low < high)
    {
        pivot = Partition(L, low, high);
        QSort(L, low, pivot - 1);
        QSort(L, pivot + 1, high);
    }
}

4 总结回顾

本章文只是在讲排序，我们需要对已经提到的各个排序算法进行对比来总结回 顾。

首先我们讲了排序的定义，并提到了排序的稳定性，排序稳定对于某些特殊需求 来说是至关重要的，因此在排序算法中，我们需要关注此算法的稳定性如何。

我们根据将排序记录是否全部被放置在内存中，将排序分为丙排序与外排序两 种，外排序需要在内外存之间多次交换数据才能进行。我们本章主要讲的是内排序的 算法。

根据排序过程中借助的主要操作，我们将内排序分为：插入排序、交换排序、选 择排序和归并排序四类。之后介绍的7种排序法，就分别是各种分类的代表算法。

?我们对各种排序方法进行总结，对比。

通过这个表，我们直接的能进行下列的分析：

从算法的简单性来看，我们将7种算法分为两类：

• 简单算法：冒泡、简单选择、直接插入。
• 改进算法：希尔、堆、归并、快速。

从平均情况来看，显然最后3种改进算法要胜过希尔排序，并远远胜过前3种简 单算法。

从最好情况看，反而冒泡和直接插入排序要更胜一筹，也就是说，如果你的待排 序序列总是基本有序，反而不应该考虑4种复杂的改进算法。

从最坏情况看，堆排序与归并排序又强过快速排序以及其他简单排序。

从这三组时间复杂度的数据对比中，我们可以得出这样一个认识。堆排序和归并 排序就像两个参加奥数考试的优等生，心理素质强，发挥稳定。而快速排序像是很情 绪化的天才，心情好时表现极佳，碰到较糟糕环境会变得差强人意。但是他们如果都 来比赛计算个位数的加减法，它们反而算不过成绩极普通的冒泡和直接插入。

从空间复杂度来说，归并排序强调要马跑得快，就得给马吃个饱。快速排序也有 相应的空间要求，反而堆排序等却都是少量索取，大量付出，对空间要求是0(1)。如 果执行算法的软件所处的环境非常在乎内存使用量的多少时，选择归并排序和快速排 序就不是一个较好的决策了。

从稳定性来看，归并排序独占鳌头，我们前面也说过，对于非常在乎排序稳定性 的应用中，归并排序是个好算法。

从待排序记录的个数上来说，待排序的个数n越小，采用简单排序方法越合适。 反之，n越大，采用改进排序方法越合适。这也就是我们为什么对快速排序优化时， 增加了一个阀值，低于阀值时换作直接插入排序的原因。

5 例题介绍

我们可以使用基于快速排序的方法，求出「出现次数数组」的前k大的值。
在对数组arr[做快速排序的过程中，我们首先将数组划分为两个部分arri...q-1]与arrq+1.j，并使得arriq-1中的每一个值都不超过arr[q]，且arrq+1..j]中的每一个值都大于arrg]。于是，我们根据k与左侧子数组arri...q-1]的长度(为q-i)的大小关系:
·如果k≤q-i，则数组arrl...r]前k大的值，就等于了数组arri...q-1前k大的值。
。否则，数组arrlr]前k大的值，就等于左侧子数组全部元素，加上右侧了数组arrq+1...jj中前?k-(q-i)大的值。
原版的快速排序算法的平均时间复杂度为O(NlogN)。我们的算法中，每次只需在其中的一个分支递归即可，因此算法的平均时间复杂度降为O(N)。

代码如下：

#include <bits/stdc++.h>
using namespace std;
struct hash_table
{
    int key;
    int val;
    UT_hash_handle hh;
};

typedef struct hash_table *hash_ptr;

struct pair
{
    int first;
    int second;
};

void swap(struct pair *a, struct pair *b)
{
    struct pair t = *a;
    *a = *b, *b = t;
}

void sort(struct pair *v, int start, int end, int *ret, int *retSize, int k)
{
    int picked = rand() % (end - start + 1) + start;
    swap(&v[picked], &v[start]);

    int pivot = v[start].second;
    int index = start;
    for (int i = start + 1; i <= end; i++)
    {
        if (v[i].second >= pivot)
        {
            swap(&v[index + 1], &v[i]);
            index++;
        }
    }
    swap(&v[start], &v[index]);

    if (k <= index - start)
    {
        sort(v, start, index - 1, ret, retSize, k);
    }
    else
    {
        for (int i = start; i <= index; i++)
        {
            ret[(*retSize)++] = v[i].first;
        }
        if (k > index - start + 1)
        {
            sort(v, index + 1, end, ret, retSize, k - (index - start + 1));
        }
    }
}

int *topKFrequent(int *nums, int numsSize, int k, int *returnSize)
{
    hash_ptr head = NULL;
    hash_ptr p = NULL, tmp = NULL;

    for (int i = 0; i < numsSize; i++)
    {
        HASH_FIND_INT(head, &nums[i], p);
        if (p == NULL)
        {
            p = malloc(sizeof(struct hash_table));
            p->key = nums[i];
            p->val = 1;
            HASH_ADD_INT(head, key, p);
        }
        else
        {
            p->val++;
        }
    }
    struct pair values[numsSize];
    int valuesSize = 0;

    HASH_ITER(hh, head, p, tmp)
    {
        values[valuesSize].first = p->key;
        values[valuesSize++].second = p->val;
    }
    int *ret = malloc(sizeof(int) * k);
    *returnSize = 0;
    sort(values, 0, valuesSize - 1, ret, returnSize, k);
    return ret;
}

6 文章结尾

本篇主要详述了排序算法的概要以及排序算法在相关竞赛的应用。陆续会更新其他竞赛中常用的一些知识点。

7 文件分享?

如果大家需要Word或者PDF版本，使用以下链接。

链接：https://pan.baidu.com/s/1ZE0VwwFqTdbk7WyMAUZ3aA?
提取码：lh91