快排助手i-快速排序的中心思想

快速排序的中心思想

1、快速排序的中心思想

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

2) 从第一个数组开始元素作为关键数据，赋值给X，即X=A[0]；

3) 从J开始向前搜索，即从后面(J=J-1)向前搜索，找到小于X的第一个，让值与X交换；

4)从I往后搜索，即从前面(I=I+1)往后搜索，找到第一个大于X的值，让该值与X交换；

5) 重复步骤 3 和 4、直到 I=J；

例如：待排序的数组A的值是：（初始键数据：X=49）

A[0],A[1],A[2],A[3] ,A[4],A[5],A[6]：

第一次交换后：

（按照算法第三步从后面开始）

第二次后交换：

（根据算法第四步，从前面开始找>X的值，65>49、两者交换，此时：I=3）

第三步之后交换：

（按照算法第五步，再从后面执行第三步算法，找到

第四次交换后：

（按照算法第四步，从前面开始找大于X的值，97>49、两者互换，此时：J=4)

此时执行第三步时，找到I=J，所以完成快速排序后，快速排序后的结果是：即所有大于49的数字都在49的后面，所以小于49的数字都在49的前面。
快速排序就是递归调用这个过程——以49为中点划分数据序列，分别对前半部分和后半部分进行类似的快速排序，从而完成整个数据序列的快速排序，最后把这个数据序列变成有序序列，按照这个思路对上述数组A进行快速排序的全过程如图6所示：

初始状态{}

快速排序后就是分为{}49{}

前后两部分分为{}49{}快排助手i}

快速排序{}在第三步和第四步交换完成排序后变为{}。

{}第三步和第四步调换后变成{}完成排序。

快速排序的中心思想www.hdianbao.com