发表更新数据结构10 分钟读完 (大约1573个字)

排序算法一：插入排序

关于排序的一些定义

稳定性

对于待排序表中的元素$R_i$和$R_j$，其对应的关键字相等，即$key_i=key_j$，且$R_i$在$R_j$前面。使用某一排序算法后，$R_i$仍然在$R_j$前面，则这个排序算法是稳定的。

举个🌰：对于数组[4,25,2,6,6,8,34,24]，经过排序算法一排序后结果为[2,4,6,6,8,24,25,34]，经过排序算法二排序后结果为[2,4,6,6,8,24,25,34]。则说明，排序算法一具有稳定性，而排序算法二不具有稳定性。

稳定性不是衡量排序算法优劣的标准，它是排序算法的一个性质。如果待排序表中的关键字不允许重复，则稳定性就无关紧要。

内部排序与外部排序

内部排序指排序期间元素全部放在内存中的排序，外部排序指排序期间无法全部同时存放在内存中，必须在排序过程中根据要求不断的在内、外存之间移动的排序。

排序算法大致可分为插入排序、交换排序、选择排序、归并排序和基数排序五大类。

插入排序

直接插入排序

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
#include <iostream>
#include "vector"

using namespace std;

/*
 * incremental sorting
 */
void InsertSort(vector<int> &nums) {
    for (int i = 1; i < nums.size(); ++i) {
        if (nums[i] < nums[i - 1]) { // if the 最坏情况下，如上图，希尔排序优于其他插入排序。

而当数据全都是已排序状态时，希尔排序不如其他插入排序。current number is less than the number before it,
            int temp{nums[i]}, j{0}; // store the current number with a temporary variable
            for (j = i - 1; j >= 0 && temp < nums[j]; --j) {
                nums[j + 1] = nums[j];
            }
            nums[++j] = temp;
        }
    }
}

int main() {
    vector<int> nums{2, 6, 4, 24, 6, 8, 25, 34};
    InsertSort(nums);
    for (int i : nums) {
        cout << i << "\t";
    }
    cout << endl;
    return 0;
}

空间复杂度：仅使用了常数个辅助单元，空间复杂度为$O(1)$

时间复杂度：最好情况下，已经有序，比较$n-1$次，移动0次；最坏情况下，倒序，需要比较$\sum_{i=2}^{n} i=\frac{1}{2}n^2+\frac{1}{2}n$次，需要移动$\sum_{i=2}^{n}(i+1)=\frac{1}{2}n^2+\frac{3}{2}n-2$次。取平均，时间复杂度为$O(n^2)$。

最坏情况下比较次数的计算：

对于数组：[3,2,1]，步骤如下：

将2移动到temp中，比较temp和3，将3后移，将temp插入。 –>比较一次、移动三次，结果为[2,3,1]

将1移动到temp中，比较temp和3，将3后移；比较temp和2，将2后移。将temp插入。 –>比较两次、移动四次，结果为[1,2,3]

合计：比较3次，移动7次。根据时间复杂度公式计算，少了两次比较？其实少的这两次在上述代码的第12行，先判断了一下当前元素是否小于前面的，如果小于才进行后续过程，否则直接进行下一个元素的判断。这样能够减少当前元素移动到temp的次数。

每次插入都是从后向前比较插入，不会出现元素位置发生变化的情况，具有稳定性。

适用于顺序存储和链式存储的线性表，对链表排序时，可以从前往后查找制定元素的位置。

大部分排序算法都仅适用于顺序存储的线性表。

带哨兵的插入排序：将待排序元素数列第0个位置空出来作为哨兵，起到上面temp的作用，能够减少一些元素插入操作，提升不大反而代码逻辑不够清晰，因此不推荐。

折半插入排序

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
#include <iostream>
#include "vector"

using namespace std;

/*
 * incremental sorting
 * optimized
 */
