排序

发表于 分类于 本文字数： 6.7k
插入排序、选择排序、交换排序、合并排序

插入排序

直接插入排序

时间复杂度：$O(n^2)$

最好情况：$O(n)$

最坏情况：$O(n^2)$

空间复杂度：$O(1)$

稳定性：稳定

适用性：适用于顺序储存和链式储存的线性表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void sort(int arr[], int len) {
    int i, j, temp;

    // 从数组序列的第二位开始排序
    for (i = 1; i < len; i++) {
        // i小于它的直接前驱，说明需要排序
        if (arr[i] < arr[i-1]) {
            temp = arr[i]; // 临时储存成员i

            // 将i之前，所有大于i的成员后移一位
            for (j = i - 1; j >= 0 && arr[j] > temp; j--)
                arr[j + 1] = arr[j];

            // 将原先的i提前
            // 这里j需要+1，因为在循环的最后j执行了一次自减
            arr[j + 1] = temp;
        }
    }
}

折半插入排序

折半插入排序仅减少了元素比较的次数，元素移动次数并未改变，因此时间空间复杂度并没有发生改变

时间复杂度：$O(n^2)$

最好情况：$O(n)$

最坏情况：$O(n^2)$

空间复杂度：$O(1)$

稳定性：稳定

适用性：仅适用于顺序储存的线性表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void sort(int arr[], int len) {
    int i, j, temp;
    int low, high, mid;

    // 从数组序列的第二位开始排序
    for (i = 1; i < len; i++) {
        temp = arr[i];

        low = 0;
        high = i - 1;

        // 使用折半查找，寻找插入位置
        while (high >= low) {
            mid = (low + high) / 2;
            // 当 mid 所指的值小于等于目标值时，向右查，否则向左查
            // 这里注意，第一个 if 条件别带等于号
            // 例如在如下序列查找 3 ，如果带等于号最后 high 指针指向 2 处
            // 为了确保算法稳定性，理应让 high 指针指向 3 处
            // 1 2 3 4 5
            if (arr[mid] > temp)
                // 向左查
                high = mid - 1;
            else
                // 向右查
                low = mid + 1;
        }

        for (j = i - 1; j > high; j--) {
            arr[j + 1] = arr[j];
        }

        arr[j + 1] = temp;
    }
}

希尔排序

时间复杂度：尚未可知

最好情况：约为$O(n^{1.3})$

最坏情况：约为$O(n^2)$

空间复杂度：$O(1)$

稳定性：不稳定

适用性：仅适用于顺序储存的线性表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * 希尔排序
 */
void sort(int arr[], int len) {
    int i, j, temp, d;

    // 第一层循环，控制增量d
    // 增量变化无统一规定
    for (d = len / 2; d > 0; d = d / 2) {

        // 第二层循环，以增量d为基，依次在各组之间切换
        for (i = d; i < len; i++) {

            // 此处与插入排序逻辑大体相同
            // 在当前组中，判断i是否小于它的直接前驱
            // 如果小于，则需要对当前组进行排序
            if (arr[i] < arr[i - d]) {
                temp = arr[i];

                // 以增量d为基，将组中排序在i之前，且大于i的所有成员后移一位
                for (j = i - d; j >= 0 && arr[j] > temp; j = j -d) {
                    arr[j + d] = arr[j];
                }

                // 将原先的i提前
                // 这里j需要+d，因为在循环的最后j执行了一次对d的自减
                arr[j + d] = temp;
            }
        }
    }
}

交换排序

冒泡排序

时间复杂度：$O(n^2)$

最好情况：$O(n)$

最坏情况：$O(n^2)$

空间复杂度：$O(1)$

稳定性：稳定

适用性：适用于顺序储存和链式储存的线性表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 从右向左冒泡，将较小值移动至左侧
 */
void sort(int arr[], int len) {
    // 外层循环中的 i 指针指向左侧边缘，j 无法到达该边缘
    for (int i = 0; i < len - 1; i++) {

        int isMove = 0; // 该变量标记是否发生了值交换

        // 内层循环中的 j 指针指向右侧边缘
        // 并从右侧向左冒泡，将较小值移动至左侧
        for (int j = len - 1; j > i; j--) {
            if (arr[j] < arr[j - 1]) {

                isMove = 1;

                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
            }
        }

        // 如果没有发生值交换，说明表有序，提前结束
        if (!isMove)
            break;
    }
}

