3.3 快速算法及思想
快速排序算法的基本思想：采用分而治之的办法对一个表进行排序，任取待排序对象序列中的某个对象（例如取第一个对象）作为基准，按照该对象的关键码大小，将整个对象序列划分为左右两个子表－low和high：
（1）左侧子序列low中所有对象的关键码都小于或等于基准对象的关键码；
（2）右侧子序列high中所有对象的关键码都大于或等于基准对象的关键码。
基准对象则排在这两个子序列中间。然后再按此方法对low和high两部分数据分别进行快速排序，其整个过程可以递归进行，从而使整个数列变成有序序列。
假设要排序的数列为A[1]……A[N],我们首先要取一个数据作为关键数据，一般情况下都是取第一个数据为关键数据。然后将所有小于它的数据放在它前面，所有大于它的数放在它后面，这个过程就称为一趟快速排序。算法的步骤如下：
（1）、设置两个变量int=i，j，在排序开始的时候，i=1,j=N；
（2）、以第一个数据为关键数据，定义为key，即key=A[1]；
（3）、从变量j向前搜索，即由右至左的搜索(j:=j-1)，找到小于key的数据，两者交换；
（4）、从变量i向后搜索，即由左至右的搜索(i:=i+1)，找到大于key的数据，两者交换；
（5）、重复排序步骤（3）和（4），直到i=j。
4.7 系统的特点
在运行本系统的时候，选择不同的菜单选项，能够清楚的看出各种排序过程的变化，例如：
（1）选择“冒泡法排序”时，可以看见绿色的长条逐渐向左移动，完全验证了冒泡排序算法的思想。
（2）选择“选择法排序”时，可以看见绿色的长条是被交换到左边的过程，这个也完全证明了选择排序算法的思想。
（3）选择“快速法排序”时，可以看见整个序列在经过i=j的过程后，被分成了2个子序列，再排列两个子序列后完成排序，这个也验证了快速排序算法的思想。
（4）选择“同时排序”时，可以清楚的看见三种算法之间效率的不同。通过观看比较出谁快谁慢，体现出快速排序的优越性。
|
