C 语言实现八大排序算法详解

代码中标明了要点，以下是说明：

要点 1：由于 tmp=arr[end+1],所以 end 最大只能是 n-2，否则越界访问

要点 2：防止因为 tmp 需要一直调到最前面，导致 end=-1，使得循环终止，那 tmp 就没有进行插入，所以我们将 arr[end+1] = tmp;写在内层循环的外部。

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高，当数组是倒序时，需要的时间最长
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

2.2 希尔排序

希尔排序是按其设计者希尔的名字命名的，该算法由希尔 1959 年公布。希尔可以说是一个脑洞非常大的人，他对普通插入排序的时间复杂度进行分析，得出了以下结论：

1.普通插入排序的时间复杂度最坏情况下为 O(N2)，此时待排序列为逆序，或者说接近逆序。

2.普通插入排序的时间复杂度最好情况下为 O(N)，此时待排序列为升序，或者说接近升序。

希尔就想若是能先将待排序列进行一次预排序，使待排序列接近有序（接近我们想要的顺序），然后再对该序列进行一次直接插入排序。因为此时直接插入排序的时间复杂度为 O(N)，那么只要控制预排序阶段的时间复杂度不超过 O(N2)，那么整体的时间复杂度就比直接插入排序的时间复杂度低了。

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成对应个组，所有距离为 gap 的记录分在同一组内，并对每一组内的记录进行排序。然后，取 gap=gap/3+1，重复上述分组和排序的工作。当到达 gap=1 时，所有记录在统一组内排好序。

希尔排序特性总结：

1.希尔排序是对直接插入的优化

2.当 gap > 1 时都是预排序，目的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比

3. 希尔排序的时间复杂度不好计算，因为 gap 的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定，我们常用的是令 gap=gap/3+1;

问题：为什么要让 gap 由大到小呢？ answer：gap 越大，数据挪动得越快；gap 越小，数据挪动得越慢。前期让 gap 较大，可以让数据更快得移动到自己对应的位置附近，减少挪动次数。

我们先尝试进行一次 gap 分组排序：

int gap = 5;
for (int i = 0;i < n - gap;i++)
{
    int end = i;
    int tmp = arr[end + gap];
    while (end >= 0)
    {
        if (arr[end] > tmp)
        {
            arr[end + gap] = arr[end];
            end -= gap;
        }
        else
        {
            break;
        }
    }
    arr[end + gap] = tmp;
}

这是令 gap=5，进行的一次排序，那我们只需要再加上一次循环，保证 gap 最后为 1，就可以实现希尔排序了，以下是完整代码：

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

希尔排序的时间复杂度很难准确计算出来，大概是 O(N^1.3),不稳定

3. 选择排序

3.1 直接选择排序

选择排序，即每次从待排序列中选出一个最小值，然后放在序列的起始位置，直到全部待排数据排完即可。

代码展示：

void SelectSort(int* arr, int n)
{
    int begin = 0, end = n - 1;
    while (begin < end)
    {
        int pmin = begin;
        for (int i = begin;i <n;i++)
        {
            if (arr[i] < arr[pmin])
            {
                pmin = i;
            }
        }
        Swap(&arr[begin], &arr[pmin]);
        begin++;
    }
}

实际上，我们可以一趟选出两个值，一个最大值 一个最小值，然后将其放在序列开头和末尾，这样可以使选择排序的效率快一倍。

代码实现：

void SelectSort(int* arr, int n)
{
    int begin = 0, end = n - 1;
    while (begin < end)
    {
        int pmax = begin, pmin = end;
        for (int i = begin;i <= end;i++)
        {
            if (arr[i] > arr[pmax]) pmax = i;
            if (arr[i] < arr[pmin]) pmin = i;
        }
        Swap(&arr[begin], &arr[pmin]);
        if (pmax == begin)////防止最大值位于序列开头，被最小值交换
            pmax = pmin;
        Swap(&arr[end], &arr[pmax]);
        begin++;
        pmin--;
    }
}

时间复杂度：O(N^2),稳定性：不稳定

4.2 堆排序

在之前的学习中，我们已经讲到过堆排序，要实现堆排序，首先要学会建堆，建堆就需要用到向下调整算法，那我们从向下调整算法开始说起。

