2021-11-09
关键字：桶排序
1、桶排序
桶排序一般用于对一组知道上下限的整数序列中。
因为桶排序的核心原理就是全覆盖式计数，为整个区间每一个数创建一个计数器，遍历待排序序列，为每一个出现的数计数加1，最后根据需要从头至尾或从尾至头打印区间计数。
举个例子，假设要为一个班级的学生数学考试分数做个排序。
已知分数范围为 0 ~ 100，是一个知道上下限的区间。现有分数：52、70、41、99、64、64。创建一个101个长度的数组score，第0号表示成绩为0分的人数，第1号为成绩为1分的人数，第101号为成绩为100分的人数。遍历待排序序列，第一个成绩为52，则将score数组第53号的值加1，第二个成绩为70，则将score数组第71号的值加1，依此类推直至结尾。当我们需要获取排序结果时，例如想要将成绩从高到低打印出来，则可以逆遍历score数组，当其计数值大于0时则打印出来即可。
桶排序的优点就是速度快，缺点是对序列元素有要求，且其空间占用会随着序列规模的增大而增大。
以下是一个桶排序的C语言实例：
#include <stdio.h> #include <string.h> int main() { //待排序序列 const char scores[] = {71, 100, 7, 40, 88, 100, 91, 96, 71, 84, 60, 40, 71, 0, 1, 0}; //序列上下限为 0 ~ 100 的整数。 char score_bucket[101]; memset(&score_bucket, 0, 101); int count = sizeof(scores) / sizeof(char); int i; for(i = 0; i < count; i++) { score_bucket[scores[i]] += 1; } //打印结果（递减顺序） int j = 0; for(i = 100; i >= 0; i--) { if(score_bucket[i]) { for(j = 0; j < score_bucket[i]; j++) { printf("%d,", i); } } } printf("\n"); return 0; }
2、冒泡排序
冒泡排序对空间的要求非常小，时间复杂度为O(n(n+1))约等于O(n2)。
其核心原理是从头到尾两两比较，将顺序不正确的两个数互换一下位置，如此一趟下来能将符合要求的最大或最小数挪到原数据的最末位，然后再重复一次操作，只不过这次因为最末一位已经是正确的顺序了，第二轮比较就只到第n-1位了。如此循环直至原数组中已排序序列数量涨至n-1个为止即表示整个排序已完成。
以下是冒泡排序的C语言实例：
#include <stdio.h> int main() { //待排序序列 char scores[] = {71, 100, 7, 40, 88, 100, 91, 96, 71, 84, 60, 40, 71, 0, 1, 0}; int count = sizeof(scores) / sizeof(char); //序列长度 int i; int j; int loop = count - 1; //最后一个元素不用参与到排序中。 char tmp; for(i = 0; i < loop; i++) { for(j = 0; j < loop - i; j++) { if(scores[j] > scores[j + 1]) { tmp = scores[j]; scores[j] = scores[j+1]; scores[j+1] = tmp; } } } //print for(i = 0; i < count; i++) { printf("%d,", scores[i]); } printf("\n"); return 0; }
3、快速排序
桶排序速度快，但是空间消耗大。冒泡排序空间消耗小，但是速度慢。快速排序则可以一定程度上兼顾空间和时间消耗，它在数值比较上采用与冒泡排序类似的两两交换法，在空间消耗上采用函数递归调用，虽然递归调用函数也会随着序列规模上升而增长，但相对来讲空间占用还是比桶排序好很多。
快速排序的核心是选中一个基准数，在递增排序的需求下将所有大于基准数的元素放在基准数右边，将所有小于基准数的元素放在其左边。然后对分别对左半子序列和右半子序列应用同样的算法，直至子序列只剩一个元素为止。通常为了方便，基准数选第1个或最后一个。
快速排序的实现原理是将待排序序列第1个元素作为基准数，分别从序列两端收缩遍历取值。如果基准数选的是第1个，则首先从右端收缩，若基准数选的是最后一个，则首先从左端收缩。当从右端开始收缩时，一直收缩直到遇到一个数小于基准数为止，然后收缩左端，直到找到一个数大于基准数为止。然后直接交换这两个数，之后再重复两端的收缩过程，直至两端收缩碰撞为止。收缩碰撞后将碰撞值直接与基准数对调，之后便可对生成的两个子序列再分别应用此算法，直至子序列只有一个元素为止。
以下是一个C语言版的实例：
#include <stdio.h>static void quick_sort(char nums[], int start, int end) { char tmp; int i = start; int j = end; if(start >= end) return; while(1) { if(i == j) { //直接跟基数交换 tmp = nums[start]; nums[start] = nums[j]; nums[j] = tmp; //迭代左边的 if(start < j) { quick_sort(nums, start, j - 1); } //迭代右边的 if(end > i) { quick_sort(nums, i + 1, end); } //排序完成 break; } else { //j先动。 if(nums[j] < nums[start]) { //轮到i动 if(nums[i] > nums[start]) { if(i != j) { //可以交换 tmp = nums[j]; nums[j] = nums[i]; nums[i] = tmp; } } else { i++; } } else { j--; } } } } int main() { //待排序序列 char nums[] = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8}; int i; quick_sort(nums, 0, 9); for(i = 0; i < 10; i++) { printf("%d, ", nums[i]); } printf("\n"); return 0; }