快速排序的问题

网上有关“快速排序的问题”话题很是火热，小编也是针对快速排序的问题寻找了一些与之相关的一些信息进行分析，如果能碰巧解决你现在面临的问题，希望能够帮助到您。

这道题的话我不清楚是不是应该把每个选项的步骤给列下来，但是我很迷惑。

快速排序实际上是以每次都以当前数组的第一位作为基准作为比较的，所以说第一位的值的位置更靠中间（排序好的），二分法后就均匀，速度就会越快。

A选项第一次选择21将会换到17的位置，第一次变换后变为：

17，9，5，21，25，23，30

再进行一次变换，就已经排好序了

C选项同理，第一次选择将21换到30的位置，变换后变为：

5，9，17，21，25，23，30

A、C两选项第一次选择的比较次数和交换次数都相同，所以时间就看第二轮了

(17,9,5)和(5,9,17)谁快？应该是（5，9，17）快一步，因为（17，9，5）还要交换一步变成（5，9，17），然后再剩下（5，9），而（5，9，17）第一步不变化，然后剩下（9，17），两个剩下的时间（即5，9和9，17再比较一次且都是已排序的）肯定都是一样的。

所以时间就差在需要交换的一步上：

（17，9，5）->(5,9,17)->(5,9)+(17)第一步需要3步比较和一次交换；

（5，9，17）->(5,9,17)->(5)+(9,17)第一步需要3步比较无需交换；

所以选C

***********************************************************************

看了你的图，我补充下：

答案对A的解释在第一步上有误啊，怎么会变成（9,17,5,21，23,25,30）呢？

A选项第一次查找将会交换25和9的位置，9只能出现在第二位的。然后再交换21和17，只会变成17，9，5，21，25，23，30啊，答案有误！！！！

另外对于其他答案，我认为，对于算法不仅仅是交换，比较也是要算时间的，快速排序在已经排序好的数列上花的时间是最大的，平方级

但是这些在规模较小的情况下因素太多了~~

快速排序法如何排序

基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。一趟快速排序的算法是：

1）设置两个变量I、J，排序开始的时候：I=0，J=N-1；

2）以第一个数组元素作为关键数据，赋值给key，即 key=A[0]；

3）从J开始向前搜索，即由后开始向前搜索（J=J-1），找到第一个小于key的值A[J]，并与A[I]交换；

4）从I开始向后搜索，即由前开始向后搜索（I=I+1），找到第一个大于key的A[I]，与A[J]交换；

5）重复第3、4、5步，直到 I=J； (3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。找到并交换的时候i， j指针位置不变。另外当i=j这过程一定正好是i+或j+完成的最后另循环结束) 6 5 4 2 7 3 1 8

以7为key进行排序:

第一次交换：6 5 4 2 3 7 1 8

第二次交换：6 5 4 2 3 1 7 8

至此完成第一趟排序得到{6 5 4 2 3 1} 7 {8}两个部分再按以上思想进行排序；

对于前一部分假设以4为key进行排序后半部分只有一个数就不要排了:

第一次交换：4 5 6 2 3 1

第二次交换：2 5 6 4 3 1

第三次交换：2 5 6 3 4 1

第四次交换：2 5 6 3 1 4

第五次交换：2 4 6 3 1 5

第六次交换：2 3 6 4 1 5

第七次交换：2 3 4 6 1 5

第八次交换：2 3 1 6 4 5

第九次交换：2 3 1 4 6 5

至此完成第二趟排序得到{2 3 1} 4 {6 5}两个部分再按以上思想进行排序；

前半部分得到{1 2 3},后半部分得到{5 6};

至此排序结束。

希望对LZ有帮助。

第一遍 12 31 54 65 32 34 45 68 75 85 43 77 98第二遍 12 31 54 65 32 34 45 68 75 85 43 77 98第三遍 12 31 32 34 45 43 54 98 77 85 75 68 65第四遍 12 31 32 34 45 43 54 98 77 85 75 68 65第五遍 12 31 32 34 45 43 54 98 77 85 75 68 65第六遍 12 31 32 34 43 45 54 98 77 85 75 68 65第七遍 12 31 32 34 43 45 54 98 77 85 75 68 65 （左边区间所有递归完成，开始右边区间逐一递归）第八遍 12 31 32 34 43 45 54 65 68 75 85 77 98 第九遍 12 31 32 34 43 45 54 65 68 75 85 77 98第十遍 12 31 32 34 43 45 54 65 68 75 85 77 98第十一遍 12 31 32 34 43 45 54 65 68 75 85 77 98第十二遍 12 31 32 34 43 45 54 65 68 75 77 85 98第十三遍12 31 32 34 43 45 54 65 68 75 77 85 98 快速算法每次取当前无序区的第一个记录为基准，首先取12作为tep量，起始位置i=0，终止位置j=12.最外层循环，只要i 不等于 j 就扫描，内层循环，首先从右向左扫描，找到第一个小于tep的值，再交换这个值和tep，这样tep的左边都是比他小的数，再从左向右扫描，找到第1个大于tep的值，与tep交换，这样右边都是比tep大的数。接下来，递归此程序，用同样方法快速排序那个tep值的左区间和右区间。可以看做是，先得出无序区第一个在此序列里应有的位置，再依此位置为轴，排序左右区间，又分别得出左右无序区间的第一个值在序列里的应有位置。

关于“快速排序的问题”这个话题的介绍，今天小编就给大家分享完了，如果对你有所帮助请保持对本站的关注！

本文来自作者[狂志达]投稿，不代表世相号立场，如若转载，请注明出处：https://sxgwz.com/sx/56.html