目录
- 一、选择排序
- 1.1 常规版(一次排好一个数)
- 1.1.1 基本思想
- 1.1.2 实现思路
- 1.1.3 代码
- 1.2 优化版(一次排好两个数)
- 1.2.1 实现思路
- 1.2.2 代码
- 1.3 时间复杂度
- 二、冒泡排序
- 2.1 实现思路
- 2.2 代码
- 2.3 时间复杂度
- 三、计数排序
- 3.1 基本思想
- 3.2 实现思路
- 3.3 时间和空间复杂度
- 总结
一、选择排序
1.1 常规版(一次排好一个数)
1.1.1 基本思想
每次从待排序的数据中选出一个最小(最大)值,从起始位置开始存放,每排好一个数,存放位置就会向后移一位,直到排所有的数据排完序。
1.1.2 实现思路
- 假设起始位置(i)是最小的,通过变量(minIndex)保存该下标
- a[mini]从该下标(i)的下一个位置(i+1)开始去数据中依次比较
- 找到比自己小的数据,就把mini设为小的下标,循环还没有结束,所以还会用mini位置的值去和后面的值比较。
- 数据都比较完后,minIndex位置的值就是全部数据中最小的,如果minIndex不等于i(一开始i和minIndex的值一样,找到最小了的值后minIndex的会被改变),就需要交换两个位置的值,相等i的位置就是最小值,不用动。(加这个判断是防止数据是有序的,有序就没有必要交换)
- i+1,为了把排好的数据给排除掉,i再去在找数据中最小的值,重复以上操作,直到
i < n - 1
结束。
注意:循环结束如果到i < n
结束,在找数据时候就会越界如n = 1,i + 1就会越界,并且当已经排好了n-1个数后,最后一个元素已经是最大的元素,不需要再进行比较和交换操作了。
1.1.3 代码
// 选择判断(常规版,选一个数)
void SelectSort(int* a, int n)
{// n-1个数排好了,最后一个数就是正确的位置,不用在排序for (int i = 0; i < n - 1; i++){int minIndex = i;for (int j = i + 1; j < n; j++){if (a[j] < a[minIndex]){minIndex = j;}}// minIndex改变了需要交换,minIndex的位置就是最小值// 没有改变,i的位置就是最小值,不用动if (i != minIndex){Swap(&a[i], &a[minIndex]);}}
}
1.2 优化版(一次排好两个数)
选择排序的优化版和常规版,大体思路还是差不多的,只不过每次选出数据中的最小值和最大值。
1.2.1 实现思路
- begin和end标识数据的区间,注意是闭区间
- 最小值(minIndex)从begin(最左边)开始放,最大值(maxIndex)从end(最右边)开始放。
- 排好两个数据后,begin往后走,end往前走,排除已排好的数据(缩小区间),直到begin和end相遇就表示排好了。
特殊情况:
所以我们进行判断,max不等于begin,我们才进行交换,因为begin和min先交换,begin和max重叠,在begin位置的值就会被换走,如果让end和max先交换,还是会有这种问题,不过情况相反而已,所以这个条件必须要加。
1.2.2 代码
// 选择判断(优化版,两个数)
void SelectSort_double(int* a, int n)
{int begin = 0, end = n - 1;while (begin < end){// 一次选出最小值和最大值int minIndex = begin, maxIndex = end;for (int i = begin; i <= end; i++){if (a[i] < a[minIndex]){minIndex = i;}if (a[i] > a[maxIndex]){maxIndex = i;}}if (minIndex != begin)Swap(&a[minIndex], &a[begin]);// max和begin重叠,maxIndex的值已被换到minIndex位置if (maxIndex == begin)maxIndex = minIndex;if (maxIndex != end)Swap(&a[maxIndex], &a[end]);begin++;end--;}
}
1.3 时间复杂度
时间复杂度为 O ( N 2 ) O(N^2) O(N2),最差的排序,最好情况下也是 O ( N 2 ) O(N^2) O(N2),数据有序的情况也要比较。
二、冒泡排序
2.1 实现思路
- 每次就排好一个数,第一个数据和第二数据先比较在交换,小的在前,大的在后,第二个数据在第三个数据交换,一直反复下去。a[j] > a[j + 1]
- 该过程会把小数据(不是最小,只是相比下小数据)交换到前面,直到交换到最后一个数据,最大的数据就在最后面了(比他小的数据都交换在他前面了),为了防止后面数据都是有序,用一个变量标识下(交换了没有),如果后面数据有序继续比较和交换效率低,我们做一下判断,如果有序(没有交换),我们就可以直接跳出。
- 排好一个数后,就排除已排好的数据(缩小区间),直到只剩最后一个数,如果有n个数,只需要交换n-1次,
j < n - 1 - i
。 - 一共只需要排n-1个数,和常规选择排序一个情况,n-1个数有序了,剩余的1个数肯定是有序的,就等于自己和自己比较在交换,无意义。
2.2 代码
// 冒泡排序
void BubbleSort(int* a, int n)
{// 最多排9个数(趟),9个数排好后,第10数就在排好的位置for (int i = 0; i < n - 1; i++){// 标识是否交换,默认是没交换int exchange = 1; // 最多交换9次,最后一次是自己和自己交换,所以只需要排9次for (int j = 0; j < n - 1 - i; j++){if (a[j] > a[j + 1]){Swap(&a[j], &a[j + 1]);exchange = 0; // 数据交换了}}// 数据没有交换,表示有序,就直接跳出if (exchange)break;}
}
冒泡和插入相比哪个更好?
插入排序,对有序,接近有序,局部有序,适应性更强
用一个接近有序的数据,对比执行次数,就能比较出来。
2.3 时间复杂度
时间复杂度为 O ( N 2 ) O(N^2) O(N2)
三、计数排序
计数排序属于非比较排序,只能排整形。
3.1 基本思想
先统计数据出现次数,写到相对的下标里,在通过数据对应的下标来进行从头依次排序,下标位置有几个数,就需要排几个数,数据值和下标相对的。
3.2 实现思路
- 计算出数据的范围区间,最大值减去最小值,这是相对范围
min——max
,绝对范围是0——max
,太浪费空间。 - 创建一个计数数组count,因为是闭区间,大小是
max-min+1
,用来存放数据出现的次数,初始化都是0。 - 统计每个数出现的次数,放入到数据减去最小值的下标位置(计数数组的相对位置)。
- 把数据写到原数组里,只写次数不为0的,出现了几次就写入几个数据,数据通过count的下标+最小值还原出来。
// 计数排序
void CountSort(int* a, int n)
{// 找到最小值和最大值int min = a[0], max = a[0];for (int i = 1; i < n; i++){if (a[i] < min)min = a[i];if (a[i] > max)max = a[i];}// 计算出相对范围int range = max - min + 1;// 创建计数数组,初始化为全0// 方法1int* count = (int*)malloc(range * sizeof(int)); assert(count);memset(count, 0, range * sizeof(int));// 方法2,calloc申请的空间默认都是NULL或0(根据指针类型决定)//int* count = (int*)calloc(range * sizeof(int)); // 统计每个数出现的次数for (int i = 0; i < n; i++){count[a[i] - min]++;}// 把数组写入原数组// 数据出现了多少次就写入多少个值int j = 0;for (int i = 0; i < range; i++){while (count[i]--){a[j++] = i + min;}}
}
3.3 时间和空间复杂度
时间复杂度为 O ( N + K ) O(N+K) O(N+K),K是相对范围(计数数组)的大小。
空间复杂度为 O ( K ) O(K) O(K)
总结
- 选择排序时间复杂度为 O ( N 2 ) O(N^2) O(N2),空间复杂度为 O ( 1 ) O(1) O(1)
- 冒泡排序时间复杂度为 O ( N 2 ) O(N^2) O(N2),空间复杂度为 O ( 1 ) O(1) O(1)
- 计数排序时间复杂度为为 O ( N + K ) O(N + K) O(N+K),K是相对范围(计数数组)的大小,空间复杂为 O ( K ) O(K) O(K)