c语言quicksort 快速排序
之前写过C语言快速排序的算法，今天在《数据结构》（C语言版）清华大学出版社的快排，感觉比之前的更快，于是贴出来。在我的机子上，排序100w的数据，只要0.3秒！其中我用python写了一个小脚本来生成100w个的随机数。附件为测试数据，本程序在GCC下编译通过。
#include "stdio.h"#include "time.h"int shu;int i,j,k,len;voidquick_sort(int left,int right);void read_file();void write_file();int partitions(int,int);int main(){ clock_t start, finish; double duration; read_file(); start = clock(); quick_sort(0,k); finish = clock(); duration = (double)(finish - start) / CLOCKS_PER_SEC; printf ("take %.6f second to sort %d datas \n",duration,k); write_file(); for (i=0;i<100;i++) printf("%d\n",shu); return 0;}void read_file(){ FILE * fp; char *filename = "100w.txt"; fp = fopen(filename,"r"); k=0; while (fscanf(fp,"%d\n",&shu)!=EOF) k++; fclose(fp);}void write_file(){ FILE * fp; char *filename = "sorted_100w.txt"; fp = fopen(filename,"w"); i = 0; while (i<k) { fprintf(fp,"%d\n",shu); i++; }}int partition(int left,int right){ int key = shu; while (left < right) { while (left < right && shu >= key) right--; shu = shu; while (left < right && shu <= key) left++; shu = shu; } shu = key; return left;}void quick_sort(int left,int right){ int mid ; if (left < right) { mid = partition(left,right); quick_sort(left,mid-1); quick_sort(mid+1,right); }}
页:
[1]