还是为考研练练手的,希望对朋友们有点帮助.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void print_array(int n[],int size){
int i;
for(i=0;i<size;i++){
printf("%02d ",n[i]);
}
printf("\n");
}
//插入排序 O(N^2)
void insertion_sort(int array[],int size){
int i,j,t;
for(i=1;i<size;i++){
t=array[i];
for(j=i;j>0 && t<array[j-1];j--){
array[j]=array[j-1];
}
array[j]=t;
}
}
//Shell排序 时间复杂度与 g 的取值及循环算法有关，O(N)<shell sort的时间复杂度<=O(N^2)
void shell_sort(int array[],int size){
int i,j,t,g;
for(g=size/2;g>0;g/=2){
for(i=g;i<size;i++){
t=array[i];
for(j=i;j>=g && t<array[j-g];j-=g){
array[j]=array[j-g];
}
array[j]=t;
}
}
}
//堆排序 时间复杂度 O(NlogN)
void heap_sort_percolate_down(int array[],int i,int n){ //二叉堆下滤函数，此函数是较小值下滤。
int c,t;
for(t=array[i];2*i+1<n;i=c){
c=2*i+1;
if(c!=n-1 && array1<array1){ //循环下滤
c++;
}
if(t<array1){
array[i]=array1;
}
else break;
}
array[i]=t;
}
void heap_sort(int array[],int size){
int i,j,t;
for(i=size/2;i>=0;i--){
heap_sort_percolate_down(array,i,size);
}
for(j=size-1;j>0;j--){
t=array[j];
array[j]=array[0];
array[0]=t;
heap_sort_percolate_down(array,0,j);
}
}
//合并排序 时间复杂度 O(NlogN)
void merge_sort_merge(int array[],int output[],int leftStart,int rightStart,int rightEnd){ //两个已排序的数组合并
int leftEnd=rightStart-1;
int tPos=leftStart;
/*两段中按大小顺序复制*/
while(leftStart<=leftEnd && rightStart<=rightEnd){
if(array[leftStart]<=array[rightStart]){
output[tPos++]=array[leftStart++];
}
else{
output[tPos++]=array[rightStart++];
}
}
/*接下来复制没有复制完那段剩下的部分*/
while(leftStart<=leftEnd){
output[tPos++]=array[leftStart++];
}
while(rightStart<=rightEnd){
output[tPos++]=array[rightStart++];
}
}
void merge_sort_recurse(int array[],int output[],int left,int right){
if(left<right){
int center=(left+right)/2;
merge_sort_recurse(array,output,left,center);
merge_sort_recurse(array,output,center+1,right);
merge_sort_merge(array,output,left,center+1,right);
}
}
void merge_sort(int array[],int size){
int* temp=(int*) malloc(sizeof(int)*size);
merge_sort_recurse(array,temp,0,size-1);
int i;
for(i=0;i<size;i++){
array[i]=temp[i];
}
free(temp);
}
//快速排序 平均时间复杂度O(NlogN) 我这儿使用平衡快速排序方式。
void quick_sort_recurse(int array[],int left,int right){
int i,j,t,p;
if(left<right-1){
int center=(left+right)/2;
if(array[center]<array[left]){
t=array[left];
array[left]=array[center];
array[center]=t;
}
if(array[right]<array[left]){
t=array[left];
array[left]=array[right];
array[right]=t;
}
if(array[right]<array[center]){
t=array[center];
array[center]=array[right];
array[right]=t;
}
//将数组里左，中，右的值按大小排序。
p=array[center];
array[center]=array[right-1];
array[right-1]=p;
//枢纽元与right-1的值互换，互换后将left至right-2的数值按快速排序的思路分成两块。
i=left;
j=right-1;
while(1){
while(array[++i]<p){}
while(array[--j]>p){};
if(i<j){
t=array[j];
array[j]=array[i];
array[i]=t;
}
else break;
}
//此时i指向了第一个大于枢纽元的元素，将其与枢纽元互换后，即完成左右分割。
array[right-1]=array[i];
array[i]=p;
quick_sort_recurse(array,left,i-1);
quick_sort_recurse(array,i+1,right);
}
else if(left<right){
if(array[left]>array[right]){
t=array[left];
array[left]=array[right];
array[right]=t;
}
}
}
void quick_sort(int array[],int size){
quick_sort_recurse(array,0,size-1);
}
//桶排序（基数排序），时间复杂度O(N),但前提是知道数组中元素的最大值M，且M不是太大,因为要分配 M*sizeof(int) 的临时空间。
void bucket_sort(int array[],int size,int max){
int i,j,p;
p=0;
int* tArray=(int*) calloc(sizeof(int),max+1);
for(i=0;i<size;i++){
tArray[array[i]]++;
}
for(i=0;i<max;i++){
for(j=0;j<tArray[i];j++){
array[p++]=i;
}
}
free(tArray);
}
void main(int argc,char* argv[]){
int size=2000000;
srand(time(NULL));
int i;
int* array=(int*)malloc(size*sizeof(int));
for(i=0;i<size;i++){
array[i]=rand()%10000;
}
int type;
if(argc==1) type=5;
else type=atoi(argv[1]);
switch(type){
case 1:
printf("Insertion sort...\n");
insertion_sort(array,size);
break;
case 2:
printf("Shell sort...\n");
shell_sort(array,size);
break;
case 3:
printf("Heap sort...\n");
heap_sort(array,size);
break;
case 4:
printf("Merge sort...\n");
merge_sort(array,size);
break;
case 5:
printf("Quick sort...\n");
quick_sort(array,size);
break;
case 6:
printf("Bucket sort...\n");
bucket_sort(array,size,10000);
break;
default:
printf("no op");
return;
}
//print_array(array,size);
free(array);
}
下面是200万条随机数据排序的实际测试结果,可以很明显地看到不同排序算法之间的差别.插入排序就不测了,浪费CPU.
hoverlees@ubuntu:~/c/sort$ \ > time ./sort 2; \ > time ./sort 3; \ > time ./sort 4; \ > time ./sort 5; \ > time ./sort 6; \ > time ./sort 7; Shell sort... real 0m1.133s user 0m1.116s sys 0m0.020s Heap sort... real 0m0.897s user 0m0.880s sys 0m0.000s Merge sort... real 0m0.341s user 0m0.328s sys 0m0.008s Quick sort... real 0m0.311s user 0m0.308s sys 0m0.004s Bucket sort... real 0m0.063s user 0m0.048s sys 0m0.012s no op real 0m0.045s user 0m0.040s sys 0m0.004s hoverlees@ubuntu:~/c/sort$