大家好，我是考100分的小小码 ，祝大家学习进步，加薪顺利呀。今天说一说快速排序算法（快速排序怎么样算一趟）,希望您对编程的造诣更进一步.
快速排序详细解说
1、单趟排序
1、把第一个元素命名为关键key，让begin指针指向首元素，end指针指向尾元素
2、end从左向右找小(小于key的元素)，begin从右向左找大(大于key的元素)
3、交换end和begin指向的元素
4、end继续找小，begin继续找大，再交换。
5、直到end等于begin，就让key与begin指向的元素交换。
2、过程演示
不难发现，经过一趟排序后，key左边都是比它小的元素，key右边都是比它大的元素。所以key就排到了自己该有的位置
即单趟排就能排好一个元素(排好的元素就不用动了)。
若我们在key左边的数组再次用单趟排(选一个新key)，在key右边的数组用单趟排，则就又能排好一个元素。
当我们不断递归下去，直到key左边和右边的数组元素只有一个时，此时key左边和右边都有序，整个数组就有序了。
3、具体代码
1、基本思路
1、把第一个元素挖走放到key，第一个位置成坑
2、end(最后一个元素的指针)找小，找到后把元素扔到坑里，end处形成新的坑
3、begin(第一个元素的指针)找大，找到后把元素扔到坑里，begin处形成新的坑
4、不断地找小找大，当end等于begin时(此处为坑)，把key值放到坑
5、递归左边，递归右边
2、具体代码
1、基本思路
1、定义一个前指针指向第一个元素，定义一个后指针指向前指针的后一个位置。
2、cur找小，遇到比keyi小的值就停下，并且prev指针++，交换两个指针的值
3、cur走到底后，把prev位置的值与keyi位置交换
4、递归左边，递归右边
2、具体代码
1、基本思想
1、让要排序的元素都入栈
2、让所以元素出栈，对出栈元素进行一趟排序(排好一个元素key)。
3、若key右边还有两个以上元素，让key右边元素都入栈；若key左边还有两个以上元素，再让左边元素都入栈
4、让左边元素都出栈，进行一趟排序；让右边元素都出栈，进行一趟排序
5、不断循环，直到key左边和右边都只有一个元素，都不需要入栈；即栈为空，就退出循环
2、具体代码
T=单趟所用时间*排序趟数
1、单趟排序所用时间(以左右指针法为列)
当左右指针相遇时，排序停止，所以用时N
2、排序趟数
第一趟排好一个元素
递归左边，右边；选出两个key
第二趟排好两个元素（一共排好了3个元素，把数组分成了四段）
选出四个key
第三趟排好四个元素
。。。。。
所以排序趟数为logN
快排时间复杂度为N*logN
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
转载请注明出处: https://daima100.com/23627.html