向下调整算法起初被我们用于堆的删除函数，堆的根节点不符合堆的结构，但是其左右子树完全符合，所以需要将根节点向下调整。那么可以知道向下调整算法的前提是：堆的左右子树必须都是大堆或小堆。

我们将要实现的是升序，所以我们要实现对大堆的向下调整算法（原因在后面进行对排序实现时会详细说明）。

代码展示：

void AdjustDown(int* arr, int size, int parent)
{
    //因为我们要找出左右孩子中较大的那一个进行交换
    //我们先假设左孩子是较大的那一个
    int child = 2 * parent + 1;
    while (child < size)
    {
        if (child + 1 < size && arr[child + 1] > arr[child]) //如果右孩子存在，且比左孩子大，那么对孩子节点进行更新
        {
            child++;
        }
        if (arr[child] > arr[parent])
        {
            Swap(&arr[child], &arr[parent]);
            parent = child;
            child = 2 * parent + 1;
        }
        else
        {
            break;
        }
    }
}

向下建堆：

我们要对一个数组进行堆排序，首先要将数组转换成堆，这里我们使用更为高效的向下调整建堆，事件复杂度为 O(N)，我们先从最后一个叶子节点的父亲节点开始向下调整，然后一直到根节点再结束。

代码展示：

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

堆排序核心思路：我们知道大堆的根节点的值一定是最大的，那如果我们将根节点与最后一个节点交换，再进行 size--,然后重新进行调整，直到 size=1。

void HeapSort(int* arr,int n)//堆排序
{
    BuildHeap(arr, n);
    int end = n - 1;
    while (end > 0)
    {
        Swap(arr, &arr[end]);
        AdjustDown(arr, end, 0);
        end--;
    }
}

时间复杂度：O(nlogn),稳定性：不稳定。

4. 交换排序

4.1 冒泡排序

将相邻的两个数依次进行比较，大的数向后进行交换。

代码展示：

void BubbleSort(int* arr, int n)
{
    for (int i = 0;i < n;i++)
    {
        int flag = 0;
        for (int j = 1;j < n - i;j++)
        {
            if (arr[j - 1] > arr[j])
            {
                int tmp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = tmp;
                flag = 1;
            }
        }
        if (flag == 0)
        {
            return;
        }
    }
}

时间复杂度 O(n^2),稳定

4.2 快速排序

4.2.1 Hoare

快速排序是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法，其基本思想为：

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

具体操作：我们需要设置一个 Key 值，我们以数组第一个元素作为 Key，然后设置两个元素 left,right，分别指向数组最左以及最右的下标，我们先让右边先行，这里是有讲究的，**左边为 Key 值，那么右边先行，反之，左边先行，**原因我在后面会分析。我们要求左边要比 key 值小，右边比 Key 值大，如果左边遇到比 Key 值大的就停下来，右边亦然，两边数据进行交换，再重复上面操作，直至两边相遇，然后将相遇点的值与 Key 进行交换，这里相遇点的值一定是要比 key 小的，这样 Key 在数组中的位置就确定了，我们就以 Key 为基准，进行左右分区，每一个区又重复上面操作，直到每个区只剩一个元素。

时间复杂度：O(nlogn),不稳定，空间复杂度 O(logn);

为什么左边为 Key 值，右边先行？

我们既然设置了左边为 Key 值，那么最后进行交换时要保证相遇点的值比 Key 小。我们知道 left、right 不是同时走，左边找大，右边找小

相遇的场景分析: L 遇 R:R 先走，停下来，R 停下条件是遇到比 key 小的值，R 停的位置一定比 key 小，L 没有找到大的，遇到 R 停下了 R 先走，找小，没有找到比 key 小的，直接跟 L 相遇了。L 停留的位置 R 遇 L:是上一轮交换的位置，上一轮交换，把比 key 小的值，换到 L 的位置了

我们不一定要求以左为 key，但是一定要保证以哪边为 key，相反的一边先走。

代码展示：

