常用排序算法的C语言版实现示例整理
所谓排序,就是要整理文件中的记录,使之按关键字递增(或递减)次序排列起来。其确切定义如下: void quick_sort1(int a[],int l,int r) { if(l >= r) return; int i,j,p; i = l-1,j = l,p = a[r]; while(j < r) { if(a[j] < p) swap(a[++i],a[j]); j++; } swap(a[++i],a[r]); quick_sort1(a,l,i-1); quick_sort1(a,i+1,r); } 《算法导论》一书中,给出了这个程序的伪代码。当数组元素相等、逆序、顺序排列时,调用这个程序会导致栈溢出。因为每次划分都是最坏坏分。可以改进一下。上述程序每次选的划分基准元素都是固定的,如果是随机产生的,那么可以大大降低出现最坏划分的概率。 void quick_sort2(int a[],j = l; p=l + rand()%(r-l); //随机产生[l,r)之间的数 swap(a[p],a[r]); p = a[r]; while(j < r) { if(a[j] < p) swap(a[++i],a[r]); quick_sort2(a,i-1); quick_sort2(a,r); } 但是,当数组元素相等时,还是出现了栈溢出。可以做如下调整。 void quick_sort3(int a[],j = r,p = a[r]; while(1) { do { i++; } while(a[i] < p && i < r); do { j--; } while(a[j] > p && j > l); if(i >= j) break; swap(a[i],a[j]); } swap(a[i],a[r]); quick_sort3(a,i-1); quick_sort3(a,r); } 但是,当数组元素顺序,逆序时,同样出现了栈溢出。若将两者结合起来,就可以尽量避免栈溢出。 void quick_sort4(int a[],j = r; p = l + rand()%(r-l); swap(a[p],a[r]); p = a[r]; while(1) { do { i++; } while(a[i] < p && i < r); do { j--; } while(a[j] > p && j > l); if(i >= j) break; swap(a[i],a[r]); quick_sort4(a,i-1); quick_sort4(a,r); } (2)冒泡排序:两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。 void bubble_sort1(int a[],int n) { int i,j; for(i = 0; i < n-1; i++) { for(j = i+1; j < n; j++) { if(a[i] > a[j]) swap(a[i],a[j]); } } } 可以稍作改进,当数组数元素顺序时,时间复杂度为O(n)。加入一个变量,如果在一遍扫描中,没有出现交换,那么结束排序,因为数组已排好序了。 void bubble_sort2(int a[],j; for(i = 0; i < n-1; i++) { bool exchange = false; for(j = i+1; j < n; j++) { if(a[i] > a[j]) { exchange = true; swap(a[i],a[j]); } } if(exchange == false) break; } } 经网友指出,上面这个冒泡排序有问题,无法得到正确结果。下面引自网友的正确写法: void bubble_sort2(int a[],j; for(i = 0;i < n-1; i++) { bool exchange = false; for(j = n-1;j > i; j--) { if(a[j-1] > a[j]) { exchange = true; swap(a[j-1],a[j]); } } if(exchange == false) break; } } (3)直接选择排序:每一趟从待排序的记录中选出关键字最小的记录,顺序放在已排好序的子文件的最后,直到全部记录排序完毕。 void select_sort1(int a[],j; for(i = 0; i < n-1; i++) { int min = i; for(j = i+1; j < n; j++) { if(a[j] < a[min]) min = j; } if(min != i) swap(a[i],a[min]); } } (4)堆排序:根据输入数据,利用堆的调整算法形成初始堆,然后交换根元素与尾元素,总的元素个数减1,然后从根往下调整。堆排序的最好、最坏、平均时间复杂度都为O(nlogn) void heap_siftdown(int a[],int n,int p) //调整算法 { int i = p,j = i*2+1; int tmp = a[i]; while(j < n) { if(j+1 < n && a[j] < a[j+1]) j++; if(a[j] <= tmp) break; else { a[i] = a[j]; i = j;j = j*2+1; } } a[i] = tmp; } void heap_sort1(int a[],int n) { int i; for(i = (n-1)/2; i >= 0;i--) heap_siftdown(a,n,i); for(i = n-1;i >= 0; i--) { swap(a[i],a[0]); heap_siftdown(a,i,0); } } (5)直接插入排序:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子文件中的适当位置,直到全部记录插入完成为止。当数组已经排好序,直接插入排序的时间复杂度为O(n) void insert_sort1(int a[],j; for(i = 1; i < n; i++) { for(j = i; j > 0 && a[j]<a[j-1]; j--) swap(a[j-1],a[j]); } } void insert_sort2(int a[],j; for(i = 1; i < n; i++) { for(j = i; j > 0 && a[j] < a[j-1]; j--) { int t = a[j-1]; a[j-1] = a[j]; a[j] = t; } } } 可以进一步改进,insert_sort2的算法不断给t赋值,可以将赋值语句移到循环外面。 void insert_sort3(int a[],j; for(i = 1;i < n; i++) { int t = a[i]; for(j = i; j > 0 && a[j-1] > t; j--) a[j] = a[j-1]; a[j] = t; } } (6)希尔排序:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。 void shell_sort1(int a[],int n) { int i = n; do{ i = i/3 + 1; shell_pass1(a,i); }while(i > 1); } void shell_pass1(int a[],int inc) //inc为1时,其实就是直接插入排序 { int i,j; for(i = inc; i < n; i++) { int t=a[i]; for(j = i;j >= inc && a[j-inc] > t; j-= inc) a[j] = a[j-inc]; a[j] = t; } } (7)归并排序:利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。可以用于外排序。 void merge_sort1(int a[],int b[],int r) { if(l >= r) return; int m = (l+r)/2; merge_sort1(a,b,m); merge_sort1(a,m+1,r); merge1(a,m,r); } void merge1(int a[],int m,int r) { int i,k; for(i = l; i <= r; i++) b[i] = a[i]; i = l; j = m+1; k = l; while(i <= m && j <= r) { if(b[i] <= b[j]) a[k++] = b[i++]; else a[k++] = b[j++]; } while(i <= m) a[k++] = b[i++]; while(j <= r) a[k++] = b[j++]; } 给出上述算法的程序的测试驱动程序及两个辅助程序。要测试某种排序算法,只需将注释去掉即可。 #include <iostream> #include <ctime> using namespace std; const int N = 100; int a[N]; int b[N]; int main() { int i; srand(time(0)); //for(i=0;i<N;i++) // a[i]= N-i; for(i = 0;i < N; i++) a[i]=rand()%N; long start,end; start = clock(); //quick_sort1(a,N-1); //quick_sort2(a,N-1); //quick_sort3(a,N-1); //quick_sort4(a,N-1); //bubble_sort1(a,N); //bubble_sort2(a,N); //merge_sort1(a,N-1); //heap_sort1(a,N); //shell_sort1(a,N); //select_sort1(a,N); //insert_sort1(a,N); //insert_sort2(a,N); //insert_sort3(a,N); end = clock(); print_array(a,N); cout<<"total time is : "<<(end-start)/1000.0<<'s'<<endl; return 0; } void swap(int a[],int i,int j) //交换元素 { int t = a[i]; a[i] = a[j]; a[j] = t; } void print_array(int a[],int n) //打印元素值 { for(int i = 0; i < n; i++) { cout<<a[i]<<' '; if(i%10==0 && i!=0) cout<<endl; } cout<<endl; }
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |