blog

991数据结构考研复习（八）——内排序

发表于 更新于 分类于
991 数据结构复习

八.、内排序

  • 排序

根据记录关键字值的递增或递减关系将记录的次序重新排列，使得原来一组次序任意的记录转变为按其关键字值有序排列的一组记录

  • 内排序

当待排序的数据量不大时，在排序中将全部信息存放在内存中处理的排序方法

  • 排序的时间效率与排序过程中数据元素之间的比较次数和交换（移动）次数直接相关，尤其是比较次数。

插入排序

基本原理：

第 i 趟排序将序列中的第 i+1 个元素插入到一个已经按值有序的子序列，得到一个长度为 i+1 且仍然保持按值有序的子序列。

元素间的比较次数：

最好情况：当原始序列已经按值递增时，对应的每个 i 值只需进行一次元素之间的比较，比较的次数最少，为：n-1，此时不需要移动元素，即 $O(n)$

最坏情况：原始序列按值递减，对应的每个 i 值都要进行 i - 1 次元素之间的比较，比较的次数最多，为：n(n-1)/2，即 $O(n^2)$

随机情况：取上述平均值，约为 $n^2 / 4$

排序总趟数：n-1

排序稳定性：稳定

链表可行性：适合

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

空间复杂度：只需一个辅助空间 $O(1)$

核心算法：

1
2
3
4
5
6
7
8
9
10
void insert_sort(int num[], int n) {
    int i, j, tmp;
    for (i = 1; i < n; i++) {
        tmp = num[i];
        for (j = i - 1; j >= 0 && num[j] > tmp; j--) {
            num[j + 1] = num[j];
        }
        num[j + 1] = tmp;
    }
}

折半插入排序

时间复杂度：

最好的情况下：$O(nlog_2n)$，比简单插入排序要好

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

核心算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void half_insert_sort(int num[], int n) {
    int i, j, tmp;
    for (i = 1; i < n; i++) {
        tmp = num[i];
        int start = 0, end = i - 1;
        int mid;
        while (start <= end) {
            mid = (start + end) / 2;
            if (num[mid] > tmp)
                end = mid - 1;
            else
                start = mid + 1;
        }
        for (j = i - 1; j >= start; j--)
            num[j + 1] = num[j];
        num[start] = tmp;
    }
}

选择排序

基本原理：

第 i 趟排序从序列的后 n-i+1 个元素中选择选择一个最小的元素与该 n-i+1 个元素的前面那个元素交换位置，即与整个序列的第 i 个位置上的元素交换位置。直至 i = n-1 排序结束

元素间的比较次数：

不论元素的初始排列状态如何，第 i 趟排序要找出值最小的元素都需要进行 n - i 次元素之间的比较。整个过程中的比较次数为：$n(n-1)/2$

元素间的移动（交换）次数：

最好情况（原序列升序）：0 次

最坏情况：3(n-1) 次，3是交换 k[i] 与 k[d] 的执行次数

排序总趟数：n - 1

排序稳定性：不稳定

链表可行性：适合

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

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

核心算法：

1
2
3
4
5
6
7
8
9
10
11
12
void select_sort(int num[], int n) {
    int i, j, index;
    for (i = 0; i < n - 1; i++) {
        index = i;
        for (j = i + 1; j < n; j++) {
            if (num[j] < num[index]) {
                index = j;
            }
        }
        swap(&num[i], &num[index]);
    }
}

泡排序

基本原理：

一趟排序：比较相邻两个元素，若前者大于后者，两者交换（此时最大值被放到了最后）

此后，再对前 n - 1 个元素进行同样的过程，依次类推，直至某一趟不出现交换动作为止

元素间的比较次数：

最好情况：原始序列为升序，只需经过 1 趟 n - 1次元素比较，此时不需要移动元素，即 $O(n)$

最坏情况：原始序列为逆序，或者最小值的元素在最后，需要进行 n - 1 趟排序，需要进行 $n(n-1)/2$次元素比较

相比于插入和选择，需要移动较多次数的元素。

排序总趟数：最多 n - 1，可以更少

排序稳定性：稳定

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

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

核心代码：

