小熊の小站

Try my best.

排序算法设计与实现

Littlebear0729's Avatar 2022-03-20 学习记

  1. 1. 概述
  2. 2. 实验设计
    1. 2.1. 算法实现原理
    2. 2.2. 算法设计与分析
  3. 3. 实验结果说明与分析
    1. 3.1. 实验设置
    2. 3.2. 实验结果以及相应的分析
  4. 4. 总结

概述

本实验旨在评估不同排序算法的时间复杂度。

本实验使用了C++语言实现冒泡排序、插入排序、归并排序以及快速排序四种常见的排序算法。通过度量在不同的数据规模下,使用不同的排序算法所耗时间,评估不同算法对数组排序的时间复杂度。

实验结果是:在十万数量级下,冒泡排序以及插入排序已经分别消耗了32s和17s。在百万数量级下的排序时间已经超出可以等待的时间范围,因此在百万数量级只评估归并排序和快速排序两种方法。

在数据规模较小时(数组大小<=1000),四种排序算法时间差异不大。

在数据规模较大时(数组大小>=10000),归并排序和快速排序相较于冒泡排序和插入排序要快100倍以上。

实验设计

算法实现原理

  1. 冒泡排序

    每一次循环将最小(或最大)的数上升(或下沉)交换到数组的头部(尾部)。

    在每一次循环后,前i个数(或后i个数)是有序的。

  2. 插入排序

    每一次循环将无序的单个数字插入到有序的位置。

    在每一次循环后,前i个数(或后i个数)是有序的。

  3. 归并排序

    整体使用递归的思想,先进行二分分隔,对每一个最小单元进行比较。

    在每一个最小单元是有序的情况下,进行比较和合并。

  4. 快速排序

    整体使用递归的思想。

    先确定一个哨兵数字,第一轮排序过后,在它左侧的数字都比它小,它右侧的数字都比它大(或相等)。

    在每一轮排序过后,哨兵数字在整体当中的位置即被确定。

    此后再分别对哨兵数字左右两侧的数组选择哨兵数字,排序…

算法设计与分析

在算法设计与分析里面详细解释算法的细节,核心代码或伪代码,并对算法的时间复杂度进行分析

  1. 冒泡排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    // Bubble sort
    int *bubbleSort(int array[], int size) {
    for (int i = 0; i < size; i++) {
    for (int j = 0; j < size - 1 - i; j++) {
    if (array[j] > array[j + 1]) {
    swap(array[j], array[j + 1]);
    }
    }
    }
    return array;
    }

    每一次i循环把最大值下沉到数组最后。

    总共需要比较约$n^2$次(双层for循环),时间复杂度$O(n^2)$。

  2. 插入排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    // Insertion sort
    int *insertionSort(int array[], int size) {
    for (int i = 1; i < size; i++) {
    int j = i;
    while (j > 0 && array[j] < array[j - 1]) {
    swap(array[j], array[j - 1]);
    j--;
    }
    }
    return array;
    }

    每一次i循环确定前第i个值是有序的,把第i个值通过逐个比较插入到前面的有序数组之中。

    总共需要比较约$n^2$次(双层for循环),时间复杂度$O(n^2)$。

  3. 归并排序

    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
    // Merge sort
    int *mergeSort(int array[], int size) {
    if (size <= 1) {
    return array;
    }
    int mid = size / 2;
    int *left = new int[mid];
    int *right = new int[size - mid];
    for (int i = 0; i < mid; i++) {
    left[i] = array[i];
    }
    for (int i = mid; i < size; i++) {
    right[i - mid] = array[i];
    }
    mergeSort(left, mid);
    mergeSort(right, size - mid);
    int i = 0, j = 0, k = 0;
    while (i < mid && j < size - mid) {
    if (left[i] < right[j]) {
    array[k++] = left[i++];
    } else {
    array[k++] = right[j++];
    }
    }
    while (i < mid) {
    array[k++] = left[i++];
    }
    while (j < size - mid) {
    array[k++] = right[j++];
    }
    return array;
    }

    通过递归将数组一层层分隔成左右两部分,直到每一块只有一个数的时候进行合并。

    合并的时候使用双指针进行比较。总共分成$\lg n$层,每一层合并需要比较$n$次,时间复杂度为$O(n\lg n)$。

  4. 快速排序

    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
    // Quick sort
    int *quickSort(int array[], int size) {
    if (size <= 1) {
    return array;
    }
    int pivot = array[0];
    int i = 1, j = size - 1;
    while (i <= j) {
    while (i <= j && array[i] < pivot) {
    i++;
    }
    while (i <= j && array[j] > pivot) {
    j--;
    }
    if (i <= j) {
    swap(array[i], array[j]);
    i++;
    j--;
    }
    }
    array[0] = array[j];
    array[j] = pivot;
    quickSort(array, j);
    quickSort(array + j + 1, size - j - 1);
    return array;
    }

    把数组第一个值作为哨兵数,使用双指针进行比较。i和j分别表示比哨兵数小的最大值和比哨兵数大的最小值,直到i和j相遇。将i和j位置上的数进行互换,直到i和j相遇时,i左侧没有比哨兵数大的值和j右侧没有比哨兵数小的值。

    在这一轮结束后,哨兵数的位置已经确定。再分别对哨兵数左右两侧的数组进行递归排序。

实验结果说明与分析

实验设置

  1. 输入

  2. 输出

    1. 目前测试的数据规模
    2. 目前使用的排序算法
    3. 所耗时间

实验结果以及相应的分析

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
Array size: 10
Bubble sort: 0.002 ms
Insertion sort: 0.001 ms
Merge sort: 0.001 ms
Quick sort: 0.001 ms

Array size: 100
Bubble sort: 0.026 ms
Insertion sort: 0.017 ms
Merge sort: 0.012 ms
Quick sort: 0.006 ms

Array size: 1000
Bubble sort: 2.367 ms
Insertion sort: 1.602 ms
Merge sort: 0.149 ms
Quick sort: 0.076 ms

Array size: 10000
Bubble sort: 290.153 ms
Insertion sort: 166.927 ms
Merge sort: 1.668 ms
Quick sort: 1.023 ms

Array size: 100000
Bubble sort: 32745.190 ms
Insertion sort: 17152.222 ms
Merge sort: 19.322 ms
Quick sort: 12.595 ms

Array size: 1000000
Bubble sort: Too long time...
Insertion sort: Too long time...
Merge sort: 215.802 ms
Quick sort: 167.150 ms

可以看到数据量在10000的时候,冒泡和插入排序已经使用了100-200ms了,但与此同时归并和快速排序不到2ms。

在数据量到100000的时候,冒泡和插入排序已经使用了数十秒,但归并和快速排序不到20ms。

在更多数据量的时候,使用归并和快速排序算法速度更快。

总结

通过此实验,了解了四种常见的排序算法(冒泡、插入、归并、快速排序)的时间复杂度和评估方法。

通过直观的时间测量了解了不同的排序算法的适用范围和优劣。

代码开源在:https://gitee.com/littlebear0729/data-structure-and-algorithm

本文作者 : Littlebear0729
本文使用 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议
本文链接 : https://blog.hailres.xyz/2022/03/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E8%AE%BE%E8%AE%A1%E4%B8%8E%E5%AE%9E%E7%8E%B0/

本文最后更新于 天前,文中所描述的信息可能已发生改变