通过对近各大试卷题型分析，总结出 对于数据排序的十大方法，希望对大家有所帮助
方法一：冒泡排序法（升序排序法）
方法二：选择排序法
方法三：插入排序法
方法四：希尔排序法（Shell Sort）
方法五：归并排序法
方法六：快速排序法（交换排序法）
方法七：堆排序法
方法八：计数排序法
方法九：桶排序法
方法十：基数排序法
1.冒泡排序法1.1 算法描述
步骤1: 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
步骤2: 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应 该会是最大的数；
步骤3: 针对所有的元素重复以上的步骤，除了最后一个；
步骤4: 重复步骤1~3，直到排序完成。
（1）对数列的排序：
#include#define sequence 10//自定义十个元素的数列 int main() { int a[sequence] = {12,43,9,13,67,98,101,89,3,35 };//十个数的无序数列 //也可以改为用scanf输入 int i, j, t; printf("此程序使用冒泡排序法排列无序数列！n"); //冒泡排序 for (i = 0; i < 10 - 1; i++)//n个数的数列总共扫描n-1次 { for (j = 0; j < 10 - i - 1; j++)//每一趟扫描到a[n-i-2]与a[n-i-1]比较为止结束 { if (a[j] > a[j + 1])//后一位数比前一位数小的话，就交换两个数的位置（升序） { t = a[j + 1]; a[j + 1] = a[j]; a[j] = t; } } } printf("排列好的数列是：n"); //输出排列好得吃数列 for (i = 0; i < 10; i++) { printf("%d ", a[i]); } return 0; }
运行结果如下：
（2）对字符的排序
#include#define Character_groups 10//定义了十个字符的字符数组 int main() { char a[Character_groups] = { 'i','l','o','v','e','y','o','u','y','x' };//十个数的无序数列 //也可以改用scanf函数输入字符 int i, j; char t; printf("此程序使用冒泡排序法排列无序数列！n"); //冒泡排序 for (i = 0; i < 10 - 1; i++)//n个数的数列总共扫描n-1次 { for (j = 0; j < 10 - i - 1; j++)//每一趟扫描到a[n-i-2]与a[n-i-1]比较为止结束 { if (a[j] > a[j + 1])//后一位数比前一位数小的话，就交换两个数的位置（升序） { t = a[j + 1]; a[j + 1] = a[j]; a[j] = t; } } } printf("排列好的字符组是：n"); //输出排列好得吃数列 for (i = 0; i < 10; i++) { printf("%c ", a[i]); } return 0; }
运行结果如下：
对字符串的排序----（自定义函数的方法实现）
#includevoid function(char a[], int m) { //冒泡排序 int i, j; char tmp; for (i = 0; i < m - 1; i++)//n个数的数列总共扫描n-1次 { for (j = 0; j < m - i - 1; j++)//每一趟扫描到a[n-i-2]与a[n-i-1]比较为止结束 { if (a[j] > a[j + 1])//后一位数比前一位数小的话，就交换两个数的位置（升序） { tmp = a[j + 1]; a[j + 1] = a[j]; a[j] = tmp; } } } return; } int main() { void function(char a[], int);//尤其注意，此处的函数声明必须是char a[],因为这里穿的是地址，不能仅仅使用char int i; char a[10] = { 'i','l','o','v','e','y','o','u','y','x' };//十个数的无序字符数列 printf("此程序使用冒泡排序法排列无序数列！n"); function(a, 10);//调用冒泡排序 printf("排列好的字符组是：n"); //输出排列好得吃数列 for (i = 0; i < 10; i++) { printf("%c ", a[i]); } return 0; }
运行结果如下：
2.选择排序法
步骤1：初始状态：无序区为R[1…n]，有序区为空；
步骤2：第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1…i-1]和R(i…n）。该趟排 序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使 R[1…i]和R[i+1…n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
步骤3：n-1趟结束，数组有序化了。
两层for循环实现
#includeint main() { int i, j, k, n, tmp, a[1000]; printf("请输入需要排序的数据个数n"); scanf("%d",&n);// 从键盘输入待排序的数据个数 for (i = 0; i < n; i++) { // 利用for循环依次将输入的数据放置在数组中 scanf("%d",&a[i]); } for (i = 0; i < n - 1; i++) {// 外层循环 变量i控制排序总共进行n-1轮 k = i; for (j = i + 1; j < n; j++) { //内层循环 变量j控制每轮进行比较的次数 if (a[j] < a[k]) { k = j; //k记录每轮比较中的最小者的下标 if (k != i) { //将第i轮的最小者，与a[i]交换 tmp = a[i]; a[i] = a[k]; a[k] = tmp; } } } } printf("排序后的数据如下：n"); for (i = 0; i < n; i++) { // 利用for循环进行输出 printf("%dt", a[i]); } return 0; }
运行结果如下：
自定义函数的方法实现
#includevoid SelectSort(int a[], int n) { //选择排序 int mix, tmp; int i, j; for (i = 0; i < n - 1; i++) { //每次循环数组，找出最小的元素，放在前面，前面的即为排序好的 mix = i; //假设最小元素的下标 for (j = i + 1; j < n; j++) //将上面假设的最小元素与数组比较，交换出最小的元素的下标 if (a[j] < a[mix]) mix = j; //若数组中真的有比假设的元素还小，则交换 if (i != mix) { tmp = a[i]; a[i] = a[mix]; a[mix] = tmp; } } } int main() { int a[10] = { 9,1,5,8,3,7,4,6,2,0 }; int i; SelectSort(a, 10); for (i = 0; i < 10; i++) printf("%d ", a[i]); printf("n"); return 0; }
运行结果如下：
3.插入排序法
步骤1: 从第一个元素开始，该元素可以认为已经被排序；
步骤2: 取出下一个元素，在已经排序的元素序列中从后向前扫描；
步骤3: 如果该元素（已排序）大于新元素，将该元素移到下一位置；
步骤4: 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
步骤5: 将新元素插入到该位置后；
步骤6: 重复步骤2~5。
（1）简单方法实现
#include#include #define sequence 5 void insertSort(int a[]) { int i, j, temp; for (i = 1; i < sequence; i++) { temp = a[i]; //当前数小于前一位数时 if (a[i] < a[i - 1]) { //将子序列重新排列为有序序列 for (j = i - 1; temp < a[j]; j--) { a[j + 1] = a[j]; } a[j + 1] = temp; } } } int main() { int a[] = { 45,32,56,71,12 }; int i; printf("未排序前：n"); for (i = 0; i < sequence; i++) { printf("%d ", a[i]); } printf("n经过直接插入排序后：n"); insertSort(a); for (i = 0; i < sequence; i++) { printf("%d ", a[i]); } return 0; }
运行结果如下：
（2）自定义函数方法实现
#includevoid print(const int* a, const int length) { int i; for (i = 0; i < length; i++) { printf("%d ", a[i]); } putchar('n'); } void pushFront(int* a, const int length, const int key) { //将所有a[j]到a[length]都往后推一格 int tmp = a[length]; for (int i = length; i > key; i--) { a[i] = a[i - 1]; } a[key] = tmp; } void insertSort(int* a, const int length) { for (int i = 0; i < length; i++) { for (int j = 0; j < i; j++) { if (a[i] < a[j]) { pushFront(a, i, j); break; } } print(a, i + 1); } } int main() { const int length = 5; int my_array[5] = { 1,5,4,3,7 }; print(my_array, length); insertSort(my_array, length); return 0; }
运行结果如下：
（3）折半插入排序法实现
#include#define N 10 //对数组a进行折半插入排序，n为数组的长度； void Half_Sort(int a[]) { for (int i = 1; i < N; i++) { int x = a[i]; //将需要进行插入排序的元素赋值给x； int low = 0, high = i - 1; //设置折半的头和尾； while (low <= high) { int mid = (low + high) / 2; //设置中间元素，与插入的元素进行比较； if (x < a[mid]) //比较； high = mid - 1; else low = mid + 1; } for (int j = i - 1; j >= low; j--) //记录依次向后移； a[j + 1] = a[j]; //将当前这个值赋给这个元素的后一个元素； a[low] = x; //插入记录； } } int main() { int a[N] = { 3,2,8,5,4,7,6,9,1,10 }; //定义数组； printf("原始数据为:n"); for (int i = 0; i < N; i++) //输出原始数据； printf("%d ", a[i]); printf("nn"); Half_Sort(a); printf("使用插入排序后的数据为:n"); for (int i = 0; i < N; i++) printf("%d ", a[i]); printf("n"); return 0; }
运行结果如下：
