C语言实现数组快速排序(含对算法的详细解释)

时间:2022-09-16 23:00:46
/* 

说明: 

代码参考过网上代码,但分析为个人原创,本贴重在说明快速排序算法的思想和运行过程。 

*/ 

代码部分: 

#include<stdio.h>
#include<stdlib.h>
void quickSort(int* arr,int startPos, int endPos)
{
int i, j;
int key;
key = arr[startPos];
i = startPos;
j = endPos;
while (i<j)
{
while (arr[j] >= key && i<j)--j; //————1 从后往去前扫,直到找到一个a[j]<key或遍历完
arr[i] = arr[j];
while (arr[i] <= key && i<j)++i; //————2 从后往去前扫,直到找到一个a[i]>key或遍历完
arr[j] = arr[i];
}
arr[i] = key;
if (i - >startPos) quickSort(arr, startPos, i - ); //————1 如果key前还有两个及以上的数,排key前的数(有一个的话自然就不用排了)
if (endPos>i + ) quickSort(arr, i + , endPos);//————2 如果key后还有两个及以上的数,排key后的数
}
int main()
{
int a[], i;
for (i = ; i<; i++)
scanf_s("%d", &a[i]);
quickSort(a, , );
for (i = ; i<; i++)
printf("%d ", a[i]);
printf("\n");
return ;
} 解析部分:
/*
以数组 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
0 2 32 39 23 45 36 57 14 27 39 为例,说明核心代码的实现机制 第一轮:
首先进入quickSort(a, 0, 10); key=0,i=0,j=10,进入外层while,进入第一个内层while,由于0是数组中最小的,故j一直扫到头,j=0,arr[0] = arr[0]=0;
显然无法进入第二个内层while,由于i=j=0,结束外层while,执行a[0]=key=0;显然不进入第一个if,进入第二个if,执行quickSort(a, 1, 10);进行从a[1]到
a[10]的排序,第一轮结束。
第二轮;
执行quickSort(a, 1, 10),key=2,i=1,j=10,进入外层while,进入第一个内层while,由于2是传入段中最小的,故j一直扫到头,j=1,arr[1] = arr[1]=2;显然
无法进入第二个内层while,由于i=j=1,结束外层while,执行a[1]=key=2;显然不进入第一个if,进入第二个if,执行quickSort(a, 2, 10);进行从a[2]到
a[10]的排序,第二轮结束。
第三轮:
执行quickSort(a, 2, 10),key=32,i=2,j=10,进入外层while,进入第一个内层while,a[10]=39>key=32,--j,j变为9;a[9]=27<key=32,,退出第一个内层while,
执行a[i]=a[2]=a[j]=a[9]=27,数组变为
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
0 2 27 39 23 45 36 57 14 27 39
注意此时a[j](即a[9])的值存入a[i](即a[2])中,a[j]可以被再赋值,32呢?32怎么没了呢?注意32始终由key保存,不用担心。注意此时i=2,j=9;
程序顺次执行,满足第二个内层while,进入,开始从左往右扫。a[2]=27<key=32,++i,i变为3(注意这是必然的,因为第一次的a[i]是由上次内层while的a[j]送给
的,而送给的条件是a[j](即这里的a[i])<key);a[i]=a[3]=39>key=32,执行a[j](前边已经说过,此时a[j]=a[9]的值已保存到a[2]中,a[j]可修改)=a[9]=a[3]
=39,数组变为
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
0 2 27 39 23 45 36 57 14 39 39
注意此时a[i]=a[3]又变为可修改。
注意此时i=3<j=9,未跳出外层while。
继续执行第一个内层while,a[j]=a[9]=39>key=32,--j,j变为8(这也是必然的,道理同前边分析);a[j]=a[8]=14<key=32,退出第一个内层while,
执行a[i]=a[3]=a[j]=a[8]=14,数组变为
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
0 2 27 14 23 45 36 57 14 39 39
注意此时a[j]=a[8]又变为可修改。此时i=3,j=8;
程序顺次执行,满足第二个内层while,进入,开始从左往右扫。a[i]=a[3]=14<key=32,++i,i变为4(必然);a[i]=a[4]=23<key=32,++i,i变为5;a[i]=a[5]=
45>key=32,退出第二个内层while,执行a[j]=a[8]=a[i]=a[5]=45,数组变为
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
0 2 27 14 23 45 36 57 45 39 39
注意此时a[i]=a[5]可修改,且i=5,j=8,未跳出外层while。
继续执行第一个内层while,a[j]=a[8]=45>key=32,--j,j变为7(必然);a[j]=a[7]=57>key=32,--j,j变为6;a[j]=a[6]=36>key=32,--j,j变为5注意到此时i=j=5,
直接退出三个while。执行a[i]=a[5]=key=32,数组变为
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
0 2 27 14 23 32 36 57 45 39 39
注意此时a[5]前的数都小于key=32,a[5]后的数都大于key=32,且startPos=2,endPos=10。
显然两个if都满足,(这是人一次性判断的,计算机只能先判断第一个if,等程序再返回到本轮时再判断第二个if,我们一次性判断是为了说明方便)首先进入第一个
if,执行quickSort(a, 2, 4),排a[5]前面的a[2]到a[4](a[0],a[1]在第二轮后已排好),进入下一轮(第四轮),但第三轮未结束,因为计算机还并未判断第二个
if。
第四轮:
执行quickSort(a, 2, 4),key=a[2]=27,i=2,j=4,startPos=2,endPos=4。
进入外层while,进入第一个内层while,a[j]=a[4]=23<key=27,执行a[i]=a[2]=a[j]=a[4]=23,数组变为
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
0 2 23 14 23 32 36 57 45 39 39
此时a[j]=a[4]可修改,且i=2,j=4,程序顺次执行,进入第二个while,a[i]=a[2]=23<key=27,++i,i变为3(必然):a[i]=a[3]=14<key=27,++i,i变为4,注意到i=
j=4,退出所有循环,执行a[i]=a[4]=key=27,数组变为
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
0 2 23 14 27 32 36 57 45 39 39
此时i=j=4,startPos=2,endPos=4,显然满足第一个if不满足第二个if(key后已无数),故执行quickSort(a, 2, 3)(排a[4]前的),进入下一轮(第五轮),但
第四轮未结束,因为计算机还并未判断第二个if。
第五轮:
执行quickSort(a, 2,3),key=a[2]=23,i=2,j=3,startPos=2,endPos=3。
进入外层while,进入第一个内层while,a[j]=a[3]=14<key=23,执行a[i]=a[2]=a[j]=a[3]=14,数组变为
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
0 2 14 14 23 32 36 57 45 39 39
此时a[j]=a[3]可修改,且i=2,j=3,程序顺次执行,进入第二个while,a[i]=a[2]=14<key=23,++i,i变为3(必然):注意到i=j=3,退出所有循环,执行a[i]=a[3]=
key=23,数组变为
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
0 2 14 23 27 32 36 57 45 39 39
此时i=j=3,startPos=2,endPos=3,显然不满足第一个if,再判断第二个,也不满足,故第五轮结束,返回到上一轮(第四轮)的第二个if处,前面已经分析过,不
满足第二if,故第四轮结束,返回到上一轮(第三轮)的第二个if处(至此,到第三轮最终的a[i]=a[5]=key=32前的元素,都已排好),这次满足。执行
quickSort(a, 6, 10),排a[5]后的元素,进入下一轮(记为第四*轮,为的是与上面的第四轮区别,同时也为了体现两者的联系)。第三轮结束。
第四*轮:
执行quickSort(a, 6, 10),key=a[6]=36,i=6,j=10,startPos=6,endPos=10。
此时a[j]=a[3]可修改,且i=2,j=3,程序顺次执行,进入第二个while,a[i]=a[2]=14<key=23,++i,i变为3(必然):注意到i=j=3,退出所有循环,执行a[i]=a[3]=
a[j]=a[10]=39>key=36,--j,j变为9;a[j]=a[9]=39>key=36,--j,j变为8;a[j]=a[8]=45>key=36,--j,j变为7;a[j]=a[7]=57>key=36,--j,j变为6;注意到i=j=6,
退出所有while,执行a[i]=a[6]=key=36,数组不变。此时i=j=6,startPos=6,endPos=10。显然不满足第一个if,满足第二个if,执行quickSort(a, 7, 10)(排
a[6]后的元素),进入第五*轮,第四*轮结束。
第五*轮:
执行quickSort(a, 7, 10),key=a[7]=57,i=7,j=10,startPos=7,endPos=10。
a[j]=a[10]=39<key=57,执行a[i]=a[7]=a[j]=a[10]=39,数组变为
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
0 2 14 23 27 32 36 39 45 39 39
此时i=7,j=10,程序顺次执行,进入第二个内层while,a[i]=a[7]=39<key=57,++i,i变为8(必然);a[i]=a[8]=45<key=57,++i,i变为9;a[i]=a[9]=39<key=57,++i,
i变为10;注意到i=j=10,退出所有while,执行a[i]=a[10]=key=57。数组变为
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
0 2 14 23 27 32 36 39 45 39 57
此时i=j=10,startPos=7,endPos=10。显然满足第一个if,不满足第二个if(a[i]=a[10]后面已没有元素),执行quickSort(a, 7, 9)(排a[10]前面的元素),进入
第六*轮,但未退出第五*轮,因为计算机并还未判断第二个if。
第六*轮:
执行quickSort(a, 7, 9),key=a[7]=39,i=7,j=9,startPos=7,endPos=9。
a[j]=a[9]=39=key=39,--j,j变为8;a[j]=a[8]=4>key=39,--j,j变为7;注意到i=j=7,退出所有while,执行a[i]=a[7]=key=39,数组不变。此时i=j=7,startPos=7,
endPos=9。显然不满足第一个if(a[i]=a[7]前已无元素),满足第二个,执行quickSort(a, 8, 9)(排a[7]后面的元素),,进入第七*轮,第六*轮结束。
第七*轮:
执行quickSort(a, 8, 9),key=a[8]=45,i=8,j=9,startPos=8,endPos=9。
a[j]=a[9]=39<key=45,执行a[i]=a[8]=a[j]=a[9]=39,数组变为
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
0 2 14 23 27 32 36 39 39 39 39
此时i=8,j=9,程序顺次执行,进入第二个内层while,a[i]=a[8]=39<key=45,++i,i变为9(必然);
注意到i=j=9,退出所有while,执行a[i]=a[10]=key=57。数组变为
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
0 2 14 23 27 32 36 39 39 45 57
此时i=j=9,startPos=8,endPos=9,显然不满足第一个if,再判断第二个,也不满足,第七*轮结束。程序回到第五*轮的第二个if,前面已经分析过,不满足,故第五*轮结束。
至此,整个quickSort函数结束,数组已排好,如上所示。
*/ 如果大家觉得分析太多,不想看,建议大家按照代码手动执行一下,就豁然开朗了。当然,过程中可以结合、参考在下的分析。 代码已经过测试,在VS2013上成功运行! 发此文有两大目的: .和大家交流经验,供需要的人参考。 .在下菜鸟,代码中难免有不妥之处,恳求大神批评指正。您的批评就是在下提高的起点,对于您的批评,在下将不胜感激!

