#include
voidbubleSort(int data[], int n); //快速排序
voidquickSort(int data[], int low, int high); intfindPos(int data[], int low, int high); //插入排序
voidbInsertSort(int data[], int n); //希尔排序
voidshellSort(int data[], int n); //选择排序
voidselectSort(int data[], int n); //堆排序
voidheapSort(int data[], int n); void swap(int data[], inti, int j);
voidheapAdjust(int data[], inti, int n); //归并排序
voidmergeSort(int data[], int first, int last); void merge(int data[], int low, int mid, int high); //基数排序
voidradixSort(int data[], int n); intgetNumPos(intnum, intpos);
int main() {
int data[10] = {43, 65, 4, 23, 6, 98, 2, 65, 7, 79}; inti;
printf(\原先数组:\for(i=0;i<10;i++) {
printf(\ }
printf(\
/*printf(\冒泡排序:\bubleSort(data, 10); for(i=0;i<10;i++) {
printf(\ }
printf(\
printf(\快速排序:\quickSort(data, 0, 9); for(i=0;i<10;i++) {
printf(\ }
printf(\
printf(\插入排序:\bInsertSort(data,10); for(i=0;i<10;i++) {
printf(\ }
printf(\
printf(\希尔排序:\shellSort(data, 10); for(i=0;i<10;i++) {
printf(\ }
printf(\
printf(\选择排序:\selectSort(data, 10); for(i=0;i<10;i++) {
printf(\ }
printf(\
int data[11] = {-1, 43, 65, 4, 23, 6, 98, 2, 65, 7, 79}; inti;
printf(\原先数组:\
int data[11] = {-1, 43, 65, 4, 23, 6, 98, 2, 65, 7, 79}; for(i=1;i<11;i++) {
printf(\ }
printf(\
printf(\堆排序:\heapSort(data, 10); for(i=1;i<11;i++) {
printf(\ }
printf(\
printf(\归并排序:\mergeSort(data, 0, 9); for(i=0;i<10;i++) {
printf(\ }
printf(\
printf(\基数排序:\radixSort(data, 10); for(i=0;i<10;i++) {
printf(\ }
printf(\
return 0; }
/*--------------------冒泡排序---------------------*/ voidbubleSort(int data[], int n) { inti,j,temp;
//两个for循环，每次取出一个元素跟数组的其他元素比较 //将最大的元素排到最后。 for(j=0;j //外循环一次，就排好一个数，并放在后面， //所以比较前面n-j-1个元素即可 for(i=0;i data[i] = data[i+1]; data[i+1] = temp; } } } } /*--------------------快速排序---------------------*/ intfindPos(int data[], int low, int high) { //将大于t的元素赶到t的左边，大于t的元素赶到t的右边 int t = data[low]; while(low < high) { while(low < high && data[high] >= t) { high--; } data[low] = data[high]; while(low < high && data[low] <=t) { low++; } data[high] = data[low]; } data[low] = t; //返回此时t在数组中的位置 return low; } //在数组中找一个元素，对大于该元素和小于该元素的两个数组进行再排序 //再对两个数组分为4个数组，再排序，直到最后每组只剩下一个元素为止 voidquickSort(int data[], int low, int high) { if(low > high) { return; } intpos = findPos(data, low, high); quickSort(data, low, pos-1); quickSort(data, pos+1, high); } /*--------------------插入排序---------------------*/ voidbInsertSort(int data[], int n) { intlow,high,mid; inttemp,i,j; for(i=1;i //把data[i]元素插入到它的前面data[0-(i-1)]中 temp =data[i]; high = i-1; //该while是折半，缩小data[i]的范围(优化手段) while(low <= high) { mid = (low+high)/2; if(data[mid] > temp) { high = mid-1; } else { low = mid+1; } } int j = i; //让data与已经排序好的数组的各个元素比较，小的放前面 while((j > low) && data[j-1] > temp) { data[j] = data[j-1]; --j; } data[low] = temp; } } /*--------------------希尔排序---------------------*/ voidshellSort(int * data, int n) { intstep,i,j,key; //将数组按照step分组，不断二分到每组只剩下一个元素 for(step=n/2;step>0;step/=2) { //将每组中的元素排序，小的在前 for(i=step;i for(j=i-step;j>=0 && key data[j+step] = data[j]; } //和上面的for循环一起，将组中小的元素换到数组的前面 data[j+step] = key; } } } /*--------------------选择排序---------------------*/ voidselectSort(int data[], int n) { inti,j,mix,temp; //每次循环数组，找出最小的元素，放在前面，前面的即为排序好的 for(i=0;i //假设最小元素的下标 int mix = i; //将上面假设的最小元素与数组比较，交换出最小的元素的下标 for(j=i+1;j if(data[j] < data[mix]) { mix = j; } } //若数组中真的有比假设的元素还小，就交换 if(i != mix) { temp = data[i]; data[i] = data[mix]; data[mix] = temp; } } } /*--------------------堆排序---------------------*/ //堆排序将数组先组成二叉树，默认从数组的data[1]开始排，data[0]是 //无效数据 voidheapSort(int data[], int n) { inti; //先将数组组成一棵完全二叉树 //从2/n开始，就是从倒数第二排结点往前开始 for(i=n/2;i>0;i--) { heapAdjust(data, i, n); } //循环每个结点，将大的结点交换到堆顶 for(i=n;i>1;i--) { swap(data, 1, i); //每次交换完都要调整二叉树，将剩下的最大的结点交换到堆顶