1
2
3
4
5
6
7
8
9
10
void bubble_sort(int num[], int n) {
    int i, j;
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - i - 1; j++) {
            if (num[j] > num[j + 1]) {
                swap(&num[j], &num[j + 1]);
            }
        }
    }
}

谢尔（Shell）排序

基本原理：

确定间隔数 gap，将所有位置间隔为gap的元素视为一个子序列，在各个子序列中采用某种方法进行排序；

缩小间隔数，重新划分子序列并进行排序，直至gap=1

特点：

元素的移动在子序列间跳跃式进行。gap越大，跳跃的跨度越大，很多时候，当gap=1时，序列已经几乎按值有序，不需要进行较多元素的移动。

元素间的比较次数：

排序总趟数：

排序稳定性：不稳定

链表可行性：不适合

时间复杂度：一般情况下认为在 $O(nlog_2n)$ 与 $O(n^2)$ 之间，回答时回答： $O(nlog_2n)$

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

核心代码（子序列中以冒泡排序为例）：

1
2
3
4
5
6
7
8
9
10
11
12
void shell_sort(int num[], int n) {
    int gap, i, j;
    for (gap = n / 2; gap > 0; gap /= 2) {
        for (i = 0; i < n - gap; i++) {
            for (j = 0; j < n - i - gap; j++) {
                if (num[j] > num[j + gap]) {
                    swap(&num[j], &num[j + gap]);
                }
            }
        }
    }
}

快速排序

基本原理：

在当前待排序的序列中选择基准元素，把小于等于基准元素的都移到基准元素的前面，大于基准元素的都移到基准元素的前后面。这样，基准元素位置就找到了

分别对基准元素前后的两个子序列递归进行上述过程即可

元素间的比较次数：

排序总趟数：

排序稳定性：不稳定

链表可行性：不适合

时间复杂度：

待排序元素初始有序（升序或降序）情况下，花费时间最长：$n(n-1)/2$ ，$O(n^2)$

分界元素在正中间：$O(nlog_2n)$

空间复杂度：

最坏情况：分界元素每次都在一边，堆栈的最大递归深度为 $n$，致使空间复杂度为 $O(n)$

最好情况：分解元素每次都在中间，最小递归深度为：$\lfloor log_2n \rfloor + 1$

若在一趟排序之后比较两个所划分的子序列的长度，并且先对长度较短的子序列进行快排，此时的堆栈深度为：$O(log_2n)$

一般情况：$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
void q_sort(int num[], int left, int right) {
    if (left >= right)
        return;
    
    int i = left, j = right, key = num[left];
    
    while (i < j) {
        while (j > i && num[j] >= key) {
            j--;
        }
        num[i] = num[j];
        while (i < j && num[i] <= key) {
            i++;
        }

        num[j] = num[i];
    }
    num[i] = key;
    q_sort(num, left, i - 1);
    q_sort(num, i + 1, right);
}

/**
 * 快速排序
 */