void QuickSort(int* arr, int left, int right)
{
    if (left >= right) return;
    int pkey = left;
    int begin = left, end = right;
    while (begin < end)
    {
        while (begin<end && arr[end]>=arr[pkey])
        {
            end--;
        }
        while (begin<end && arr[begin]<=arr[pkey])
        {
            begin++;
        }
        Swap(&arr[begin], &arr[end]);
    }
    Swap(&arr[begin], &arr[pkey]);
    QuickSort(arr, left, begin - 1);
    QuickSort(arr, begin+1,right);
}

其实在这基础上，代码还是可以进一步优化。

三数取中

我们的 key 值应该尽量使得分区是一半一半分的，否则不仅效率降低，还有因为递归层数较深，栈溢出的风险，所以我们尽量把 key 值取中间大小的数。

int Getmidnum(int* arr,int left, int right)
{
    int mid = left + (right-left) / 2;
    if (arr[mid] > arr[left])
    {
        if (arr[mid] < arr[right]) return mid;
        else if (arr[left] > arr[right]) return left;
        else return right;
    }
    else
    {
        if (arr[mid] > arr[right]) return mid;
        else if (arr[left] < arr[right]) return left;
        else return right;
    }
}

我们得到下标之后，进行 Swap(&arr[pkey], &arr[left]);这样对后面的操作就没有影响了。

小区间优化

我们可以想到，就算是理想状态下的快速排序，也不能避免随着递归的深入，每一层的递归次数会以 2 倍的形式快速增长。 为了减少递归树的最后几层递归，我们可以设置一个判断语句，当序列的长度小于某个数的时候就不再进行快速排序，转而使用其他种类的排序。小区间优化若是使用得当的话，会在一定程度上加快快速排序的效率，而且待排序列的长度越长，该效果越明显。

完整优化代码展示：

void QuickSort(int* arr, int left, int right)
{
    if (left >= right) return;
    int pkey = Getmidnum(arr,left,right);
    Swap(&arr[pkey], &arr[left]);
    pkey = left;
    int begin = left, end = right;
    if (end - begin + 1 < 10)
    {
        InsertSort(arr + left, end - begin + 1);
    }
    else
    {
        while (begin < end)
        {
            while (begin < end && arr[end] >= arr[pkey])
            {
                end--;
            }
            while (begin < end && arr[begin] <= arr[pkey])
            {
                begin++;
            }
            Swap(&arr[begin], &arr[end]);
        }
        Swap(&arr[begin], &arr[pkey]);
        QuickSort(arr, left, begin - 1);
        QuickSort(arr, begin + 1, right);
    }
}

4.2.2 挖坑法

挖坑法的单趟排序的基本步骤如下： 1、选出一个数据（一般是最左边或是最右边的）存放在 key 变量中，在该数据位置形成一个坑。 2、还是定义一个 L 和一个 R，L 从左向右走，R 从右向左走。（若在最左边挖坑，则需要 R 先走；若在最右边挖坑，则需要 L 先走）。 3、在走的过程中，若 R 遇到小于 key 的数，则将该数抛入坑位，并在此处形成一个坑位，这时 L 再向后走，若遇到大于 key 的数，则将其抛入坑位，又形成一个坑位，如此循环下去，直到最终 L 和 R 相遇，这时将 key 抛入坑位即可。（选取最左边的作为坑位）

经过一次单趟排序，最终也使得 key 左边的数据全部都小于 key，key 右边的数据全部都大于 key。然后也是将 key 的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作。

void QuickSort(int* arr, int left, int right)
{
    if (left >= right) return;
    int begin = left, end = right;
    int key = arr[left];//在左边形成一个坑位
    while (begin < end)
    {
        while (begin < end && arr[end] >= key)
        {
            end--;
        }
        arr[begin] = arr[end];//填坑
        while (begin < end && arr[begin] <= key)
        {
            begin++;
        }
        arr[end] = arr[begin];//填坑
    }
    int pmeet = begin;
    arr[pmeet] = key;
    QuickSort2(arr, left, pmeet - 1);
    QuickSort2(arr, pmeet + 1, right);
}

4.2.3 前后指针法

我们的核心思想依旧是经过单趟排序，使得 key 的左边全部小于 key,key 的右边全部大于 key。

