数据结构：八种常见排序算法

直接插入排序的特性总结 元素集合越接近有序，直接插入排序算法的时间效率越高 时间复杂度：O(n^2) 【最差情况：1+2+……+n-1，最好情况(O(n))：1+1+……+1】 空间复杂度：O(1)

2.1.2 希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数（通常是 gap=n/3+1），把待排序文件所有记录分成各组，所有的距离相等的记录分在同一组内，并对每一组内的记录进行排序，然后 gap=gap/3+1 得到下一个整数，再将数组分成各组，进行插入排序，当 gap=1 时，就相当于直接插入排序。(gap 为 n，就划分为 n 组)

它是在直接插入排序算法的基础上进⾏改进而来的，综合来说它的效率肯定是要高于直接插入排序算法的。

希尔排序的特性

1. 希尔排序是对直接插入排序的优化。当 gap > 1 时都是预排序，目的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。

代码实现：

void ShellSort(int* arr, int n) {
    int gap = n;
    while (gap > 1) {
        gap = gap / 3 + 1; //+1 是因为当 gap=1 时是直接插入排序
        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;
        }
    }
}

2.1.2.1 希尔排序的时间复杂度计算

希尔排序的时间复杂度估算：

外层循环：外层循环的时间复杂度可以直接给出为：O(logn) 或者 O(log3n)，即 O(logn)

内层循环：

gap 取值有（以除 3 为例）：n/3，n/9，n/27，… 2，1

• 当 gap 为 n/3 时，移动总数为：n/3*(1 + 2) = n • 当 gap 为 n/9 时，移动总数为：n/9*(1 + 2 + 3 + … + 8) = 4n • 最后一趟，gap=1 即直接插入排序，内层循环排序消耗为 n

通过以上的分析，可以画出这样的曲线图：

因此，希尔排序在最初和最后的排序的次数都为 n，即前一阶段排序次数是逐渐上升的状态，当到达某一顶点时，排序次数逐渐下降至 n，而该顶点的计算暂时无法给出具体的计算过程

希尔排序时间复杂度不好计算，因为 gap 的取值很多，导致很难去计算，因此很多书中给出的希尔排序的时间复杂度都不固定。

《数据结构(C 语言版)》—严蔚敏书中给出的时间复杂度为：

2.2 选择排序

选择排序的基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

2.2.1 直接选择排序

代码实现：

//优化后
void SelectSort(int* arr, int n) {
    int begin = 0, end = n - 1;
    while (begin < end) {
        int mini = begin, maxi = begin;
        for (int i = begin + 1; i <= end; i++) {
            if (arr[i] > arr[maxi]) {
                maxi = i;
            }
            if (arr[i] < arr[mini]) {
                mini = i;
            }
        }
        if (begin == maxi) {
            maxi = mini;
        }
        Swap(&arr[mini], &arr[begin]);
        Swap(&arr[maxi], &arr[end]);
        ++begin;
        --end;
    }
}

直接选择排序的特性总结：

1. 直接选择排序思考非常好理解，但是效率不是很好，实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)

2.2.2 堆排序

堆排序 (Heapsort) 是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

2.3 交换排序

交换排序基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置

交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动

2.3.1 冒泡排序

前面在算法题中我们已经接触过冒泡排序的思路了，冒泡排序是一种最基础的交换排序。之所以叫做冒泡排序，因为每一个元素都可以像小气泡一样，根据自身大小一点一点向数组的一侧移动。

代码实现：

void BubbleSort(int* arr, int n) {
    int exchange = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                exchange = 1;
                Swap(&arr[j], &arr[j + 1]);
            }
        }
        if (exchange == 0) {
            break;
        }
    }
}

冒泡排序的特性总结

• 时间复杂度：O(N^2)

• 空间复杂度：O(1)

2.3.2 快速排序

快速排序是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

快速排序实现主框架：

//快速排序
void QuickSort(int* arr, int left, int right) {
    if (left >= right) {
        return;
    }
    //找基准值，并把基准值放到指定的位置上
    QuickSort(arr, left, meet - 1);
    QuickSort(arr, meet + 1, right);
}

如何找基准值，并把基准值放到指定的位置上？

主要有以下几种实现方式：

2.3.2.1 hoare 版本（重要）

算法思路： 1）创建左右指针，确定基准值 2）right：从右向左找出比基准值小的数据，left：从左向右找出比基准值大的数据，左右指针数据交换，进入下次循环

问题 1：为什么跳出循环后 right 位置的值一定不大于 key？当 left > right 时，即 right 走到 left 的左侧，而 left 扫描过的数据均不大于 key，因此 right 此时指向的数据一定不大于 key

