#include <iostream>#include <cstdlib>#include <ctime>inline void exch(int &A, int &B){int temp = A; A = B; B = temp;} inline void compexch(int &A, int &B){if (A > B) exch(A,B);} void selection_sort(int src[],int lengh);void insertion_sort(int src[],int lengh);void insertion_sort_adv(int src[],int lengh);void bubble (int src[] , int lengh);void quick_sort(int src[],int l, int lengh);int partition(int src[],int l, int lengh);void shell_sort(int src[], int lengh); using namespace std; int main(){ int *src; int index_i; clock_t start, finish; clock_t save[10]; int max; cout <<"enter\n"; cin >>max; src = (int *) malloc (max*sizeof(int)); for (index_i = 0; index_i < max ; index_i++) src[index_i] =max - index_i; start = clock(); selection_sort( src, max-1); finish = clock(); save[0] =finish - start ; //////////////////////////////////////////////////////////////// for (index_i = 0; index_i < max ; index_i++) //reset src[index_i] =max - index_i; start = clock(); insertion_sort(src ,max - 1); finish = clock(); save[1] =finish - start ; //////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////// for (index_i = 0; index_i < max ; index_i++) //reset src[index_i] =max - index_i; start = clock(); insertion_sort_adv(src ,max - 1); finish = clock(); save[2] =finish - start ; //////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////// for (index_i = 0; index_i < max ; index_i++) //reset src[index_i] =max - index_i; start = clock(); bubble (src , max-1); finish = clock(); save[3] =finish - start ; //////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////// for (index_i = 0; index_i < max ; index_i++) //reset src[index_i] =max - index_i; start = clock(); shell_sort (src , max-1); finish = clock(); save[4] =finish - start ; //////////////////////////////////////////////////////////////// cout << "\n "<<max<<" Itmes sorting\n"; cout << "selection sort time: " << save[0] << "ms" << endl; cout << "insertion sort time: " << save[1] << "ms" << endl; cout << "insertion sort adv time: " << save[2] << "ms" << endl; cout << "bubble time: " << save[3] << "ms" << endl; cout << "shell sort time: " << save[4] << "ms" << endl; free (src); system("pause"); return 0 ;} //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// void selection_sort(int src[],int lengh) //选择排序{ for ( int i = 0 ; i < lengh ; i++) { int min = i; for (int j = i + 1 ; j <= lengh ; j++) { if (src[j] < src[min]) min = j; exch(src[i] , src[min]); } }} void insertion_sort(int src[],int lengh) //插入排序{ /* for ( int i = 1 ; i <= lengh ; i++ ) { for ( int j = i ; j > lengh ; j--) compexch(src[j-1],src[j]); } */ int i,j; int next; for (i = 1 ; i< lengh ; i++) { next = src[i]; for (j = i - 1 ; j >= 0 && next < src[j] ; j--) src[j+1] = src[j]; src[j+1] = next; }} void insertion_sort_adv(int src[],int lengh)//改进版 插入排序{ int i; for (i = lengh ; i > 0 ; i--) compexch(src[i-1],src[i]); for ( i = 2 ; i <= lengh ; i++) { int j = i ; int v = src[i]; while ( v < src[j-1]) { src[j] = src[j-1]; j--; } src[j] = v; }} void bubble (int src[] , int lengh){ for (int i = 0 ; i < lengh ; i++) { for (int j = lengh ; j > i ; j--) { compexch(src[j-1],src[j]); } }} void quick_sort(int src[], int l,int lengh){ if ( lengh <= 0 ) return ; int i = partition(src ,0, lengh); quick_sort(src , 0 , i - 1); quick_sort(src , i + 1 , lengh);} int partition(int src[], int l,int lengh){ int i = l-1 ,j = lengh ; int v = src[lengh]; for (;;) { while (src[++i] < v) ; while (v < src[--j]) { if ( j == l) break; } if (i >= j) break; exch(src[i],src[j]); } exch(src[i],src[lengh]); return i;} void shell_sort(int src[], int lengh){ int h; for (h=1 ; h <= lengh / 9 ; h = 3*h+1) ; for ( ; h > 0 ; h /= 3) { for (int i = h; i <= lengh ; i++) { int j = i; int v = src[i]; while (j >= h && v < src[j-h]) { src[j] = src[j-h]; j -= h; } src[j] = v; } }} 测试结果大致如下:---------------------------------------------------------------selection sort time: 157163 msinsertion sort time: 39598 msinsertion sort adv time: 37767 msbubble sort time: 223095 msshell sort time: 16 ms--------------------------------------------------------------- 因为我只是将书上的算法实现代码运行了一下,所以上述各个排序算法的实现都不一定是最优的.至于如何优化,我会慢慢学习的. 如果有哪位朋友知道还望告知小弟.
评论