数据结构与算法_排序算法_四个基础排序算法性能对比

分析一下冒泡排序、选择排序、插入排序、希尔排序等四个基础排序算法的性能，先逐个分析一下它们的特点。

一、四个基础排序算法的特点

1. 冒泡排序特点

相邻元素两两比较，并进行交换；其缺点是交换次数太多了，这也导致了冒泡排序是所有排序算法中效率最低的。
冒泡算法的改进：当某趟比较没有交换时，退出循环；
时间复杂度：冒泡排序的平均时间复杂度是O(n*n)，最好情况下时间复杂度是O(n),即数组是有序的。
**空间复杂度：**空间复杂度是O(1)，没有占用额外的空间。
稳定性：冒泡排序是稳定的排序算法，因为只有前一个元素大于后一个元素时才交换，小于等于则不交换，所以该排序算法是稳定的。
该算法每趟都能产生一个最大或最小的元素。

2. 选择排序特点

冒泡排序通过两两比较，每趟冒出一个元素放在末尾，而选择排序在逻辑上将数列分成两个数列【个人这样理解的】，一个数有序数列，一个数无序数列。
该排序算法思想是每趟比较都在无序数列中选择最小的一个元素和有序数列中末尾元素进行交换。
从该算法的过程中也可看出，选择排序算法相对于冒泡排序算法减少了交换次数，减少了IO开销，也就提高了算法性能。从下面的实验对比可以看出，同时对80000个数组进行排序，选择排序比冒泡排序的时间减少了一倍左右。
选择排序算法每趟也能产生一个最大或最小的元素。
时间复杂度：时间复杂度是O（nn），该算法之所以还是慢的原因是虽然比冒泡排序交换的次数少了，但还是需要进行交换，一旦涉及到交换就比移动效率更低，数组交换比数组移动需要更少的指令数，所以交换比移动效率更低。
空间复杂度：O(1)；
稳定性：不稳定，比如13 15 | 15 14 这趟交换完毕后，13 14 | 15* 15 所以，该算法不稳定。

3. 插入排序特点

插入排序最大的特点是数据越趋近有序，那么插入排序是所有排序算法中，效率最低的排序算法。该算法的也可以理解为将数列逻辑上分成两个数列，一个是有序数列一个是无序数列，每次都将无序数列中的一个元素插入到有序数列的合适的位置，保持有序数列一直有序。具体做法是从无序数列中选出一个元素与有序数列最后一个位置开始逐个向前比较，如果该元素大于（以从小到大排序为例）有序数列中这个次数时，就插入到有序数列中的当前位置的后边，否则有序数列中当前的元素进行后移。
时间复杂度：共需要n趟操作，假设都趟都会涉及到有序数列中数据的向后移动，所以最坏情况下时间复杂度是O(n*n)，最好情况下不需要数据的移动，或者很少需要数据移动，所以是O(n)；
空间复杂度：没有占用额外的内存，所以时间复杂度是O(1);
**稳定性：**该算法是稳定算法。

4. 希尔排序特点

插入排序是数据越趋近有序，插入排序的效率就越高，因为不需要进行数据的移动；希尔排序对插入排序进行了两个方面的改进，分别从“减少待比较元素”和“基本有序”两个方面。从减少待插入元素来说，将整个数列按一定的增量进行分组，这样相对于整个数列来说，带插入元素减少了。从“基本有序”方面来说，对于每个分组进行插入排序，这样对于整个数列来说，整个数列逐渐变得基本有序。
时间复杂度：希尔排序的时间复杂度取决于增量，不同的增量时间复杂度也不同，但是没有一种最好的增量序列。大量实验表明，希尔排序的平均时间复杂度是O(n^1.3)，最坏情况下是O(n*n)，空间复杂度是O(1)
稳定性：不稳定。

二、性能分析代码

// 冒泡排序：
// 时间复杂度 O(n) * O(n) 最好情况下O(n)，即比较一趟后没有产生交换
// 空间复杂度，O(1)
void BubbleSort(int arr[],int size)
{
	for (int i = 0; i < size - 1; i++)
	{
		bool flag = false; // 优化:如果某行不用进行交换，说明数组已经有序
		for (int j = 0; j < size - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])  // 稳定算法，
			{
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
				flag = true;
			}
		}
		if (!flag)
		{
			break;
		}
	}
}

// 选择排序 
// 时间复杂度：O(n) * O(n)
// 空间复杂度O(1) 
// 稳定性：不稳定
void ChoiceSort(int arr[], int size)
{
	for (int i = 0; i < size - 1; i++)  // 比较 n - 1趟即可，最后一趟不用比较
	{
		int min = arr[i];
		int k = i;       // 记录当前比较的元素和其索引，假设当前值是最小值 
		for (int j = i + 1; j < size; j++)   // 这个for循环减少了 交换次数
		{
			if (min > arr[j])   
			{
				min = arr[j];
				k = j;
			}
		}
		if (i != k)
		{
			int tmp = arr[i];
			arr[i] = arr[k];
			arr[k] = tmp;
		}
	}

}

// 插入排序
// 在普通算法中，数据越趋于有序，插入排序是最高的。
void InsertSort(int arr[], int size)
{
	for (int i = 1; i < size; i++)  // i指向无序序列中的首元素 
	{
		int val = arr[i];  // val
		int j = i - 1;
		for (; j >= 0; j--)  // j指向了有序数列最后一个元素，每次比较实际上有序数列都多出一个位置
		{						// 这个for作用是找出待插入元素的位置，同时将待插入位置空出来
			if (arr[j] <= val)
			{
				break;
			}
			arr[j + 1] = arr[j];// j + 1 表示当前比较元素的后边一个元素，也就是要插入val的位置
		}
		arr[j + 1] = val;
	}
}

void ShellSort(int arr[], int size)
{
	for (int gap = size / 2; gap > 0; gap /= 2)
	{
		for (int i = gap; i < size; i++)
		{
			int val = arr[i];  // i 仍然指向无序数列首元素
			int j = i - gap;     // j 仍然指向有序元素的最后一个位置
			for (; j >= 0; j -= gap)
			{
				if (arr[j] <= val)   // 有序数列中元素从后向前和val进行比较
				{
					break;
				}
				arr[j + gap] = arr[j];
			}
			arr[j + gap] = val;
		}
	}

}


// 四种算法比较
int main()
{
	const int CONNT = 80000;
	int *arr1 = new int[CONNT];
	int *arr2 = new int[CONNT];
	int *arr3 = new int[CONNT];
	int *arr4 = new int[CONNT];

	srand(time(0));

	for (int i = 0; i < CONNT; i++)
	{
		int val = rand() % CONNT;
		arr1[i] = val;
		arr2[i] = val;
		arr3[i] = val;
		arr4[i] = val;
	}
	cout << endl;
	clock_t begin, end;
	begin = clock();
	BubbleSort(arr1, CONNT);
	end = clock();
	cout << "BubbleSort1() spend" << (end - begin)*1.0 / CLOCKS_PER_SEC << "s" << endl;

	begin = clock();
	ChoiceSort(arr2, CONNT);
	end = clock();
	cout << "ChoiceSort() spend" << (end - begin)*1.0 / CLOCKS_PER_SEC << "s" << endl;

	begin = clock();
	InsertSort(arr3, CONNT);
	end = clock();
	cout << "InsertSort() spend" << (end - begin)*1.0 / CLOCKS_PER_SEC << "s" << endl;


	begin = clock();
	ShellSort(arr4, CONNT);
	end = clock();
	cout << "ShellSort() spend" << (end - begin)*1.0 / CLOCKS_PER_SEC << "s" << endl;

	system("pause");
	return 0;
}
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

三、时间对比

冒泡排序效率最低，因为每趟都涉及到交换和比较；
选择排序效率次之，减少了交换次数，所以比冒泡排序效率高一些。
插入排序没有数据的交换，对数据进行移动，移动的效率比交换的效率高，所以时间上减少了一倍。
希尔排序效率更高，移动次数比插入排序移动次数和待比较元素都减少了，所以效率更高了。