快速排序
快速排序算法
快速排序主要思想:递归 分治
快速排序算法原理可参考:舞动的排序算法 快速排序
复杂度分析:空间复杂度不需要额外消耗空间存储数组;时间复杂度:最差情况O(n^2),最优情况O(nlgn),一般情况O(nlgn)
实现代码如下(从文件中读取数据,排序后再存储到另外一个文件中)
#include<stdio.h> #define MAX 100 int quicksort(int *arry, int low, int high) { int ii = low; int jj = high; int key = arry[ii]; if(low>high) //如果左边数组大于右边,结束排序 return 0; while(ii<jj) { while((key<=arry[jj]) && (ii<jj)) //对右边数组排序 jj--; arry[ii] = arry[jj]; while((key>=arry[ii]) && (ii<jj)) //对左边数组排序 { ii++; } arry[jj] = arry[ii]; } arry[ii] = key; //查找一遍后将key回归 quicksort(arry, low, ii-1); quicksort(arry, jj+1, high); } int main() { int arry[MAX]; int i; int len=0; FILE *file_in,*file_out; //定义文件指针 file_in = fopen("data_in.txt","r"); if(file_in == NULL) { printf("无效的文件"); return -1; } while(!feof(file_in)) //从文件中读取待排序的数据 { fscanf(file_in,"%d",&arry[len]); len = len+1; } quicksort(arry,0,len-1); //排序函数 file_out = fopen("data_out.txt","w"); if(file_out == NULL) { printf("无法创建文档"); return -1; } for(i=0;i<len;i++) //将排序后的数据写入文件 { fprintf(file_out,"%d ",arry[i]); } fclose(file_in); fclose(file_out); return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。