问题 2：为什么 left 和 right 指定的数据和 key 值相等时也要交换？相等的值参与交换确实有一些额外消耗。但是实际还有各种复杂的场景，假设数组中的数据大量重复时，无法进行有效的分割排序。比如下面这种情况

代码实现：

tips：递归的时间复杂度=单次递归的时间 * 循环次数=nlogn 循环次数是二叉树的高度，满二叉树的结点个数 n=2k-1，则 k=log2n+1

// 找基准值，时间复杂度不是 n^2，而是 n，因为两层 while 循环只循环了一遍数组
int _QuickSort(int* arr, int left, int right) {
    int keyi = left;
    left++;
    while (left <= right) {
        //right:从右往左找小于基准值的
        while (left <= right && arr[right] > arr[keyi]) {
            --right;
        }
        //left：从左往右找大于基准值的
        while (left <= right && arr[left] < arr[keyi]) {
            ++left;
        }
        //这里找到 left 比基准值大，right 比基准值小
        if (left <= right)
            Swap(&arr[left++], &arr[right--]);
    }
    //right 的位置就是基准值的位置
    Swap(&arr[keyi], &arr[right]);
    return right;
}

//快速排序
void QuickSort(int* arr, int left, int right) {
    if (left >= right) {
        return;
    }
    //找基准值 keyi
    int keyi = _QuickSort(arr, left, right);
    //左右序列递归继续排序
    QuickSort(arr, left, keyi - 1);
    QuickSort(arr, keyi + 1, right);
}

如果基准值找的不好/数组有序，时间复杂度为 n^2。

2.3.2.2 挖坑法

思路：创建左右指针。首先从右向左找出比基准小的数据，找到后立即放入左边坑中，当前位置变为新的"坑"，然后从左向右找出比基准大的数据，找到后立即放入右边坑中，当前位置变为新的"坑"，结束循环后将最开始存储的分界值放入当前的"坑"中，返回当前"坑"下标（即分界值下标）

int _QuickSort(int* arr, int left, int right) {
    int hole = left;
    int key = arr[hole];
    while (left < right) {
        while (left < right && arr[right] > key) {
            --right;
        }
        arr[hole] = arr[right];
        hole = right;
        while (left < right && arr[left] < key) {
            ++left;
        }
        arr[hole] = arr[left];
        hole = left;
    }
    arr[hole] = key;
    return hole;
}

2.3.2.3 lomuto 前后指针（重要）

创建前后指针，从左往右找比基准值小的进行交换，使得小的都排在基准值的左边。

int _QuickSort(int* arr, int left, int right) {
    int prev = left, cur = left + 1;
    int key = left;
    while (cur <= right) {
        if (arr[cur] < arr[key] && ++prev != cur) {
            Swap(&arr[cur], &arr[prev]);
        }
        ++cur;
    }
    Swap(&arr[key], &arr[prev]);
    return prev;
}

快速排序特性总结：

1. 时间复杂度：O(nlogn)
2. 空间复杂度：O(logn)

2.3.2.4 非递归版本（重要）

非递归版本的快速排序需要借助数据结构：栈

代码实现

void QuickSortNonR(int* arr, int left, int right) {
    ST st;
    STInit(&st);
    STPush(&st, right);
    STPush(&st, left);
    while (!STEmpty(&st)) {
        int begin = STTop(&st);
        STPop(&st);
        int end = STTop(&st);
        STPop(&st);
        // 单趟
        int keyi = begin;
        int prev = begin;
        int cur = begin + 1;
        while (cur <= end) {
            if (arr[cur] < arr[keyi] && ++prev != cur)
                Swap(&arr[prev], &arr[cur]);
            ++cur;
        }
        Swap(&arr[keyi], &arr[prev]);
        keyi = prev;
        // [begin, keyi-1] keyi [keyi+1, end]
        if (keyi + 1 < end) {
            STPush(&st, end);
            STPush(&st, keyi + 1);
        }
        if (begin < keyi - 1) {
            STPush(&st, keyi - 1);
            STPush(&st, begin);
        }
    }
    STDestroy(&st);
}

2.4 归并排序（重要）

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

归并递归排序核心步骤：

代码实现

void _MergeSort(int* arr, int left, int right, int* tmp) {
    if (left >= right) {
        return;
    }
    int mid = (right + left) / 2;
    // [left,mid] [mid+1,right]
    _MergeSort(arr, left, mid, tmp);
    _MergeSort(arr, mid + 1, right, tmp);
    int begin1 = left, end1 = mid;
    int begin2 = mid + 1, end2 = right;
    int index = begin1;
    //合并两个有序数组为一个数组
    while (begin1 <= end1 && begin2 <= end2) {
        if (arr[begin1] < arr[begin2]) {
            tmp[index++] = arr[begin1++];
        } else {
            tmp[index++] = arr[begin2++];
        }
    }
    while (begin1 <= end1) {
        tmp[index++] = arr[begin1++];
    }
    while (begin2 <= end2) {
        tmp[index++] = arr[begin2++];
    }
    for (int i = left; i <= right; i++) {
        arr[i] = tmp[i];
    }
}

void MergeSort(int* arr, int n) {
    int* tmp = (int*)malloc(sizeof(int) * n);
    _MergeSort(arr, 0, n - 1, tmp);
    free(tmp);
}

归并排序特性总结：

1. 时间复杂度：O(nlogn)
2. 空间复杂度：O(n)

2.5 测试代码：排序性能对比

// 测试排序的性能对比
void TestOP() {
    srand(time(0));
    const int N = 100000;
    int* a1 = (int*)malloc(sizeof(int) * N);
    int* a2 = (int*)malloc(sizeof(int) * N);
    int* a3 = (int*)malloc(sizeof(int) * N);
    int* a4 = (int*)malloc(sizeof(int) * N);
    int* a5 = (int*)malloc(sizeof(int) * N);
    int* a6 = (int*)malloc(sizeof(int) * N);
    int* a7 = (int*)malloc(sizeof(int) * N);
    for (int i = 0; i < N; ++i) {
        a1[i] = rand();
        a2[i] = a1[i];
        a3[i] = a1[i];
        a4[i] = a1[i];
        a5[i] = a1[i];
        a6[i] = a1[i];
        a7[i] = a1[i];
    }
    int begin1 = clock();
    InsertSort(a1, N);
    int end1 = clock();
    int begin2 = clock();
    ShellSort(a2, N);
    int end2 = clock();
    int begin3 = clock();
    SelectSort(a3, N);
    int end3 = clock();
    int begin4 = clock();
    HeapSort(a4, N);
    int end4 = clock();
    int begin5 = clock();
    QuickSort(a5, 0, N - 1);
    int end5 = clock();
    int begin6 = clock();
    MergeSort(a6, N);
    int end6 = clock();
    int begin7 = clock();
    BubbleSort(a7, N);
    int end7 = clock();
    printf("InsertSort:%d\n", end1 - begin1);
    printf("ShellSort:%d\n", end2 - begin2);
    printf("SelectSort:%d\n", end3 - begin3);
    printf("HeapSort:%d\n", end4 - end4);
    printf("QuickSort:%d\n", end5 - begin5);
    printf("MergeSort:%d\n", end6 - begin6);
    printf("BubbleSort:%d\n", end7 - begin7);
    free(a1);
    free(a2);
    free(a3);
    free(a4);
    free(a5);
    free(a6);
    free(a7);
}

2.6 非比较排序

2.6.1 计数排序

计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。

操作步骤： 1）统计相同元素出现次数 2）根据统计的结果将序列回收到原来的序列中

代码实现

void CountSort(int* arr, int n) {
    //找 min，max
    int min = arr[0], max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) max = arr[i];
        if (arr[i] < min) min = arr[i];
    }
    //确定数组大小 range
    int range = max - min + 1;
    int* count = (int*)malloc(sizeof(int) * range);
    if (count == NULL) {
        perror("malloc fail");
        exit(1);
    }
    //对 count 初始化----calloc，memset
    memset(count, 0, sizeof(int) * range);
    // 统计次数
    //通过映射的方式将数组保存在 count 数组中
    //映射的方式==原数组的值-min
    for (int i = 0; i < n; i++) {
        count[arr[i] - min]++;
    }
    //将 count 数组中的数据还原到 arr 数组中
    int index = 0;
    for (int i = 0; i < range; i++) {
        while (count[i]--) {
            arr[index++] = i + min;
        }
    }
    free(count);
}

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

时间复杂度：O(n + range)

空间复杂度：O(range)

稳定性：稳定

3. 排序算法复杂度及稳定性分析

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。

四种不稳定排序举例

本节全部代码汇总

//Sort.h
#pragma once
#include<stdio.h>
#include<memory.h>
#include<stdlib.h>

//插入排序
//1）直接插入排序 <n^2
void InsertSort(int* arr, int n);
//2）希尔排序 n^1.3
void ShellSort(int* arr, int n);

//选择排序
//1）直接选择排序 n^2
void SelectSort(int* arr, int n);
//2）堆排序 nlogn
void HeapSort(int* arr, int n);

//交换排序
//1）冒泡排序 n^2
void BubbleSort(int* arr, int n);
//2）快速排序 nlogn
void QuickSort(int* arr, int left, int right);
//3)非递归版本的快速排序
void QuickSortNonR(int* arr, int left, int right);

//归并排序 nlogn
void MergeSort(int* arr, int n);

//非比较排序
void CountSort(int* arr, int n);

//Stack.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>
typedef int STDataType;
typedef struct Stack {
    STDataType* arr; //数组
    int top; //有效数据的个数，也是栈顶
    int capacity; //栈的空间大小
} ST;

// 初始化栈
void STInit(ST* ps);
// 销毁栈
void STDestroy(ST* ps);
// 入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//取栈顶元素
STDataType STTop(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);
//栈是否为空
bool STEmpty(ST* ps);

//Stack.c
#include"Stack.h"

// 初始化栈
void STInit(ST* ps) {
    ps->arr = NULL;
    ps->top = ps->capacity = 0;
}

// 销毁栈
void STDestroy(ST* ps) {
    if (ps->arr)
        free(ps->arr);
    ps->arr = NULL;
    ps->top = ps->capacity = 0;
}

// 入栈
void STPush(ST* ps, STDataType x) {
    assert(ps); //先判断空间是否足够
    if (ps->top == ps->capacity) {
        //如果 capacity==0；不能直接*2
        int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
        if (tmp == NULL) {
            perror("realloc");
            exit(1);
        }
        ps->arr = tmp;
        ps->capacity = newCapacity;
    }
    //空间足够
    ps->arr[ps->top++] = x;
}

//出栈
void STPop(ST* ps) {
    assert(!STEmpty(ps));
    ps->top--;
}

//取栈顶元素
STDataType STTop(ST* ps) {
    assert(!STEmpty(ps));
    return ps->arr[ps->top - 1];
}

//获取栈中有效元素个数
int STSize(ST* ps) {
    assert(ps); //传的参数指针不为空就行，有效数据个数可以为 0
    return ps->top;
}

//栈是否为空
bool STEmpty(ST* ps) {
    assert(ps);
    return ps->top == 0; //如果 top==0 就直接返回
}

//test.c
#include"Sort.h"

void printArr(int* arr, int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void test01() {
    //int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };
    //int a[] = { 5, 3, 9, 6, 2, 4 };
    int a[] = {6, 1, 2, 7, 9, 3};
    int n = sizeof(a) / sizeof(a[0]);
    printf("排序之前:");
    printArr(a, n);
    //InsertSort(a,n);
    //ShellSort(a, n);
    //SelectSort(a, n);
    //QuickSort(a, 0, n - 1);
    //QuickSortNonR(a, 0, n - 1);
    //MergeSort(a, n);
    CountSort(a, n);
    printf("排序之后:");
    printArr(a, n);
}

// 测试排序的性能对比
void TestOP() {
    srand(time(0));
    const int N = 100000;
    int* a1 = (int*)malloc(sizeof(int) * N);
    int* a2 = (int*)malloc(sizeof(int) * N);
    int* a3 = (int*)malloc(sizeof(int) * N);
    int* a4 = (int*)malloc(sizeof(int) * N);
    int* a5 = (int*)malloc(sizeof(int) * N);
    int* a6 = (int*)malloc(sizeof(int) * N);
    int* a7 = (int*)malloc(sizeof(int) * N);
    for (int i = 0; i < N; ++i) {
        a1[i] = rand();
        a2[i] = a1[i];
        a3[i] = a1[i];
        a4[i] = a1[i];
        a5[i] = a1[i];
        a6[i] = a1[i];
        a7[i] = a1[i];
    }
    int begin1 = clock();
    InsertSort(a1, N);
    int end1 = clock();
    int begin2 = clock();
    ShellSort(a2, N);
    int end2 = clock();
    int begin3 = clock();
    SelectSort(a3, N);
    int end3 = clock();
    int begin4 = clock();
    HeapSort(a4, N);
    int end4 = clock();
    int begin5 = clock();
    QuickSort(a5, 0, N - 1);
    int end5 = clock();
    int begin6 = clock();
    MergeSort(a6, N);
    int end6 = clock();
    int begin7 = clock();
    BubbleSort(a7, N);
    int end7 = clock();
    printf("InsertSort:%d\n", end1 - begin1);
    printf("ShellSort:%d\n", end2 - begin2);
    printf("SelectSort:%d\n", end3 - begin3);
    printf("HeapSort:%d\n", end4 - begin4);
    printf("QuickSort:%d\n", end5 - begin5);
    printf("MergeSort:%d\n", end6 - begin6);
    printf("BubbleSort:%d\n", end7 - begin7);
    free(a1);
    free(a2);
    free(a3);
    free(a4);
    free(a5);
    free(a6);
    free(a7);
}

int main() {
    test01();
    //TestOP();
    return 0;
}