具体过程： 1.依旧是设置两个变量，prev 指向 left,cur 指向 prev+1 2.如果 cur 遇到的值小于 key，那么 prev++,同时交换 prev 与 cur 的值，cur++;如果大于 key，那么 cur++ 3.直到 cur 越界，交换 prev 以及 key 的值，单趟排序完成

后面依旧将 key 的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作。

void QuickSort3(int* arr, int left, int right)
{
    if (left >= right) return;
    int pkey = Getmidnum(arr, left, right);
    Swap(&arr[pkey], &arr[left]);
    pkey = left;
    int prev = left, cur = prev + 1;
    while (cur <= right)//当 cur 没有越界
    {
        if (arr[cur] < arr[pkey])
        {
            prev++;
            Swap(&arr[prev], &arr[cur]);
        }
        cur++;
    }
    int pmeet = prev;
    Swap(&arr[pkey], &arr[prev]);
    QuickSort3(arr, left, pmeet - 1);
    QuickSort3(arr, pmeet + 1, right);
}

我们把单趟排序的过程写上之后，后续的就交给递归了，那如果没有递归，我们能否实现快排？

4.2.4 非递归实现

我们要使用非递归实现快排，就需要知道函数递归调用栈帧核心是什么？我们以 Hoare 方法来看看。

void QuickSort(int* arr, int left, int right)

我们先看看函数参数，其中 arr 是个整型指针，在函数递归过程中不会改变，而 left 以及 right，是每次函数调用的区间，每一组区间都是不一样的，那么关键就在这里了，函数递归传递的核心就是这些区间，那我们只需要把每次分区的左右端点保存起来，再调用函数就实现了对应区间的排序。那我们应该用什么来存储左右端点？栈。深入想想，会发现用栈来存储左右端点几乎完美复原了函数递归的过程。

代码实现思路： 1.我们先将最初的左右端点入栈，先入右端点再入左端点。 2.我们可以选取三中方法中的任意一种思想来进行单趟排序，我这里选取的是 Hoare 的方法 3.每次取到栈顶数据之后，要删除栈顶数据。 4.得到相遇点的下标之后，需要将分区之后的左右端点再次入栈，但是要判断数据是否合理，依次循环直到栈为空。

代码展示：

int QuickSort1(int* arr, int left, int right)
{
    int pkey = Getmidnum(arr, left, right);
    Swap(&arr[pkey], &arr[left]);
    pkey = left;
    int begin = left, end = right;
    while (begin < end)
    {
        while (begin < end && arr[end] >= arr[pkey])
        {
            end--;
        }
        while (begin < end && arr[begin] <= arr[pkey])
        {
            begin++;
        }
        Swap(&arr[begin], &arr[end]);
    }
    Swap(&arr[begin], &arr[pkey]);
    return begin;
}
void QuickSortNonR(int* arr,int left,int right)
{
    stack st;
    StackInit(&st);
    StackPush(&st, right);
    StackPush(&st, left);
    while (!StackEmpty(&st))
    {
        int begin = StackTop(&st);//左端点
        Stackpop(&st);
        int end = StackTop(&st);//右端点
        Stackpop(&st);
        int pmeet=QuickSort1(arr, begin, end);
        //这里就需要把分好的区的端点入栈
        // [left, pmeet-1] pmeet [pmeet+1, right]
        if (end > pmeet + 1)
        {
            StackPush(&st, end);
            StackPush(&st, pmeet+1);
        }
        if (begin < pmeet - 1)//保证有两个点
        {
            StackPush(&st, pmeet - 1);//右端点先进，左端点就会先出
            StackPush(&st, begin);
        }
    }
    StackDestroy(&st);
}

5. 归并排序

基本思想： 归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

核心思想：把数组一直分，最后分成一个数据，就可以看成有序了，让它与相邻的数据进行合并，合并成一个有序序列，合并之后再合并，最终变成一个有序序列。

递归实现

