温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

快速排序的总结

发布时间:2020-07-24 11:08:07 来源:网络 阅读:310 作者:buzhbuzh 栏目:编程语言

快速排序的思想是分而治之,利用递归达到快速排序的效果

首先要选定一个基准数,一般选择最左边的数为基准数,排序的目标就是让这个基准数的左边全小于这个基准数,右边全大于这个基准数。然后以这个基准数为分隔线,在左右两侧再次调用这个排序的函数,直到全部有序。简述过程:

以  8 9 4 7 2 6 首选

1. 选择两个哨兵 i,j 分别指向8,6,基准数为8

2.从j哨兵开始,因为j指向的6小于基准数8,不符合j指向的数都要大于8的要求,所以将j指向的数覆盖i指向的数,同时i指向的数变成9

6 9 4 7 2 6

3.此时i指向9大于基准数8,不符合基准数左边的都要小于基准数,右边的都要大于基准数,所以i指向的数覆盖j指向的数,同时j--,j指向7

6 9 4 7 2 9

重复以上步骤,直到 哨兵i 和 哨兵j相遇

4.最后一步将基准值放到中间 

代码实现:

void QuickSort(int a[], int low, int high)

{

int i = low, j = high;//每次i,j都指向最低一个元素,和最高一个元素

int temp = a[low];//每次选择最左边的数为基准数

while(i < j)//每次循环结束的条件是 i == j

{

while(i < j && a[j] >= temp) j--;//先从左边开始,找到小于基准数的数

if(i < j){

a[i] = a[j];

i++;

}//和i指向的数交换

while(i < j && a[i] <= temp) i++;//找到基准数左边大于基准数的数

if(i < j){

a[j] = a[i];

j--;

}//换到基准数右边去

}//以上执行完后,将基准数放到中间

a[i] = temp;

if(low < i)//如果是基准数左边的话

     QuickSort(a, low, i-1);//将最高位i-1

if(i < high)//如果是基准数右边的话

QuickSort(a, j+1, high);//最低位为基准位+1

}




向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI