排序——交换类排序、插入类排序、选择类排序、归并类排序

排序

排序算法分为交换类排序、插入类排序、选择类排序、归并类排序。

交换类排序

冒泡排序

冒泡排序的基本思想是：从后往前（或从前往后）两两比较相邻元素的值。若A[ j - 1 ] > A[ j ]，则交换它们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置。关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”。下一趟冒泡时，前一趟确定的最小元素不再参与比较，每趟冒泡的结果是把序列中的最小元素放到了序列的最终位置…这样最多做$n-1$趟冒泡就能把所有元素排好序。

可以通过点击此处进入旧金山大学提供的网站来演示冒泡排序动画效果。

代码实战:

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

typedef int ElemType;

typedef struct {
    // 存储元素的起始地址
    ElemType *elem;
    // 元素个数
    int table_len;
} SSTable;


/*
 * 顺序表初始化
 */
void st_init(SSTable &ST, int len) {
    ST.table_len = len;
    ST.elem = (ElemType *) malloc(sizeof(ElemType) * ST.table_len);

    // 用于生成随机数的骰子
    srand(time(NULL));

    for (int i = 0; i < ST.table_len; i++) {
        // 生产的数是0-99之间
        ST.elem[i] = rand() % 100;
    }
}


/*
 * 顺序表打印
 */
void st_print(SSTable ST) {
    for (int i = 0; i < ST.table_len; i++) {
        printf("%3d", ST.elem[i]);
    }
    printf("\n");
}


/*
 * 交换两个元素
 */
void swap(ElemType &a, ElemType &b) {
    ElemType temp;

    temp = a;
    a = b;
    b = temp;
}


/*
 * 冒泡排序
 *
 * 排序往往都是用两层循环：1.内层循环控制比较/交换 2.外层循环控制
 */
void bubble_sort(ElemType *A, int len) {
    // 哨兵: 是否发生交换
    bool flag;

    // 外层循环控制
    for (int i = 0; i < len - 1; i++) {
        flag = false;

        // 内层控制比较/交换
        // j = len - 1 是从最后一个元素从后往前比较/交换
        for (int j = len - 1; j > i; j--) {
            if (A[j - 1] > A[j]) {
                swap(A[j - 1], A[j]);
                flag = true;
            }
        }

        // 本趟排序未发生交换说明整个顺序表已经有序
        if (false == flag) {
            return;
        }
    }
}


/*
 * 冒泡排序
 */
int main() {
    SSTable ST;
    // 一、顺序表初始化
    st_init(ST, 10);

    // 固定数组用于调试
    ElemType A[10] = {64, 94, 95, 79, 69, 84, 18, 22, 12, 78};
    // memcpy可用于拷贝整型数组、浮点型数组 strcpy只能拷贝字符型数组
    memcpy(ST.elem, A, sizeof(A));
    // 打印顺序表
    st_print(ST);

    // 二、冒泡排序
    bubble_sort(ST.elem, ST.table_len);
    st_print(ST);

    return 0;
}

时间复杂度：时间复杂度其实就是程序实际的运行次数，可以看到内层是$j>i$，外层$i$的值是从$0$到$n-1$，所以程序的总运行次数是$1+2+3+...+(n-1)$，这是等差数列求和，得到是结果是$n(n-1)/2$，忽略低阶项和高阶项的首项系数，因此时间复杂度是$O(n^2)$。

空间复杂度：因为未使用额外的空间（额外空间必须与输入元素的个数N相关），所以空间复杂度是$O(1)$

快速排序

快速排序的核心是分治思想：假设我们的目标依然是按从小到大的顺序排列，我们找到数组中的一个分割值，把比分割值小的数都放在数组的左边，把比分割值大的数都放在数组的右边，这样分割值的位置就被确定。

数组一分为二，我们只需排前一半数组和后一半数组，复杂度直接减半。采用这种思想，不断地进行递归，最终分割得只剩一个元素时，整个序列自然就是有序的。

可以通过点击此处进入旧金山大学提供的网站来演示快速排序动画效果。

代码实战：

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

typedef int ElemType;

typedef struct {
    // 存储元素的起始地址
    ElemType *elem;
    // 元素个数
    int table_len;
} SSTable;


/*
 * 顺序表初始化
 */
void st_init(SSTable &ST, int len) {
    ST.table_len = len;
    ST.elem = (ElemType *) malloc(sizeof(ElemType) * ST.table_len);

    // 用于生成随机数的骰子
    srand(time(NULL));

    for (int i = 0; i < ST.table_len; i++) {
        // 生产的数是0-99之间
        ST.elem[i] = rand() % 100;
    }
}


/*
 * 顺序表打印
 */
void st_print(SSTable ST) {
    for (int i = 0; i < ST.table_len; i++) {
        printf("%3d", ST.elem[i]);
    }
    printf("\n");
}


/*
 * 分割函数 挖坑法
 */
int partition(ElemType *A, int low, int high) {
    // 拿最左边的元素作为分割值 并存储下来
    ElemType pivot = A[low];

    while (low < high) {
        // 找到一个比分割值小的元素
        while (low < high && A[high] >= pivot) {
            high--;
        }
        A[low] = A[high];

        // 找到一个比分割值大的元素
        while (low < high && A[low] <= pivot) {
            low++;
        }
        A[high] = A[low];
    }

    // 分割值放到中间位置
    // 左边的都比分割值小 右边都比分割值大
    A[low] = pivot;

    return low;
}


/*
 * 快速排序
 */
void quick_sort(ElemType *A, int low, int high) {
    if (low < high) {
        // 存储分割值的位置
        int pivoit_pos = partition(A, low, high);
        quick_sort(A, low, pivoit_pos - 1);
        quick_sort(A, pivoit_pos + 1, high);
    }
}


int main() {
    SSTable ST;
    // 一、顺序表初始化
    st_init(ST, 10);

    // 固定数组用于调试
    ElemType A[10] = {64, 94, 95, 79, 69, 84, 18, 22, 12, 78};
    // memcpy可用于拷贝整型数组、浮点型数组 strcpy只能拷贝字符型数组
    memcpy(ST.elem, A, sizeof(A));
    // 打印顺序表
    st_print(ST);

    // 二、快速排序
    quick_sort(ST.elem, 0, ST.table_len - 1);
    st_print(ST);

    return 0;
}

时间复杂度：假如每次快速排序数组都被平均地一分为二，那么可以得出quick_sort递归的次数是$lo{g}_{2}n$，第一次partition遍历次数为$n$，分成两个数组后，每个数组遍历$n/2$次，加起来还是$n$，因此时间复杂度是 $O(nlo{g}_{2}n)$，因计算机是二进制的，所以在复试面试回答复杂度或与人交流时，提到复杂度时一般直接讲 $O(nlogn)$，而不带下标$2$。

快速排序最差的时间复杂度为什么是呢？

因为数组本身从小到大有序时，如果每次我们仍然用最左边的数作为分割值，那么每次数组都不会二分，导致递归$n$次，所以快速排序最坏时间复杂度为$n$的平方。当然，为了避免这种情况，有时会首先随机选择一个下标，先将对应下标的值与最左边的元素交换，再进行partition操作，从而极大地降低出现最坏时间复杂度的概率，但是仍然不能完全避免。

因此快排最好和平均时间复杂度是 $O(nlo{g}_{2}n)$，最差是$O(n^2)$.

空间复杂度：$O(lo{g}_{2}n)$，因递归的次数是$lo{g}_{2}n$，而每次递归的形参都是需要占用空间的。

插入类排序

插入类排序有三种：直接插入排序、折半插入排序、希尔排序。

直接插入排序

如果一个序列只有一个数，那么该序列自然是有序的。插人排序首先将第一个数视为有序序列，然后把后面9个数视为要依次插入的序列。首先，我们通过外层循环控制要插人的数，用 insertVal保存要插入的值87，我们比较 arr[0]是否大于 arr[1]，即3是否大于87，由于不大于，因此不发生移动，这时有序序列是3，87.接着，将数值2插入有序序列，首先将2赋给 insertVal，这时判断87 是否大于2，因为87大于2，所以将87向后移动，将2覆盖然后判断3是否大于2，因为3大于2，所以3移动到87所在的位置，内层循环结束，这时将2赋给arr[0]的位置，得到下表中第2次插人后的效果。

	有序序列	要插入的数的序列
最初	3	87 2 93 78 56 61 38 12 40
第1次插入	3 87	2 93 78 56 61 38 12 40
第2次插入	2 3 87	93 78 56 61 38 12 40
…	…	…

继续循环会将数依次插人有序序列，最终使得整个数组有序。插入排序主要用在部分数有序的场景，例如手机通讯录时时刻刻都是有序的，新增一个电话号码时，以插入掛序的方法将其插入原有的有序序列，这样就降低了复杂度。

可以通过点击此处进入旧金山大学提供的网站来演示插入排序动画效果。

代码实战：

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

typedef int ElemType;

typedef struct {
    // 存储元素的起始地址
    ElemType *elem;
    // 元素个数
    int table_len;
} SSTable;


/*
 * 顺序表初始化
 */
void st_init(SSTable &ST, int len) {
    ST.table_len = len;
    ST.elem = (ElemType *) malloc(sizeof(ElemType) * ST.table_len);

    // 用于生成随机数的骰子
    srand(time(NULL));

    for (int i = 0; i < ST.table_len; i++) {
        // 生产的数是0-99之间
        ST.elem[i] = rand() % 100;
    }
}


/*
 * 顺序表打印
 */
void st_print(SSTable ST) {
    for (int i = 0; i < ST.table_len; i++) {
        printf("%3d", ST.elem[i]);
    }
    printf("\n");
}


/*
 * 插入排序
 */
void insert_sort(ElemType *A, int len) {
    int i, j, insert_val;

    // 外层控制要插入的数 从第A[1]个开始
    for (i = 1; i < len; i++) {
        // 待插入的值
        insert_val = A[i];

        // 内层控制 j要大于等于0 同时A[j]大于insert_val时 A[j]位置元素往后覆盖
        for (j = i - 1; j >= 0 && A[j] > insert_val; j--) {
            A[j + 1] = A[j];
        }
        A[j + 1] = insert_val;
    }
}


int main() {
    SSTable ST;
    // 一、顺序表初始化
    st_init(ST, 10);

    // 固定数组用于调试
    ElemType A[10] = {64, 94, 95, 79, 69, 84, 18, 22, 12, 78};
    // memcpy可用于拷贝整型数组、浮点型数组 strcpy只能拷贝字符型数组
    memcpy(ST.elem, A, sizeof(A));
    // 打印顺序表
    st_print(ST);

    // 二、插入排序
    insert_sort(ST.elem, ST.table_len);
    st_print(ST);

    return 0;
}

时间复杂度：随着有序序列的不断增加，插入排序比较的次数也会增加，插入排序的执行次数也是从$1$加到$n-1$，总运行次数为$n(n-1)/2$，时间复杂度依然为$O(n$