void InsertSort(vector<int> &nums) {
    for (int i = 2; i < nums.size(); ++i) {
        int low{0}, high{i - 1}, temp{nums[i]};
        while (low <= high) {
            int mid{int((low + high) / 2)};
            // if mid == temp, we still cannot insert temp after mid! because we don't know how many items are repeated
            // for example,[1,2,2,2,3...],while we compare number 2 with the third number 2,they are equal,
            // but we cannot insert number 2 into the place after the third number 2,because the stability is compromised
            if (temp < nums[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        for (int j = low; j <= i - 1; ++j) {
            nums[j + 1] = nums[j];
        }
        nums[low] = temp;
    }
}

int main() {
    vector<int> nums{2, 6, 4, 24, 6, 8, 25, 34};
    InsertSort(nums);
    for (int i : nums) {
        cout << i << "\t";
    }
    cout << endl;
    return 0;
}

对链表进行排序，无法使用折半插入排序。

对链表进行排序，其比较次数不变，但是元素移动次数不变。

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
 * reduceMultiples: the multiple of the step reduction
 */
void ShellSort(vector<int> nums, int reduceMultiples) {
    int step = int(nums.size() / 2);
    for (; step >= 1; step /= reduceMultiples) {
        for (int i = step; i < nums.size(); ++i) {
            if (nums[i] < nums[i - step]) {
                int temp{nums[i]}, j{i - step};
                for (; j >= 0 && temp < nums[j]; j -= step) {
                    nums[j + step] = nums[j];
                }
                nums[j + step] = temp;
            }
        }
    }
}

三种插入排序执行时间的比较

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>
#include "vector"
#include "ctime"

using namespace std;

/*
 * incremental sorting
 */
void InsertSort(vector<int> nums) {
    for (int i = 1; i < nums.size(); ++i) {
        if (nums[i] < nums[i - 1]) { // if the current number is less than the number before it,
            int temp{nums[i]}, j; // store the current number with a temporary variable
            for (j = i - 1; j >= 0 && temp < nums[j]; --j) {
                nums[j + 1] = nums[j];
            }
            nums[++j] = temp;
        }
    }
}

/*
 * incremental sorting
 * optimized
 */
void InsertSortOptimized(vector<int> nums) {
    for (int i = 2; i < nums.size(); ++i) {
        int low{0}, high{i - 1}, temp{nums[i]};
        while (low <= high) {
            int mid{int((low + high) / 2)};
            // if mid == temp, we still cannot insert temp after mid! because we don't know how many items are repeated
            // for example,[1,2,2,2,3...],while we compare number 2 with the third number 2,they are equal,
            // but we cannot insert number 2 into the place after the third number 2,because the stability is compromised
            if (temp < nums[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        for (int j = low; j <= i - 1; ++j) {
            nums[j + 1] = nums[j];
        }
        nums[low] = temp;
    }
}

/*
 * reduceMultiples: the multiple of the step reduction
 */
void ShellSort(vector<int> nums, int reduceMultiples) {
    int step = int(nums.size() / 2);
    for (; step >= 1; step /= reduceMultiples) {
        for (int i = step; i < nums.size(); ++i) {
            if (nums[i] < nums[i - step]) {
                int temp{nums[i]}, j{i - step};
                for (; j >= 0 && temp < nums[j]; j -= step) {
                    nums[j + step] = nums[j];
                }
                nums[j + step] = temp;
            }
        }
    }
}


int main() {
    vector<int> nums{25000};
    for (int i = 25000; i > 0; --i) {
        nums.push_back(i);
    }

    clock_t start, finish;
    double duration;

    start = clock();
    InsertSort(nums);
    finish = clock();
    duration = (double) (finish - start);
    printf("duration 1: %f\n", duration);

    start = clock();
    InsertSortOptimized(nums);
    finish = clock();
    duration = (double) (finish - start);
    printf("duration 2: %f\n", duration);

    start = clock();
    ShellSort(nums, 2);
    finish = clock();
    duration = (double) (finish - start);
    printf("duration 3: %f\n", duration);
    return 0;
}
1
2
3
4
5
6
/home/wenzengsheng/CLionProjects/DataStructure/cmake-build-debug/DataStructure
duration 1: 1460104.000000
duration 2: 1013374.000000
duration 3: 3053.000000

Process finished with exit code 0
1
2
3
4
5
6
/home/wenzengsheng/CLionProjects/DataStructure/cmake-build-debug/DataStructure
duration 1: 711.000000
duration 2: 2513.000000
duration 3: 3453.000000

Process finished with exit code 0

最坏情况下，希尔排序优于其他插入排序。而当数据全都是已排序状态时，希尔排序不如其他插入排序。

#

喜欢这篇文章？打赏一下作者吧

评论

最新文章

标签

ADB1
Ajax1
Apriori1
Bootstrap2
C++4
C语言1
Docker2
FRP1
FTP2
Git3
GitHub1
Gitee1
IDEA1
JSP3
Java16
K-Means1
Linux9
MariaDB1
Maven1
MySQL5
Navicat1
Nginx6
Node.js1
OAuth21
Office1
PHP1
PaddlePaddle1
PyTorch1
Python5
Radis1
SpEL1
Spring1
Tomcat2
UML2
Vue8
Windows2
conda1
gcc1
gpio1
iPhone1
jQuery11
pi4j1
ss1
人工智能6
其他学科4
决策树1
前端24
安卓2
广工2
微信小程序4
微表情识别1
排序算法1
数据挖掘3
数据结构4
旁路由1
树莓派9
私人网盘2
线性代数1
网易云音乐1
计算机网络1
计量经济学2
金融学1
飞浆1

分类

关注我

目录

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×

×