复杂排序

简单排序的时间复杂度都是o(



n

2

n^2







n










2












)，在很长一段时间里充斥着“排序算法不可能突破o(



n

2

n^2







n










2












)”的声音。但最终还是有科学家将排序算法的时间复杂度提升至o(nlogn)。

希尔排序

希尔排序是在直接插入排序的基础上进行改进并提升效率。

基本思想：直接插入排序是简单排序算法中比较高效的算法，当初始序列长度较短或基本有序时，效果很好。希尔排序则是将原本有大量元素的序列进行按一定长度进行分组，分成若干个子序列。此时每个子序列的元素数就比较少了，然后在这些子序列内分别进行直接插入排序，当整个序列都基本有序时，再对整个序列进行一次直接插入排序。

所谓基本有序是指小的关键字基本在前面，大的关键字基本在后面，其余的在中间。例如，像[2，1，3，6，4，7，5，8，9]就是基本有序，而[1，5，9，3，7，8，2，4，6]这样的就不是基本有序。

希尔排序在分组时，采用跳跃分割的策略：根据算出的“增量（increment）”，相距某个“增量”的元素组成一个子序列，这样才能保证子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。因为要在最后再进行一次整个序列的直接插入排序，因此在计算increment的时候，要保证最终的increment=1。

由于希尔排序是跳跃式移动的，因此希尔排序并不是一种稳定的排序算法。

堆排序

堆排序是简单选择排序的改进。在简单选择排序中，并没有将每一趟的比较结果保存下来，在后一趟的比较中，有许多比较在前一趟已经做过了，但由于没有记录，后一趟又重复执行了这些比较操作，导致性能的浪费。

堆是具有下列性质的完全二叉树：每个结点的值都大于等于其左右孩子结点的值，这样的堆被称为大顶堆，小顶堆同理。对于序号为i的结点，其左右孩子的结点序号分别为：2i和2i+1。

基本思想：将代排序的n个结点序列构造成一个大顶堆。此时序列的最大值就是堆顶的根节点。将它与堆数组的最后一个元素进行交换，然后重新对堆数组的前n-1个元素进行重构大顶端，重复以上操作，便可以得到一个有序序列。

由于堆排序的比较与交换也是跳跃的，因此堆排序也是一种不稳定的排序算法。

归并排序

基本思想：假设原始序列含有n个元素，则可以看成n个有序的子序列，每个子序列的长度为1，然后再两两归并，得到ceil(n/2)个长度为2或1的有序子序列；再两两归并，如此重复，直到得到一个长度为n的有序序列为止。该方法被称为2路归并排序。

归并排序有递归实现版本，也有迭代实现版本。但由于递归版本会造成大量的时间和空间上的性能损耗，因此尽量考虑吧非递归版本。

由于归并排序算法需要两两比较，不存在跳跃，因此归并排序是一种稳定的排序算法。

快速排序

快速排序是冒泡排序的升级，它们都属于交换排序类，即通过不断比较和移动交换来实现排序的。只不过快速排序的实现，增大了元素的比较和移动距离，将关键字较大的元素从前面直接移动到后面，关键字较小的元素直接从后面移动到前面，从而减少了总的比较次数和移动交换次数。

基本思想：通过选择出一个关键字作为中间关键字，然后将该序列中的所有比中间关键字小的元素移动到中间关键字的前面，比中间关键字大的元素移动到后面。然后再分别对这两部分继续进行排序，以达到整个序列排序的目的。

总结

并不存在十全十美的算法，每次在使用时，要具体问题具体分析。

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

从最好情况来看，反而冒泡和直接插入排序要更好些。也就是在原始序列基本有序的情况下，简单排序效果就很好。

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

并且待排序的元素个数n越小的情况下，采用简单排序方法越合适。反之，n越大，采用复杂排序更合适。

代码实现

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 100

typedef struct SqList
{
    int data[MAXSIZE + 1];
    int length;
} SqList;

void SwapData(SqList *L, int i, int j)
{
    int temp = L->data[i];
    L->data[i] = L->data[j];
    L->data[j] = temp;
}

void ShellSort(SqList *L)
{
    int increment = L->length;
    do
    {
        increment = increment / 3 + 1; // 增量是根据先前经验选出的
        for (int i = increment + 1; i <= L->length; i++)
        {
            if (L->data[i] < L->data[i - increment])
            {
                L->data[0] = L->data[i];
                int j;
                for (j = i - increment; j > 0 && L->data[0] < L->data[j]; j -= increment)
                {
                    L->data[j + increment] = L->data[j];
                }
                L->data[j + increment] = L->data[0];
            }
        }
    } while (increment > 1);
}

// s为需要对第几个节点进行重构， len为参与重构的元素的个数
void HeapAdjust(SqList *L, int s, int len)
{
    int temp = L->data[s];
    for (int i = 2 * s; i <= len; i *= 2)
    {
        if (i < len && L->data[i] < L->data[i + 1])
        {
            i++;
        }
        if (temp > L->data[i])
        {
            break;
        }
        L->data[s] = L->data[i];
        s = i;
    }
    L->data[s] = temp;
}

void HeapSort(SqList *L)
{
    for (int i = L->length / 2; i > 0; i--)
    {
        HeapAdjust(L, i, L->length); // 构建大顶堆
    }

    for (int i = L->length; i > 1; i--)
    {
        SwapData(L, 1, i);       // 将第一个元素（最大值）交换至索引最后一个
        HeapAdjust(L, 1, i - 1); // 重新构建大顶端
    }
}

void Merge(int sourceData[], int targetData[], int low, int mid, int high)
{
    int i = low, j = mid + 1, k = low;
    for (; i <= mid && j <= high; k++)
    {
        if (sourceData[i] < sourceData[j])
            targetData[k] = sourceData[i++];
        else
            targetData[k] = sourceData[j++];
    }

    for (int l = 0; l <= mid - i; l++)
    {
        targetData[k + l] = sourceData[i + l]; // 将剩余的sourceData[i, .., mid]复制到targetData中
    }
    for (int l = 0; l <= high - j; l++)
    {
        targetData[k + l] = sourceData[j + l]; // 将剩余的sourceData[j, .., high]复制到targetData中
    }
}

// 最终目标是将targetData1中的数组按顺序排好
void MSort(int sourceData[], int targetData1[], int low, int high)
{
    int targetData2[MAXSIZE + 1] = {0};
    if (low == high)
    {
        targetData1[low] = sourceData[low];
    }
    else
    {
        int mid = (low + high) / 2;
        MSort(sourceData, targetData2, low, mid);        // 递归地将sourceData[low, .., mid]归并为有序的targetData2[low, .., mid]
        MSort(sourceData, targetData2, mid + 1, high);   // 递归将sourceData[mid+1, .., high]归并为有序的targetData2[mid+1, .., high]
        Merge(targetData2, targetData1, low, mid, high); // 将targetData2[low, .., mid]和targetData2[mid+1, .., high]归并到targetData1[low, ..,  high]
    }
}

// 递归版
void MergeSort1(SqList *L)
{
    MSort(L->data, L->data, 1, L->length);
}

// 将sourceData中相邻长度为k的子序列两两归并到targetData中
void MergePass(int sourceData[], int targetData[], int k, int high)
{
    int i;
    for (i = 1; i <= high - 2 * k + 1; i += 2 * k)
    {
        Merge(sourceData, targetData, i, i + k - 1, i + 2 * k - 1);
    }
    if (i < high - k + 1)
    {
        Merge(sourceData, targetData, i, i + k - 1, high);
    }
    else
    {
        for (int j = i; j <= high; j++)
        {
            targetData[j] = sourceData[j];
        }
    }
}

// 迭代版
void MergeSort2(SqList *L)
{
    int *targetData = (int *)malloc(sizeof(int) * L->length);
    int k = 1;
    while (k < L->length)
    {
        MergePass(L->data, targetData, k, L->length);
        k *= 2;
        MergePass(targetData, L->data, k, L->length);
        k *= 2;
    }
}

int Partition(SqList *L, int low, int high)
{
    // 使用三点(首、尾、中)取中法求出一个中间值
    int mid = (low + high) / 2;
    if (L->data[low] > L->data[high])
    {
        SwapData(L, low, high);
    }
    if (L->data[mid] > L->data[high])
    {
        SwapData(L, mid, high);
    }
    if (L->data[mid] > L->data[low])
    {
        SwapData(L, mid, low);
    }
    int midKey = L->data[low];

    while (low < high)
    {
        while (low < high && L->data[high] >= midKey)
        {
            high--;
        }
        L->data[low] = L->data[high];
        while (low < high && L->data[low] <= midKey)
        {
            low++;
        }
        L->data[high] = L->data[low];
    }
    L->data[low] = midKey;
    return low;
}

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

void QuickSort(SqList *L)
{
    QSort(L, 1, L->length);
}

int main()
{
    int a[10] = {2, 6, 4, 23, 15, 9, 45, 3, 5, 11};
    SqList *L = (SqList *)malloc(sizeof(SqList));
    for (int i = 0; i < 10; i++)
    {
        L->data[i + 1] = a[i];
    }
    L->length = 10;

    // 希尔排序
    // ShellSort(L);
    // 堆排序
    // HeapSort(L);
    // 归并排序（递归版）
    // MergeSort1(L);
    // 归并排序（迭代版）
    // MergeSort2(L);
    // 快速排序
    // QuickSort(L);

    for (int i = 1; i <= L->length; i++)
    {
        printf("%d ", L->data[i]);
    }
    return 0;
}