void quick_sort(int num[], int n) {
    q_sort(num, 0, n - 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
void q_sort_use_stack(int num[], int left, int right, int stack[]) {
    if (left >= right)
        return;

    int top = 0;
    stack[top++] = left;
    stack[top++] = right;

    while (top > 0) {
        right = stack[--top];
        left = stack[--top];

        int i = left, j = right, key = num[left];

        while (i < j) {
            while (j > i && num[j] >= key) {
                j--;
            }
            num[i] = num[j];
            while (i < j && num[i] <= key) {
                i++;
            }

            num[j] = num[i];
        }
        num[i] = key;

        if (i - 1 > left) {
            stack[top++] = left;
            stack[top++] = i - 1;
        }

        if (i + 1 < right) {
            stack[top++] = i + 1;
            stack[top++] = right;
        }
    }
}

/**
 * 快速排序非递归算法
 */
void quick_sort_use_stack(int num[], int n) {
    int *stack = (int *) malloc(sizeof(int) * n);
    q_sort_use_stack(num, 0, n - 1, stack);
}

堆积（Heap）排序

基本原理：

大顶堆：一棵完全二叉树，其中每个分支节点的值均大于或等于其左子树和右子树（若存在右子树的话）中所有结点的值，并且该完全二叉树的根节点值最大

排序算法：

  1. 设法构造初始堆积，使得最大值在第一个位置；
  2. 交换第一个与最后一个元素的位置；
  3. 重新把移走最大值后剩余的元素组成的序列转化为堆积
  4. 重复执行第 2 步到第 3 步 n - 1 次

元素间的比较次数：

排序总趟数：n - 1

排序稳定性：不稳定

链表可行性：不适合

时间复杂度：

将原始序列调整为一个初始堆积：所需时间应是各层上的节点数与该层上节点可移动的最大距离之积的总和，为 2n，这一部分的时间花费：$O(n)$

将剩下元素重新调整为新堆积：每调用一次 adjust 函数，节点移动的最大距离为这棵完全二叉树的深度：$d=log_2(n+1)$，一共调用了 n + 1 次，这一部分的时间花费：$O(nlog_2n)$

总时间花费：$O(nlog_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
/**
 * 调整堆积
 * @param root 根节点所在位置
 */
void adjust(int num[], int root, int end) {
    int dad = root;
    int son = root * 2 + 1;  //son 为 root 左孩子的序号

    while (son <= end) {
        if (son + 1 <= end && num[son] < num[son + 1]) { //此时右孩子更大一些，选大的
            son++;
        }
        if (num[dad] >= num[son])
            break;
        swap(&num[(son - 1) / 2], &num[son]);
        dad = son;
        son = son * 2 + 1;
    }
}

/**
 * 堆排序
 */
void heep_sort(int num[], int n) {
    int i;
    for (i = (n - 1) / 2; i >= 0; i--)
        adjust(num, i, n - 1);

    for (i = n - 1; i >= 1; i--) {
        swap(&num[0], &num[i]);
        adjust(num, 0, i - 1);
    }
}

二路归并排序

基本原理：

将初始长度为 n 的原始序列看成是由 n 个长度为 1 的按值有序的子序列组成，并把这些子序列中的相邻子序列两两合并，得到 $\lfloor n/2 \rfloor$ 个长度为 2 的按值有序的子序列；

继续合并，得到 $\lfloor n/4 \rfloor$ 个长度为 4 的按值有序的子序列；依此类推，最后只剩下一个长度为 n 的子序列，即为最终结果

元素间的比较次数：

排序总趟数：$\lceil log_2n \rceil$

排序稳定性：稳定

链表可行性：适合

时间复杂度：

等于归并趟数乘以每一趟归并的时间复杂度。子算法 merge_part 时间复杂度为 $O(n)$，因此总的时间复杂度为：$O(nlog_2n)$

空间复杂度：需要用到长度为 n 的辅助空间，为 $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
void merge(int num[], int tmp[], int start, int mid, int end) {
    int i = start, j = mid + 1, k = start;
    while (i != mid + 1 && j != end + 1) {
        if (num[i] < num[j])
            tmp[k++] = num[i++];
        else
            tmp[k++] = num[j++];
    }
    while (i != mid + 1)
        tmp[k++] = num[i++];
    while (j != end + 1)
        tmp[k++] = num[j++];
    for (i = start; i <= end; i++)
        num[i] = tmp[i];
}

void merge_part(int num[], int tmp[], int start, int end) {
    int mid;
    if (start < end) {
        mid = start + (end - start) / 2;
        merge_part(num, tmp, start, mid);
        merge_part(num, tmp, mid + 1, end);
        merge(num, tmp, start, mid, end);
    }
}

void merge_sort(int num[], int n) {
    int *tmp = (int *) malloc(sizeof(int) * n);
    merge_part(num, tmp, 0, n - 1);
}

小结

  • 稳定性：
    • 稳定：插入、冒泡、归并
    • 不稳定：选择、谢尔、快排、堆排
  • 链表结构的适合度
    • 适合：插入、冒泡、归并、选择
    • 不适合：快排、堆排、谢尔
  • 时间复杂度：
    • $O(n^2)$：插入、冒泡、选择
    • $ O(nlog_2n)$：谢尔、快排（最坏情况为 $O(n^2)$）、堆排、归并
  • 空间复杂度：
    • $O(n)$：归并
    • $O(log_2n)$：快排
    • $O(1)$：插入、谢尔、冒泡、选择、堆排
相关文章推荐
坚持原创技术分享，感谢您的支持和鼓励！