排序算法一:插入排序

关于排序的一些定义

稳定性

对于待排序表中的元素$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

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

评论

Your browser is out-of-date!

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

×