数据结构之——八大排序算法 (3)

  希尔排序是对插入排序的一种改进，先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2 < d1重复上述的分组和排序，直至所取的增量 =1( < …< d2< d1)，即所有记录放在同一组中进行直接插入排序为止。

#include<iostream> using namespace std; void Insert_Sort(int k[],int n) { int temp,j,i; int gap = n; do { gap = gap/3 + 1; for(i = gap; i < n; i++) { if(k[i] < k[i-gap]) { temp = k[i]; for( j = i-gap; k[j] > temp && j >= 0; j-=gap) { k[j+gap] = k[j]; } k[j+gap] = temp; } } }while(gap > 1); } int main() { int k[10] = {3,5,1,7,2,0,8,9,4,6}; Insert_Sort(k,10); for(int i = 0; i < 10; i++) cout<<k[i]<<" "; return 0; } 归并排序

归并排序，基于分治算法思想，就比如是比武大赛一样，先对数据进行分组，两两进行比较，并排序，然后将有序的两个小数组进行归并，得到一个新数组，再和其他新得到的数组进行两两归并，如此重复，直到归并为一个大数组，此时，此数组有序！

#include <iostream> using namespace std; void Merge(int array[], int start, int mid, int end) { //start到mid表示第一个数组，mid+1到end表示第二个数组 int newarray[end - start + 1]; //对两个数组进行归并 int p = start, q = mid + 1, r = 0; //分别指示第一个数组，第二个数组，和第三个新数组 while(p <= mid && q <= end) { if(array[p] <= array[q]) { newarray[r++] = array[p++]; } else { newarray[r++] = array[q++]; } } //左侧小集合还有剩余，依次归并到大集合尾部 while(p <= mid) { newarray[r++] = array[p++]; } //右侧小集合还有剩余，依次归并到大集合尾部 while(q <= end) { newarray[r++] = array[q++]; } //将大集合元素依次复制回原数组 for(int i = 0; i < end - start + 1; i++) //to do array[i+start] = newarray[i]; } void Merge_Sort(int array[], int start, int end) { int mid = (start + end) / 2; if(start < end) { Merge_Sort(array,start,mid); Merge_Sort(array,mid+1,end); //合并 Merge(array,start,mid,end); } } int main() { int k[10] = {3,9,6,1,8,4,0,7,2,5}; Merge_Sort(k,0,9); for (int i = 0; i < 10; ++i) { cout<<k[i]<<" "; } } 基数排序

个人理解(最好先了解一下桶排序)：
  从待排序数组每个数字的基数开始排序，然后一直到最大数的最高位。准备10个桶，从低位开始分别将其放入对应编号为0-9的桶中。等到低位排完得到一个子序列，再将这个序列按照次低位的大小进入相应的桶中，一直排到最高位为止，数组排序完成。
算法步骤

先找出所有数中的最高位数，即循环次数，要存入桶和出桶这么多次

每次循环用一个count[10]数组记录每个桶中的数字个数（循环开始之前，要记得将上次循环时count中保存的值初始化为0）

遍历数组中每一个数，将其放入指定的桶中

按0-9的顺序又将桶中元素存回数组，覆盖之前的值

先对个位排序

再对十位排序

继续百位

一直到最高位

此时将桶中数字依次输出，即有序！

#include <iostream> #include <cmath> using namespace std; //求数据的最大位数，可以作为对内私有的函数，先找数组中的最大数，然后求最大数的位数 int maxbit(int data[], int n) { int max = 0, bit = 0; for (int i = 0; i < n; i++) if (data[i] > max) max = data[i]; while (max != 0) { max /= 10; bit++; } return bit; } void sort(int data[], int n) { int bit = maxbit(data, n); int count[10]; //统计每个桶中数的个数 int* bucket = new int[10 * n]; //二维数组，10个桶，每个桶容量最大是n，即所有元素存到一个桶中 for (int i = 1; i <= bit; i++) //循环最高位数次 { int x = 0; for (int p = 0; p < 10; ++p) //每次将统计桶中个数的数组清零 count[p] = 0; for (int j = 0; j < n; j++) //遍历数组中每一个数，将其放入指定的桶中 { int b = data[j]; //取一个数的倒数第n位的数字，就是让它除以10的n-1次方，再取10的余数 b /= pow(10, i - 1); b %= 10; count[b]++; bucket[b * n + count[b]] = data[j]; //放入桶中 } //将桶中的数据按顺序存回数组中 for (int r = 0; r < 10; r++) { for (int t = 1; t <= count[r]; t++) { data[x] = bucket[r * n + t]; x++; } } } } int main() { int data[10] = { 34, 90, 12, 21, 128, 231412, 678, 123, 3, 10 }; sort(data, 10); for (int i = 0; i < 10; ++i) { cout << data[i] << " "; } system("pause"); }