快速排序为什么要右先移动
来源：学生作业帮助网 编辑：六六作业网 时间：2024/12/24 07:18:13
快速排序为什么要右先移动
快速排序为什么要右先移动
快速排序为什么要右先移动
基本思想是：通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列.
设要排序的数组是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有帮助.