本文主要回顾排序算法中的插入排序，主要有如下内容：
1.一句白话说插入排序
2.插入排序的具体实现
3.插入排序与选择排序的性能对比
一句白话说插入排序
一句白话说插入排序：每次将一个待排序的元素，按大小插入到前面已经排好序的子序列中的适当位置，直到全部元素插入完成为止。
插入排序的具体实现
- C语言实现
1 |
|
- C++实现
清单1：头文件SortTestHelper.h1
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
using namespace std;
namespace SortTestHelper
{
//生成有n个元素的随机数组，每个元素的随机范围为[range_l, range_r]
int *generateRandomArray(int n, int range_l, int range_r)
{
int *arr = new int[n];
srand(time(NULL));
for(int i = 0; i < n; i++)
arr[i] = rand()%(range_r - range_l + 1) + range_l;
return arr;
}
//拷贝整型数组a中的所有元素到一个新的数组，并返回新的数组
int *copyIntArray(int a[], int n)
{
int *arr = new int[n];
for(int i = 0; i < n; i++)
arr[i] = a[i];
return arr;
}
//打印数组中所有元素
template<typename T>
void printArray(int a[], int n)
{
for(int i = 0; i < n; i++)
cout << a[i] <<" ";
cout << endl;
return;
}
//判断数组是否有序
template<typename T>
bool isSorted(T a[], int n)
{
for(int i = 0; i < n - 1; i++)
{
if(a[i] > a[i+1])
return false;
}
return true;
}
//测试排序算法的正确性和算法运行的时间
template<typename T>
void testSort(const string &sortName, void(*sortAlgo)(T[], int), T arr[], int n)
{
clock_t startTime = clock();
sortAlgo(arr, n);
clock_t endTime = clock();
cout << sortName << ":" << double(endTime - startTime)/CLOCKS_PER_SEC << " s"<<endl;
assert(isSorted(arr, n));
return;
}
}
清单2：头文件SelectionSort.h1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
template<typename T>
void selectionSort(T arr[], int n)
{
for(int i = 0; i < n; i++)
{
int minIndex = i;
for(int j = i + 1; j < n; j++)
{
if(arr[j] < arr[minIndex])
minIndex = j;
}
swap(arr[i], arr[minIndex]);
}
return;
}
清单3:insertSort.cpp
1 |
|
上述C++代码代码实现中对插入排序和选择排序进行了对比
在我自己的电脑上实际运行结果如下：
1 | Test for random array, size = 20000, random range [0, 20000] |
从运行结果可以看出：
选择排序和插入排序所耗费的时间确实满足O( n^2 )规律的，当数据规模扩大10倍时，运行时间几乎扩大100倍
插入排序从理论上来说比选择排序要快一些的，因为插入排序内部循环在满足arr[j] >= arr[j-1]时就可以停下来了，也就是说内部循环的次数是比选择排序要少的；但是为何实际测试的结果却比选择排序慢呢
插入排序与选择排序的性能对比
从理论上来说二者都是O( n^2 )的排序算法
- 选择排序：对于任何一个数组，两层循环，每层循环都会完全的执行完成，效率慢
- 插入排序：第二层循环根据数组情况，可能会提前跳出循环，比如说在近乎有序的情况，因此在近乎有序的情况下，插入排序的性能是很高的
上一小节留下了一个问题，那就是为何上面的插入排序的实现比选择排序的实测结果要慢：
其实原因是上面的实现每次都有去swap交换，而每次swap里面就有三次赋值，还不考虑其他的，这样累积下来就比选择排序耗时了。
既然如此，那我们是不是应该想办法对上述的插入排序进行优化了，避免每次都去swap
优化的方法就是避免每次都去swap，将swap转换为普通的赋值，而不是每次都去swap，具体实现见清单4：
清单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
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
using namespace std;
template<typename T>
void insertSort(T arr[], int n)
{
//插入排序时，第一个元素默认已经是排好序了，所以i从1开始
for(int i = 1; i < n; i++)
{
//(int j = i; j > 0 && arr[j] < arr[j-1]; j--)
//{
// swap(arr[j], arr[j-1]);
//}
T tmp = arr[i];
int j;
for(j = i; j > 0 && arr[j-1] > tmp; j--)
arr[j] = arr[j-1];
arr[j] = tmp;
}
return;
}
int main()
{
int n = 20000;
cout<<"Test for random array, size = "<<n<<", random range [0, "<<n<<"]"<<endl;
int *arr1 = SortTestHelper::generateRandomArray(n, 0, n);
int *arr2 = SortTestHelper::copyIntArray(arr1, n);
SortTestHelper::testSort("Insert Sort", insertSort, arr1, n);
SortTestHelper::testSort("Selection Sort", selectionSort, arr2, n);
//别忘了delete函数里面new出来的数组，否则会造成内存泄露
delete[] arr1;
delete[] arr2;
n = 200000;
cout<<"Test for random array, size = "<<n<<", random range [0, "<<n<<"]"<<endl;
int *arr3 = SortTestHelper::generateRandomArray(n, 0, n);
int *arr4 = SortTestHelper::copyIntArray(arr3, n);
SortTestHelper::testSort("Insert Sort", insertSort, arr3, n);
SortTestHelper::testSort("Selection Sort", selectionSort, arr4, n);
//别忘了delete函数里面new出来的数组，否则会造成内存泄露
delete[] arr3;
delete[] arr4;
return 0;
}
实际运行结果：1
2
3
4
5
6
7
8
9Test for random array, size = 20000, random range [0, 20000]
Insert Sort:0.271 s
Selection Sort:0.528 s
Test for random array, size = 200000, random range [0, 200000]
Insert Sort:28.025 s
Selection Sort:52.455 s
Process returned 0 (0x0) execution time : 83.397 s
Press any key to continue.
数组近乎有序时的测试
清单5：头文件SortTestHelper.h加入生成近乎有序数组的函数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
95
96
97
using namespace std;
namespace SortTestHelper
{
//生成有n个元素的随机数组，每个元素的随机范围为[range_l, range_r]
int *generateRandomArray(int n, int range_l, int range_r)
{
int *arr = new int[n];
srand(time(NULL));
for(int i = 0; i < n; i++)
arr[i] = rand()%(range_r - range_l + 1) + range_l;
return arr;
}
// 生成一个近乎有序的数组
// 首先生成一个含有[0...n-1]的完全有序数组, 之后随机交换swapTimes对数据
// swapTimes定义了数组的无序程度:
// swapTimes == 0 时, 数组完全有序
// swapTimes 越大, 数组越趋向于无序
int *generateNearlyOrderedArray(int n , int swapTimes)
{
int *arr = new int[n];
for(int i = 0; i < n; i++)
arr[i] = i;
srand(time(NULL));
for(int i = 0; i < swapTimes; i++)
{
int posx = rand()%n;
int posy = rand()%n;
swap(arr[posx], arr[posy]);
}
return arr;
}
//拷贝整型数组a中的所有元素到一个新的数组，并返回新的数组
int *copyIntArray(int a[], int n)
{
int *arr = new int[n];
for(int i = 0; i < n; i++)
arr[i] = a[i];
return arr;
}
//打印数组中所有元素
template<typename T>
void printArray(int a[], int n)
{
for(int i = 0; i < n; i++)
cout << a[i] <<" ";
cout << endl;
return;
}
//判断数组是否有序
template<typename T>
bool isSorted(T a[], int n)
{
for(int i = 0; i < n - 1; i++)
{
if(a[i] > a[i+1])
return false;
}
return true;
}
//测试排序算法的正确性和算法运行的时间
template<typename T>
void testSort(const string &sortName, void(*sortAlgo)(T[], int), T arr[], int n)
{
clock_t startTime = clock();
sortAlgo(arr, n);
clock_t endTime = clock();
cout << sortName << ":" << double(endTime - startTime)/CLOCKS_PER_SEC << " s"<<endl;
assert(isSorted(arr, n));
return;
}
}
清单6：insertSort.cpp加入对近乎有序的数组的测试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
using namespace std;
template<typename T>
void insertSort(T arr[], int n)
{
//插入排序时，第一个元素默认已经是排好序了，所以i从1开始
for(int i = 1; i < n; i++)
{
//(int j = i; j > 0 && arr[j] < arr[j-1]; j--)
//{
// swap(arr[j], arr[j-1]);
//}
T tmp = arr[i];
int j;
for(j = i; j > 0 && arr[j-1] > tmp; j--)
arr[j] = arr[j-1];
arr[j] = tmp;
}
return;
}
int main()
{
int n = 20000;
cout<<"Test for random array, size = "<<n<<", random range [0, "<<n<<"]"<<endl;
int *arr1 = SortTestHelper::generateRandomArray(n, 0, n);
int *arr2 = SortTestHelper::copyIntArray(arr1, n);
SortTestHelper::testSort("Insert Sort", insertSort, arr1, n);
SortTestHelper::testSort("Selection Sort", selectionSort, arr2, n);
//别忘了delete函数里面new出来的数组，否则会造成内存泄露
delete[] arr1;
delete[] arr2;
n = 200000;
cout<<"Test for random array, size = "<<n<<", random range [0, "<<n<<"]"<<endl;
int *arr3 = SortTestHelper::generateRandomArray(n, 0, n);
int *arr4 = SortTestHelper::copyIntArray(arr3, n);
SortTestHelper::testSort("Insert Sort", insertSort, arr3, n);
SortTestHelper::testSort("Selection Sort", selectionSort, arr4, n);
//别忘了delete函数里面new出来的数组，否则会造成内存泄露
delete[] arr3;
delete[] arr4;
//测试近乎有序的数组
int swapTimes = 1000;
cout<<"Test for nearly ordered array, size = "<<n<<", swap time= "<<swapTimes<<endl;
arr1 = SortTestHelper::generateNearlyOrderedArray(n, swapTimes);
arr2 = SortTestHelper::copyIntArray(arr1, n);
SortTestHelper::testSort("Insertion Sort", insertSort, arr1, n);
SortTestHelper::testSort("Selection Sort", selectionSort, arr2, n);
delete[] arr1;
delete[] arr2;
return 0;
}
实测结果1
2
3
4
5
6
7
8
9
10
11
12Test for random array, size = 20000, random range [0, 20000]
Insert Sort:0.285 s
Selection Sort:0.516 s
Test for random array, size = 200000, random range [0, 200000]
Insert Sort:28.214 s
Selection Sort:52.536 s
Test for nearly ordered array, size = 200000, swap time= 1000
Insertion Sort:0.063 s
Selection Sort:52.458 s
Process returned 0 (0x0) execution time : 137.457 s
Press any key to continue.
可以看到虽然同为O( n^2 )的排序算法，但是在近乎有序的情况下，插入排序的性能是极大的好于选择排序的。