void _MergeSort(int* arr, int* tmp, int left, int right)
{
    if (left >= right) return;
    int mid = (left + right) / 2;
    //递归进行分割
    //分割的区间为 [left,mid],[mid+1,right]
    //这里分割有也讲究，否则会陷入死循环
    _MergeSort(arr, tmp, left, mid);
    _MergeSort(arr, tmp, mid + 1, right);
    int begin1 = left, end1 = mid;
    int begin2 = mid + 1, end2 = right;
    int i = left;
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (arr[begin1] < arr[begin2])
        {
            tmp[i++] = arr[begin1++];
        }
        else
        {
            tmp[i++] = arr[begin2++];
        }
    }
    while (begin1 <= end1)//把剩下的一边全部加到 tmp 数组中
    {
        tmp[i++]= arr[begin1++];
    }
    while (begin2 <= end2)
    {
        tmp[i++] = arr[begin2++];
    }
    memcpy(arr+left,tmp+left,(right - left + 1) * sizeof(int));
}
void MergeSort(int* arr,int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL)
    {
        perror("malloc failed");
        return;
    }
    _MergeSort(arr, tmp, 0, n - 1);
    free(tmp);
    tmp = NULL;
}

非递归实现

归并排序的非递归算法并不需要借助栈来完成，我们只需要控制每次参与合并的元素个数即可，最终便能使序列变为有序：

当然，以上例子是一个待排序列长度比较特殊的例子，我们若是想写出一个广泛适用的程序，必定需要考虑到某些极端情况： 情况一： 当最后一个小组进行合并时，第二个小区间存在，但是该区间元素个数不够 gap 个，这时我们需要在合并序列时，对第二个小区间的边界进行控制。

情况二： 当最后一个小组进行合并时，第二个小区间不存在，此时便不需要对该小组进行合并。

情况三： 当最后一个小组进行合并时，第二个小区间不存在，并且第一个小区间的元素个数不够 gap 个，此时也不需要对该小组进行合并。（可与情况二归为一类）

代码展示：

void MergeSortNonR(int* arr, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL)
    {
        perror("malloc failed");
        return;
    }
    int gap= 1;
    while (gap < n)
    {
        for (int i = 0;i < n;i += 2 * gap)
        {
            int begin1 = i, end1 = i + gap - 1;
            int begin2 = i + gap, end2 = i + 2 * gap - 1;
            if (begin2 >= n)//这里说明整个第二区间都越界了，那么就不需要合并了
            {
                break;
            }
            if (end2 >= n)
            {
                end2 = n - 1;
            }
            int j=begin1;
            while (begin1 <= end1 && begin2 <= end2)
            {
                if (arr[begin1] < arr[begin2])
                {
                    tmp[j++] = arr[begin1++];
                }
                else
                {
                    tmp[j++] = arr[begin2++];
                }
            }
            while (begin1 <= end1)
            {
                tmp[j++] = arr[begin1++];
            }
            while (begin2 <= end2)
            {
                tmp[j++] = arr[begin2++];
            }
            memcpy(arr + i, tmp + i, (end2-i + 1) * sizeof(int));
        }
        gap *= 2;
    }
    free(tmp);
    tmp = NULL;
}

6. 计数排序

计数排序，又叫非比较排序。顾名思义，该算法不是通过比较数据的大小来进行排序的，而是通过统计数组中相同元素出现的次数，然后通过统计的结果将序列回收到原来的序列中。

计数排序的特性总结：

1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。

2. 时间复杂度：O(MAX(N，范围))

3. 空间复杂度：O(范围)

4. 稳定性：稳定

代码展示：

void CountSort(int* arr, int n)
{
    int min = arr[0], max = arr[0];
    for (int i = 0;i < n;i++)
    {
        if (min > arr[i]) min = arr[i];
        if (max < arr[i]) max = arr[i];
    }
    int range = max - min + 1;
    int* count = (int*)calloc(range, sizeof(int));
    for (int i = 0;i < n;i++)//把 arr 中出现的数字进行计数，数字与下标的差值为 min
    {
        count[arr[i] - min]++;//映射
    }
    int j = 0;
    for (int i = 0;i < range;i++)
    {
        while(count[i]--)
        {
            arr[j++] = i + min;
        }
    }
    free(count);
    count = NULL;
}

特性总结

本文涵盖了八大排序算法的核心原理与实现细节，包括直接插入排序、希尔排序、直接选择排序、堆排序、冒泡排序、快速排序（含多种优化）、归并排序及计数排序。读者可通过对比各算法的时间复杂度、空间复杂度及稳定性，根据实际应用场景选择合适的排序策略。