(排序大汇总.docxVIP

#include stdio.h#include time.h#include math.h#include stdlib.h#include limits.h#define SIZE 100#define MAX 1000//交换数据void Swap(int *a, int *b){ int temp; temp = *a; *a = *b; *b = temp;}//冒泡排序void BubbleSort(int *arr, int size){ int i, j; for(i=0;isize-1;i++) for(j=size-1;ji;j--) if(arr[j] arr[j-1]) Swap(arr[j], arr[j-1]);}//选择排序void SelectionSort(int *arr, int size){ int i, j, min; //找出从a[i]到a[size-1]的最小元素的位置 for(i=0;isize-1;i++) { min = i; for(j=i+1;jsize;j++) if(arr[min] arr[j]) min = j; //将a[i]与a[min]的数据交换 Swap(arr[i], arr[min]); }}//插入排序void InsertSort(int *arr, int size){ int fOut, loc, temp; for(fOut=1;fOutsize;fOut++) if(arr[fOut] arr[fOut-1]) { temp = arr[fOut]; loc = fOut; do { arr[loc] = arr[loc-1]; loc--; }while(loc0 arr[loc-1]temp); arr[loc] = temp; }}//快速排序int Partition(int *arr, int first, int last){ int i, small, x; //为了减少最差情况的出现频率而作的一种优化 Swap(arr[first], arr[(first+last)/2]); x = arr[first]; small = first; for(i=first+1;i=last;i++) if(arr[i] x) { small++; Swap(arr[small], arr[i]); } Swap(arr[first], arr[small]); return small;}void RecQuick(int *arr, int first, int last){ int pivotLoc; if(first last) { pivotLoc = Partition(arr, first, last); RecQuick(arr, first, pivotLoc-1); RecQuick(arr, pivotLoc+1, last); }}void QuickSort(int *arr, int size){ RecQuick(arr, 0, size-1);}//计数排序void CountSort(int *arr, int size){ int temp[MAX] = {0}; int i, j; for(i=0;isize;i++) temp[arr[i]]++; j = 0; for(i=0;iMAX;i++) { while(0 != temp[i]) { arr[j] = i; temp[i]--; j++; } }}//归并排序void Merge(int *arr, int start, int mid, int end){ int temp1[SIZE], temp2[SIZE]; int n1, n2; int i, j, k; n1 = mid - start + 1; n2 = end - mid; //拷贝前半部分数组 for(i=0;in1;i++) temp1[i] = arr[start + i]; //拷贝后半部分数组 for(i=0;in2;i++) temp2[i] = arr[mid + i + 1]; //把后面的元素设置的很大 temp1[n1] = temp2[n2] = INT_MAX; i = j = 0; // 逐个扫描两部分数组然后放到相应的位置去 for(k=start;k=end;k++) { if(temp1[i] = temp2[j]) { arr[k] = temp1[i]; i++; } else { arr[k] = temp2[j]; j++; } }}void RecMerge(int *arr, int start, int end)