排序法里比较出名的,具体的算法看下图:
这篇博客说的通俗易懂:http://blog.csdn.net/morewindows/article/details/6684558
这是快速排序的基础,用代码实现如下:
void DiviedSort(int* arr_p,int start,int end)
{
int left,right,i=;
int pivot,result;
bool flag;
flag = TRUE;
pivot = arr_p[start];
right = end;
left = start;
#if DEBUG
printf("pivot:%d\r\n",pivot);
printf("L: ");
for(i=;i<end+;i++){
if(i==)
printf("_ ");
else
printf("%d ",arr_p[i]);
}
printf("\r\n");
#endif
while(left<right && flag){
while(arr_p[right]>=pivot){
right--;
if(right<=left){ //右边没有找到小于pivot的数 退出总循环
arr_p[left] = pivot; //将pivot保存到左边的坑里
flag = FALSE;
break;
}
}
if(flag){
//找到小于pivot的数移动到left
arr_p[left] = arr_p[right];
arr_p[right] = ;
left++;
if(left>=right){
flag = FALSE;
arr_p[right] = pivot;//当left右移等于right说明正好结束;
}
}else{
#if DEBUG
printf("Lf: ");
for(i=;i<end+;i++){
if(arr_p[i]==)
printf("_ ");
else
printf("%d ",arr_p[i]);
}
printf("\r\n");
#endif
break;
}
#if DEBUG
printf("R: ");
for(i=;i<end+;i++){
if(arr_p[i]==)
printf("_ ");
else
printf("%d ",arr_p[i]);
}
printf("\r\n");
#endif
while(arr_p[left]<=pivot){
left++;
if(left>=right){//左边没有找到大于pivot的数退出总循环
arr_p[right] = pivot;//保存pivot到右边的坑里
flag = FALSE;
break;
}
}
if(flag){
//找到大于pivot的数移动到right
arr_p[right] = arr_p[left];
arr_p[left] = ;
right--;
if(right<=left){
flag = FALSE;
arr_p[left] = pivot;//当right左移等于left说明正好结束
}
}else{
#if DEBUG
printf("Rf: ");
for(i=;i<end+;i++){
if(arr_p[i]==)
printf("_ ");
else
printf("%d ",arr_p[i]);
}
printf("\r\n");
#endif
break;
}
#if DEBUG
printf("L: ");
for(i=;i<end+;i++){
if(arr_p[i]==)
printf("_ ");
else
printf("%d ",arr_p[i]);
}
printf("\r\n");
#endif
}
}
运行结果是:
这个例子比较特殊。一轮就得出结果了,但是实际上要对pivot左右两边都分别递归调用这个算法,才能得到从小到大的顺序。
这里递归判断的条件是:
Left<Right
左边下标大于或者等于右边下标的时候说明数字已经按照从小到大排列。
下面是快速排序的完整代码。
//快速排序
//left:数组的起始位
//right:数组的结束位置,注意不是数组的最大容量
void QuickSort(int * arr,int left,int right)
{
int pivotNum = ;
int start,end;
if(left<right){
start = left,end = right;
pivotNum = arr[start];
while(start<end){
//从右边找一个小于pivotNum的数
while(start<end && arr[end]>=pivotNum){
end--;//右边的游标左移
}
if(start<end){
arr[start++] = arr[end];
}
//从左边找一个大于pivotNum的数
while(start<end && arr[start]<=pivotNum){
start++;//左边的游标右移
}
if(start<end){
arr[end--] = arr[start];
}
}
arr[start] = pivotNum;//这里在得出按照pivotNum比较得出顺序之后,要把中间数保存到最后游标停下的位置
QuickSort(arr,left,start-);
QuickSort(arr,start+,right);
}
}
验证代码:
int main(int argc, char *argv[]) {
int i=;
int arr[] = {,,,,,,,,,,};
QuickSort(arr,,);
for(i=;i<;i++){
printf("%d ",arr[i]);
}
printf("\r\n");
system("pause");
return ;
}
运行结果:
最后对于pivotNum中间值的选择可以随机选择也可以去中间值。
快速排序的效率问题:
如果每次确定的中值都是最小或者最大,那么时间复杂度是O(N^2);
最好的情况是中值正好是中间值,那么时间复杂度是O(nlgN);
总结:就平均效率而言,快速排序是基于关键之比较的速度最快的,平均效率是O(nlgN);
快速排序,C语言实现的更多相关文章
-
快速排序_C语言_数组
快速排序_C语言_数组 #include <stdio.h> void quickSort(int *, int, int); int searchPos(int *, int, int) ...
-
快速排序 - C语言
看了这本<数据结构与算法分析>中的快速排序. 写下自己理解后的代码,以备后用. #include "stdio.h" void insertSort(int arr[] ...
-
[数据结构] 快速排序C语言程序
//由大到小//快速排序(待排序数组,左侧起点,右侧起点) void quickSort(int *array, int l, int r) { if ( l >= r) return; int ...
-
快速排序 C语言实现
转载于> http://blog.chinaunix.net/uid-26404477-id-3329885.html 总的关键字比较次数:O(nlgn) 尽管快速排序的最坏时间为O(n2),但 ...
-
快速排序c语言实现
#include <stdio.h> void quick_sort(int* a, int n) { ) return; int i,j,tmp,k; k = a[n/]; ,j = n ...
-
P1177【模板】快速排序(JAVA语言)
import java.util.Scanner; import java.util.ArrayList; import java.util.Collections; import java.util ...
-
C语言排序
排序算法 快速排序 C语言快速排序qsort(数组,长度,元素大小,cmp函数(*,*))//注意函数cmp的参数为指针 #include <stdio.h> #include <s ...
-
PHP-----数组和常见排序算法
数组的创建 <?php //php创建数组 //第一种方法 $arr[0]=1; $arr[1]=23; $arr[2]=20; $arr[3]=43; for($i=0;$i<count ...
-
Neo4j 3.5发布,在索引方面大幅增强
Neo4j 3.5版本已正式发布,这也是Neo4j宣布企业版闭源以来发布的第一个版本. 这个版本在性能.资源使用率以及安全方面均有增强,我们可以先快速浏览一下这个版本: 全文索引 基于Index的快速 ...
-
C语言快速排序
复习快速排序,用C语言实现: #include <stdio.h> int quicksort(int begin, int end, int a[], int len); void ma ...
随机推荐
-
i18n国际化
<% request.setAttribute("date", new Date()); request.setAttribute("salary", ...
-
iOS 学习 - 10下载(3) NSURLSession 音乐 篇
使用 NSURLSession 下载,需要注意的是文件下载文件之后会自动保存到一个临时目录,需要开发人员自己将此文件重新放到其他指定的目录中 // // ViewController.m // Web ...
-
Ubuntu 开启ssh
sudo apt-get install openssh-server Ubuntu缺省安装了openssh-client,所以在这里就不安装了,如果你的系统没有安装的话,再用apt-get安装上即可 ...
-
《摇滚南京》——";人生下来就是孤独";
昨天是纪录片<摇滚南京>东南大学站的展映分享会 我不是一个摇滚迷,作为学渣狗看论文.码代码的时候会塞个耳机,平时其实民谣听得更多一点,摇滚觉得有点高大上.所以整好趁着学校有活动,也跟着高大 ...
-
CentOS7安装Hadoop2.7完整流程
总体思路,准备主从服务器,配置主服务器可以无密码SSH登录从服务器,解压安装JDK,解压安装Hadoop,配置hdfs.mapreduce等主从关系. 1.环境,3台CentOS7,64位,Hadoo ...
-
Sass学习
1.1下载地址: http://rubyinstaller.org/downloads 2.1 安装 SASS是Ruby语言写的,但是两者的语法没有关系.不懂Ruby,照样使用.只是必须先安装Ruby ...
-
整数转字符与字符转整数的C系统函数
atoi (表示 alphanumeric to integer)是把字符串转换成整型数的一个函数 http://baike.baidu.com/link?url=VTP54JT5-EY5TL0GFf ...
-
PHP集成环境自定义设置PHP版本,同时运行多个php版本,700个PHP版本随时切换,一键开启常用模块。
本文采用我自己开发的纯绿色版WAMP环境(我将这个WAMP环境命名为PHPWAMP) (PHPWAMP默认集成VC,不需要单独安装) 那么什么是WAMP环境?WAMP这个词是什么意思? Windows ...
-
FIT9132 Introduction to Databases
FIT9132 Introduction to Databases2019 Semester 1Assignment 1 - Database Design - Monash Hospital (MH ...
-
大臣的旅费|2013年蓝桥杯A组题解析第十题-fishers
标题:大臣的旅费 很久以前,T王国空前繁荣.为了更好地管理国家,王国修建了大量的快速路,用于连接首都和王国内的各大城市. 为节省经费,T国的大臣们经过思考,制定了一套优秀的修建方案,使得任何一个大城市 ...