排序算法（一）

排序是我们在程序中经常用到的算法之一，接下来的两篇博客就将对常见的排序算法进行总结、实现、评价。

在此之前，先补充一个概念——

稳定性：如果排序后原来关键字相同的元素的相对顺序不变，则称此排序算法是稳定的，否则不稳定。

一、插入排序

1.直接插入排序

（1）基本思想

把待排序的元素按照关键值的大小依次插入到一个已经有序的有序序列中，直到所有元素都插入完毕即可得到该组元素的有序序列。

（2）代码实现（升序）

void InsertSort(int* a, int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        int end = i;
        int tmp = a[end + 1];
        while (end >= 0)
        {
            if (tmp < a[end])  //
            {
                a[end + 1] = a[end];
                end--;
            }
            else
                break;
        }
        a[end + 1] = tmp;
    }

}

（3）分析

每次插入元素时，所需移动次数最少为0，最多为已经有序的元素个数（从0到n-1），因此该算法的时间复杂度为

不需要额外的空间，空间复杂度为

从上面代码可以看出，在进行大小比较时，如果相等，也会退出循环，不再继续移动元素，保证了二者的相对次序不变，因此该算法稳定。（当然，如果把<改为<=，这样算法依然可以实现排序功能，但是不稳定了。尽管如此，我们在实现该算法时还是可以让其成为稳定的，因此我们认为该算法是稳定的。下面的其他稳定性的算法与此同理。从中也可以看出，我们更希望一个排序算法是稳定的。）

元素集合越接近有序，直接插入排序的时间效率就越高。

2.希尔排序

（1）基本思想

选取一个整数gap，把所有元素分成gap组：相距gap的元素为一组，并对每组元素都进行直接插入排序。然后逐步缩小gap，重复上述操作，直到gap=1时，进行直接插入排序后便可得到有序序列。（如有疑问，请看分析部分）

（2）代码实现（升序）

关于gap的取法有很多种，本代码gap从n开始逐渐减半，直到gap=1结束。（不论gap怎么取，最终的gap必须等于1）

void ShellSort(int* a, int n)
{
    int gap = n;
    while (gap > 1)
    {
        gap /= 2;
        for (int i = 0; i < n - gap; i++)
        {
            int end = i;
            int tmp = a[end + gap];
            while (end >= 0)
            {
                if (tmp < a[end])  //
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                    break;
            }
            a[end + gap] = tmp;
        }
    }
}

（3）分析

既然最后一次也要全部进行直接插入排序，为什么还要提前进行多次的分组插入排序呢？直接插入排序的时间复杂度为，而且元素越无序，越接近，元素越有序，越接近1。提前进行多次分组插入排序可以让元素的排列逐渐趋向有序，这样时间效率会越来越高，因此希尔排序的时间复杂度也会比直接插入排序小。可以说，希尔排序是对直接插入排序的优化。

那么希尔排序的时间复杂度是多少呢？这是一个复杂的问题，因为它的时间是所取距离gap的函数，这涉及一些数学上尚未解决的难题，经过大量的实验，目前认为希尔排序的时间复杂度约为。

不需要额外空间，空间复杂度为。

在分组插入排序的过程中，相同的元素可能分到不同的组别，进而导致各自排序后其相对次序可能改变，因此希尔排序不稳定。

二、选择排序

基本思想

每次从待排序的数据元素中挑选出最小或最大的一个元素，存放在序列的起始或末端位置，直到所有元素有序为止。

1.简单选择排序

该算法应该是C语言入门阶段就应该了解熟知的排序算法，不再过多介绍。

（1）代码实现（升序）

void Swap(int* x, int* y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

void SelectSort(int* a, int n)
{
    for (int i = 0; i < n-1; i++)
    {
        int mini = i;
        for (int j = i + 1; j < n; j++)
        {
            if (a[j] < a[mini])  //
                mini = j;
        }
        if (mini != i)
            Swap(a + i, a + mini);
    }
}

（2）分析

时间复杂度为

空间复杂度为

该算法不稳定。

简单选择排序效率太低，实际中很少使用。

2.堆排序

堆排序是通过建堆来挑选最大或最小的元素的。升序建大堆，降序建小堆。有关堆的细节可以查看上篇博客【堆的实现及应用】。

（1）代码实现（升序）

void Swap(int* x, int* y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

void AdjustDown(int* a, int size, int parent)
{
    int child = parent * 2 + 1;
    while (child < size)
    {
        if (child + 1 < size && a[child + 1] > a[child])  //
        {
            child++;
        }
        if (a[child] > a[parent])  //
        {
            Swap(a + child, a + parent);
            parent = child;
            child = child * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

void HeapSort(int* a, int n)
{
    for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(a, n, i);
    }

    int index_end = n - 1;
    while (index_end > 0)
    {
        Swap(a, a + index_end);
        AdjustDown(a, index_end, 0);
        index_end--;
    }
}

（2）分析

单次向下调整的时间复杂度为O(n)，堆排序的时间复杂度为

不需要额外空间，空间复杂度为

在建堆过程中相同的元素其相对次序会改变，堆排序不稳定