- 冒泡排序
- 选择排序
- 插入排序
- 希尔排序
冒泡排序
思想:
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
效率:
比较:N - 1 + N - 2 + ...+ 3 + 2 + 1 ~O(N2/2)
交换:最少 0次 最多比较一次交换一次
即:N - 1 + N - 2 + ...+ 3 + 2 + 1 ~O(N2/2)
说明:
Code
int a[10] = {4, 2, 5, 7, 8, 9, 10, 1, 6, 3};
for (int i = 0; i < 10 - 1; i++) {
for (int j = 0; j < 10 - i - 1; j++) {
if (a[j] > a[j + 1]) {
exchange(&a[j], &a[j + 1]);
}
}
}
选择排序
思想:
- 找出数组中最小的那个元素，与数组中的第一个元素交换(如果第一个元素就是最小的元素那么它就和自己交换)。
- 找出剩下元素中最小的元素，与数组中的第一个元素交换。如此往复， 直到将整个数组排序。
效率:对于长度为N的数组,选择排序需要大约N2/2次比较和N次交换
说明:
- 对于思想的第1步,找出数组中最小的那个元素需要次数:
2 1 3 4 5五个数找出最小, 假设第一个最小,后边依次比较如果更小就交换,所以5个数字找出最小的那个数需要4次比较。
所以比较次数:
N-1 + N-2 + ...+ 3 + 2 + 1 = na1 + n(n-1)d/2 = N(N-1)/2
Code
int a[] = {2, 8, 7, 1, 3, 5, 6, 4};
for (int i = 0; i < N; i++) {
int index = i;
for (int j = i + 1; j < N; j++) {
if (a[j] < a[index]) {
index = j;
}
exchange(&a[index], &a[i]);
}
}
插入排序
思想:
- 比如把4 插入 1 2 5 6 中
- 4 < 6 前继续找合适位置插入, 4 < 5继续 但是2 < 4 故 4 插入2 5之间。
效率:对于长度为N的数组且主键不重复的数组， 平均插入需要N^2/4次比较以及N2/4交换。最坏需要~N2/2次比较和~N^2/2次交换, 最好需要N-1次比较和0次交换
说明:
可见红色箭头移动一次累加比较次数：1 + 2 + 3 因为a[j] 都比a[j - 1]小 所以比较次数很多。交换 1 + 2 + 3次。
但是 如果是 【1 2 3 4】 比较 3次 交换0次。
Code
int a[10] = {4, 2, 5, 7, 8, 9, 10, 1, 6, 3};
for (int i = 1; i < N; i++) {
for (int j = i; j > 0 && a[j] < a[j - 1]; j--) {
exchange(&a[j], &a[j -1]);
}
}
其中N是宏定义的个数， exchange是定义的一个交换函数。j交换以后红色箭头元素会移动， 但是j--。移动一次j--一次， 所以箭头的任然是a[j]初始那个元素。插入排序对部分有序的数组十分高效，也很是很小规模的数组。所以可以让数组先部分有序， 这就减少了比较次数， 提高了效率。所以这就很好理解希尔排序了。
希尔排序
思想:
- 先部分有序化(任然是小范围插入排序思想)
- 增量为1时 为 插入排序
效率:希尔排序的时间复杂度会比o(n2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
说明:
递增序列给出一种:1 4 13 40 ...(3 * h + 1)
增量为4时对以下元素进行部分有序化。
code
int a[10] = {4, 2, 5, 7, 8, 9, 10, 1, 6, 3};
int h = 1;
while (h < N/3) h = 3 * h + 1;
while (h >= 1) {
for (int i = h; i < N; i++) {
for (int j = i; j >= h && a[j] < a[j - h]; j-=h) {
exchange(&a[j], &a[j - h]);
}
}
h = (h - 1)/3;
}