冒泡排序实现方式千变万化，不必拘泥于某种特定实现方式，如下两种，均有不同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * 从左向右冒泡，将较大值移动至右侧
 */
void sort2(int arr[], int len) {
    // 外层循环中的 i 指针指向右侧边缘，j 无法到达该边缘
    for (int i = len - 1; i > 0; i--) {

        int isMove = 0; // 该变量标记是否发生了值交换

        // 内层循环中的 j 指针指向左侧边缘
        // 并从左侧向右冒泡，将较大值移动至右侧
        for (int j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {

                isMove = 1;

                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }

        // 如果没有发生值交换，说明表有序，提前结束
        if (!isMove)
            break;
    }
}

/**
 * 依然是从左向右冒泡，将较大值移动至右侧
 * 优雅，太他妈的优雅了
 */
void sort3(int arr[], int len) {
    int i, j, temp, move;
    // i 来限制冒泡时右侧的边缘
    for (i = 0; i < len - 1; i++) {
        // 该变量标记是否发生了值交换
        move = 0;
        // 不要超过 i 限制的边缘
        for (j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 发生了值交换
                move = 1;
                // 交换值
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        // 如果没有发生值交换，说明表有序，提前结束
        if (!move)
            break;
    }
}

快速排序

时间复杂度：大多数情况下更接近$O(n\log _2n)$

最好情况：$O(n\log _2n)$

最坏情况：$O(n^2)$

空间复杂度：$O(\log _2n)$

稳定性：不稳定

适用性：仅适用于顺序储存的线性表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int part(int arr[], int low, int high) {

    // 将 low 所指的元素定义为“枢轴”
    int pivot = arr[low];

    // 通过一个循环，将low、high之间的元素根据枢轴分为两部
    while (low < high) {
        // 从右至左，找一个小于枢轴的值
        while (low < high && arr[high] >= pivot) high--;
        // 将该值移动至low所指的位置
        arr[low] = arr[high];

        // 从左至右，找一个大于枢轴的值
        while (low < high && arr[low] <= pivot) low++;
        // 将该值移动至high所指的位置
        arr[high] = arr[low];
    }

    // 此时理论上low = high
    // 将枢轴移动至该位置
    arr[low] = pivot;

    // 将枢轴的位置返回
    return low;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivot = part(arr, low, high);
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
    }
}

void sort(int arr[], int len) {
    quickSort(arr, 0, len - 1);
}

选择排序

简单选择排序

时间复杂度：$O(n^2)$

最好情况：$O(n^2)$

最坏情况：$O(n^2)$

空间复杂度：$O(1)$

稳定性：不稳定

适用性：适用于顺序储存和链式储存的线性表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void sort(int arr[], int len) {

    // 通过 len - 1 次最小值的选择和交换，排列数据表
    for (int i = 0; i < len - 1; i++) {
        // 假设本趟的 i 为最小值
        int min = i;

        // 对 i 之后的元素遍历，找到最小值
        for (int j = i + 1; j < len; j++)
            if (arr[j] < arr[min])
                min = j;

        // 将最小值和 i 进行元素交换
        if (min != i) {
            int temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        }
    }
}

堆排序

时间复杂度：$O(n\log _2n)$

空间复杂度：$O(1)$

稳定性：不稳定

适用性：仅适用于顺序储存的线性表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/**
  * 调整数据表为大根堆
  * 在逻辑上，将数据表视为一棵完全二叉树
  * 接下来的操作中，判断某分支结点是否存在大于自身的子结点
  * 若有，把相对较大的一个子结点和自身做交换
  * @param arr  数据表
  * @param p    结点在数据表中的位序（非下标）
  * @param len  数据表长度（不包括 arr[0] 位）
  */
void adjust(int arr[], int p, int len) {
    // 暂存根结点
    arr[0] = arr[p];

    /* 此处使用循环，目的是防止：
     *   若被交换的子结点是分支结点，经过交换后，
     *   该分支结点继续出现子结点大于自身的情况，
     *   如下 5 和 8 交换后，5 还要再和 7 交换才满足大根堆
     *        5
     *      /   \
     *     4     8
     *    / \   / \
     *   1   2 6   7
     *   需要注意的是，在代码中并没有出现“值的交换”
     *   而是暂存 根结点值，并将大于 根结点值 的 子结点值 复制到 根结点位置
     *   此时原 根结点值 可以作为 子结点值，并与 子结点的子结点值 进行对比
     */
    for (int i = 2 * p; i <= len; i *= 2) {
        // 选择较大的一个子结点
        if (i < len && arr[i] < arr[i + 1])
            i++;

        // 若最大的子结点值大于根结点值，则将子结点值复制到根结点所在位置
        // 注意：第一趟循环时 arr[0] 在根结点位置，第二趟及之后原根结点在逻辑上移至子结点
        // 否则跳出循环
        if (arr[0] < arr[i]) {
            arr[p] = arr[i];

            // 记录被复制值的子结点的 index
            // 逻辑上该 index 现在是 arr[0] 所在的结点
            // arr[0] 经过向下调整后,需要继续与其新位置的子结点作比较
            p = i;
        } else {
            break;
        }
    }

    // p的值循环反复，循环结束后，指向最后一个已经被复制至父结点的子结点身上
    // 此时存放原根节点的值
    arr[p] = arr[0];
}

/**
 * 构建大根堆
 */
void build(int arr[], int len) {
    // 在逻辑上，将数据表视为一棵完全二叉树
    // 根据完全二叉树的特性，对所有分支结点进行调整
    // 使数据表成为大根堆
    for (int i = len / 2; i > 0; i--)
        adjust(arr, i, len);
}

/**
 * 需要注意的是,在大根堆数组中,第一位不储存数据
 */
void sort(int arr[], int len) {
    // 构建大根堆
    build(arr, len);

    // 通过 len - 1 次循环，对大根堆排列
    for (int i = len; i > 1; i--) {
        // 交换堆顶和堆底元素
        int temp = arr[i];
        arr[i] = arr[1];
        arr[1] = temp;
        // 调整交换后的堆
        adjust(arr, 1, i - 1);
    }
}

其实adjust中直接进行结点与结点的值交换也可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void adjust(int arr[], int p, int len) {
    for (int i = 2 * p; i <= len; i *= 2) {
        // 选择较大的一个子结点
        if (i < len && arr[i] < arr[i + 1])
            i++;

        if (arr[p] < arr[i]) {
            // i 升为父结点以后就不用再管了
            // p 降为子结点以后，需要再和后面的新子结点比较
            int temp = arr[p];
            arr[p] = arr[i];
            arr[i] = temp;

            p = i;
        } else {
            break;
        }
    }
}

归并排序

时间复杂度：$O(n\log _2n)$

空间复杂度：$O(n)$

稳定性：稳定

适用性：适用于顺序储存和链式储存的线性表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * 将表中的数据以mid划分为两部分，
 * 并将这两部分视为两个数据表，然后进行合并
 */
void merge(int arr[], int low, int high, int len) {
    int i, j, k;
    int mid = (high + low) / 2;

    // 构建辅助表
    int* aux = (int*)malloc(sizeof(int) * len);

    // 把原表中的数据复制进辅助表
    for (k = low; k <= high; k++)
        aux[k] = arr[k];

    // 以mid为中心将数据表划分为两部分
    // 每趟循环将其中一部分的较小值储存至原数据表中
    // 直到某一部分的数据被全部储存为止
    for (i = low, j = mid + 1, k = low; i <= mid && j <= high; k++) {
        if (aux[i] < aux[j])
            arr[k] = aux[i++];
        else
            arr[k] = aux[j++];
    }

    // 将另一部分没有被全部储存的数据存进原数据表
    while (i <= mid) arr[k++] = aux[i++];
    while (j <= high) arr[k++] = aux[j++];

    // 释放辅助表
    free(aux);
}

void mergeSort(int arr[], int low, int high, int len) {
    if (low < high) {
        int mid = (low + high) / 2;
        // 处理左部分
        mergeSort(arr, low, mid, len);
        // 处理右部分
        mergeSort(arr, mid + 1, high, len);
        // 合并处理完毕的两部分
        merge(arr, low, high, len);
    }
}

void sort(int arr[], int len) {
    mergeSort(arr, 0, len - 1, len);
}