#include <iostream> #include <ctime> using std::cout; using std::cin; using std::endl; #define SIZE 100 bool Check(int *);//检验函数 void BubbleSortUp(int *, int n);//冒泡排序-上升 void BubbleSortDown(int *, int n);//冒泡排序下降 void InsertSort(int *, int n);//直接插入排序 int Partition(int *, int n);//快速排序 void QuickSort(int *, int n); void ShellSort(int *, int n);//希尔排序 void SelectSort(int *, int n);//直接选择排序 void Sift(int *, int, int);//建堆, 堆排序 void HeapSort(int *, int n); void Merge(int *, int *, int low, int mid, int high);//归并排序 void MergePass(int *, int *, int n, int len); void MergeSort(int *, int); int main() { int Array[SIZE];//生成随机数组 srand((unsigned)time(0)); for(int i=0; i<SIZE; i++) { Array[i] = rand()%(SIZE); } cout<<"Please choose sorting algorithm:"<<endl \ <<"1.冒泡排序(上升)"<<endl \ <<"2.冒泡排序(下降)"<<endl \ <<"3.直接插入排序"<<endl \ <<"4.快速排序"<<endl \ <<"5.希尔排序"<<endl \ <<"6.直接选择排序"<<endl \ <<"7.堆排序"<<endl \ <<"8.二路归并"<<endl; int nChoose; cin>>nChoose;//提示,选择 time_t tmStart; time_t tmEnd; switch(nChoose) { case 1: tmStart = time(0); BubbleSortUp(Array, SIZE); tmEnd = time(0); break; case 2: tmStart = time(0); BubbleSortDown(Array, SIZE); tmEnd = time(0); break; case 3: tmStart = time(0); InsertSort(Array, SIZE); tmEnd = time(0); break; case 4: tmStart = time(0); QuickSort(Array, SIZE); tmEnd = time(0); break; case 5: tmStart = time(0); ShellSort(Array, SIZE); tmEnd = time(0); break; case 6: tmStart = time(0); SelectSort(Array, SIZE); tmEnd = time(0); break; case 7: tmStart = time(0); HeapSort(Array, SIZE); tmEnd = time(0); break; case 8: tmStart = time(0); MergeSort(Array, SIZE); tmEnd = time(0); break; default: break; } /* for(int i=0; i<SIZE; i++) { cout<<Array[i]<<" "; }*///输出排序结果 bool result = Check(Array);//检验排序结果 if(true == result) cout<<"Congratulatoin, Sorting right!!!"<<endl <<"Cost "<<tmEnd - tmStart<<" s."; else cout<<"Sorry, Sorting error!!!"<<endl; return 0; } bool Check(int *Array) { bool flag = true; for(int i=0; i<SIZE-1; i++) { if(Array[i] > Array[i+1]) { flag = false; break; } } return flag; } void BubbleSortUp(int *Array, int n) { int i, j; bool flag; int temp; for(i=0; i<n-1; i++) { flag = false; for(j=n-1; j >= i+1; j--) { if(Array[j] < Array[j-1]) { flag = true; temp = Array[j]; Array[j] = Array[j-1]; Array[j-1] = temp; } } if(!flag) break; } } void BubbleSortDown(int *Array, int n)//冒泡排序下降 { int i, j; bool flag; int temp; for(i=0; i<n-1; i++) { flag = false; for(j=0; j <= n-2-i; j++) { if(Array[j] > Array[j+1]) { flag = true; temp = Array[j]; Array[j] = Array[j+1]; Array[j+1] = temp; } } if(!flag) break; } } void InsertSort(int *Array, int n)//插入排序 { int i, j; int temp; for(i=1; i <= n-1; i++) { if(Array[i] >= Array[i-1]) continue; temp = Array[i]; j = i-1; do{ Array[j+1] = Array[j]; j--; }while(Array[j] > temp); } } int Partition(int *Array, int n)//快速排序 { int i, j; int temp; i=0; j=n-1; temp = Array[0]; while(i < j) { while((i < j) && (Array[j] >= temp)) j--; if( i < j) { Array[i] = Array[j]; i++; } while((i < j) && (Array[i] <= temp)) i++; if( i < j) { Array[j] = Array[i]; j--; } } Array[i] = temp; return i; } void QuickSort(int *Array, int n) { if(n == 0) return;//递归出口 int i = Partition(Array, n); QuickSort(Array, i); QuickSort(Array+i+1, n-i-1); } void ShellSort(int *Array, int n)//希尔排序 { int d = n; int temp; int k; while(d > 1) { d = (d+1) / 2; for(int i=0; i < d; i++) { for(int j=i+d; j<n; j+=d) { if(Array[j] >= Array[j-d]) continue; temp = Array[j]; k = j-d; do { Array[k+d] = Array[k]; k-=d; }while(k >= 0 && Array[k] > temp); Array[k+d] = temp;//插入到本趟排序正确位置 } } } } void SelectSort(int *Array, int n)//直接选择排序 { int i, j, k; int temp; for(i=0; i < n-1; i++) { k = i; for(j = k+1; j <= n-1; j++) { if(Array[j] < Array[k]) k = j; } if( k != i) { temp = Array[i]; Array[i] = Array[k]; Array[k] = temp; } } } void Sift(int *Array, int start, int end)//希尔排序 { int i, j; int temp; temp = Array[start]; i=start; j=2*i; while(j < end) { if(j < end-1 && Array[j] < Array[j+1]) j++; if(temp >= Array[j]) break; Array[i] = Array[j]; i = j; j = 2*i; } Array[i] = temp; } void HeapSort(int *Array, int n) { int i; int temp; for(i=n/2-1; i >= 0; i--) Sift(Array, i, n); for(i=n-1; i>=1; i--) { temp = Array[0]; Array[0] = Array[i]; Array[i] = temp; Sift(Array, 0, i-1); } } void Merge(int *Array, int *ArrayTemp, int low, int mid, int high)//二路归并排序 { int i, j, k; i=low; j=mid+1; k = low; while(i <= mid && j <= high) { if(Array[i] <= Array[j]) ArrayTemp[k++] = Array[i++]; else ArrayTemp[k++] = Array[j++]; } while(i <= mid) ArrayTemp[k++] = Array[i++]; while(j <= high) ArrayTemp[k++] = Array[j++]; } void MergePass(int *Array, int *ArrayTemp, int n, int len) { int i; i=0; while(i+2*len-1 < n) { Merge(Array, ArrayTemp, i, i+len-1, i+2*len-1); i = i + 2*len; } if(i+len-1 < n-1) Merge(Array, ArrayTemp, i, i+len-1, n-1); else for(int j=i; j<n; j++) ArrayTemp[j] = Array[j]; } void MergeSort(int *Array, int n) { int len = 1; int ArrayTemp[SIZE];; while(len < n) { MergePass(Array, ArrayTemp, n, len); len = len*2; MergePass(ArrayTemp, Array, n, len); len = len*2; } }