C语言实现数组快速排序(含对算法的详细解释)的更多相关文章

  1. KMP算法的详细解释及实现

    这是我自己学习算法时有关KMP的学习笔记,代码注释的十分的详细,分享给大家,希望对大家有所帮助 在介绍KMP算法之前, 先来介绍一下朴素模式匹配算法: 朴素模式匹配算法: 假设要从主串S=”goodg ...

  2. KMP算法的详细解释

    什么是kmp算法呢?这是一个处理字符串的算法,用来判断给出的模式串p是否存在于文本串t中(p的长度小于t). 在本文中,字符串储存在字符数组中,并且第一个字符放在下标为1的元素中. 那么如何理解kmp ...

  3. 【算法】C语言实现数组的动态分配

    C语言实现数组的动态分配 作者:白宁超 2016年10月27日20:13:13 摘要:数据结构和算法对于编程的意义不言而喻,具有指导意义的.无论从事算法优化方向研究,还是大数据处理,亦或者网站开发AP ...

  4. 快速排序&lowbar;C语言&lowbar;数组

    快速排序_C语言_数组 #include <stdio.h> void quickSort(int *, int, int); int searchPos(int *, int, int) ...

  5. C语言实现整数数组的逆置算法

    读入100个整数到一个数组中,写出实现该数组进行逆置的算法. 方法一: 假设100个整数读入到数组a中,算法f1的思想是分别从数组两端依次将对应数进行交换,即a[i]与a[100 - i - 1]进行 ...

  6. 【转载】经典10道c&sol;c&plus;&plus;语言经典笔试题&lpar;含全部所有参考答案&rpar;

    经典10道c/c++语言经典笔试题(含全部所有参考答案) 1. 下面这段代码的输出是多少(在32位机上). char *p; char *q[20]; char *m[20][20]; int (*n ...

  7. 我们一起来排序——使用Java语言优雅地实现常用排序算法

    破阵子·春景 燕子来时新社,梨花落后清明. 池上碧苔三四点,叶底黄鹂一两声.日长飞絮轻. 巧笑同桌伙伴,上学径里逢迎. 疑怪昨宵春梦好,元是今朝Offer拿.笑从双脸生. 排序算法--最基础的算法,互 ...

  8. 学习C语言的数组

    C语言的数组 数组声明的实例:int num[3];只要记下这个模板就好. 不建议使用变量定义数组,如果使用了变量定义数组,作为数组的元素的个数,不初始化的情况下是随机值,如果初始化会直接报错 注意: ...

  9. 使用C语言实现二维&comma;三维绘图算法&lpar;2&rpar;-解析曲面的显示

    使用C语言实现二维,三维绘图算法(2)-解析曲面的显示 ---- 引言---- 每次使用OpenGL或DirectX写三维程序的时候, 都有一种隔靴搔痒的感觉, 对于内部的三维算法的实现不甚了解. 其 ...

随机推荐

  1. Direct3D 10学习笔记(四)——Windows编程

    本篇将简单整理基本的Windows应用程序的实现,并作为创建Direct3D 10应用程序的铺垫.具体内容参照< Introduction to 3D Game Programming with ...

  2. CocoaPods的版本升级

    我们在项目开发过程中为了更好的管理项目中引用的一些第三方的开源代码,我们在项目开发中都会使用CocoaPods,在项目中不使用Cocoapods可以绕过这篇帖子,但是Cocopods升级比较快,但是怎 ...

  3. hibernate学习(设计多对多 关系 映射)

    // package org.crazy.app.domain; import java.util.HashSet; import java.util.Set; import javax.persis ...

  4. 模仿cocos2dx 风格用工厂方法,实现class A&comma;不使用宏&comma;

    class A { static A *create(); bool init(); }; A* A::create() { A *pRet=new A; if(pRet && pRe ...

  5. 六、spark常见问题总结(转载)

    问题导读 1.当前集群的可用资源不能满足应用程序的需求,怎么解决? 2.内存里堆的东西太多了,有什么好办法吗?         1.WARN TaskSchedulerImpl: Initial jo ...

  6. Docker 1&period;13 管理命令

    1.12 CLI 的问题 Docker1.12 命令行接口(CLI)有40多个*命令,这些命令存在以下问题: 没有归类组织,这让docker 新手很难学习: 有些命令没有提供足够的上下文环境,以至于 ...

  7. 老男孩Python九期全栈学习笔记4

    ---恢复内容开始--- day4 1.作业回顾 1.有变量name = 'aleX leNb',完成如下操作: 1)移除 name 变量对应的值两边的空格,并输出处理结果 2)移除 name 变量左 ...

  8. PL&sol;SQL学习笔记之存储过程

    一:PL/SQL的两种子程序 子程序:子程序是执行一个特定功能.任务的程序模块.PL/SQL中有两种子程序:函数  和  过程. 函数:主要用于计算并返回一个值. 过程:没有直接返回值,主要用于执行操 ...

  9. Android--解决EditText放到popupWindow中,原有复制、粘贴、全选、选择功能失效问题

    1.原来是将EditView放到了popupwindow,发现EditView原有的复制.粘贴.全选.选择功能失效了,所以便用DialogFragment代替了popupWindow 直接上代码 ①. ...

  10. display&lowbar;css

    display所有可选值: none block inline inline-block inherit initial unset compact & marker list-item ru ...