对数组int a[5] = { 3, 4, 2, 1, 5 }进行快速排序。
划分出两个子序列的方法:
1、找到中值key:一般来说任意找一个即可,比如key = 2。我们把值大于2的数排在右边,不大于2的数排在左边。
2、将key 的值和首元素值交换(如果我们取)。
2 4 3 1 5
3、然后在次和尾分别设置指针i = 1,j = len - 1
2 4 3 1 5
^ ^
i=1 j=4
从i=1开始,左往右,当发现a[i]的值比key大,则将a[i]和a[j]交换,并且j--;否则i++
-------------------------
2 5 3 1 4
^ ^
i=0 j=2
-------------------------
2 1 3 5 4
^ ^
i=0 j=2
-------------------------
2 1 3 5 4
^ ^
i=1j=2
-------------------------
2 1 5 3 4
^
i=1
j=1
-------------------------
4、此时,i(j)左边的数都不大于key,i(j)右边的数都大于2,只需判断a[i](a[j])和key的关系。
1)若a[i]<key, 说明a[i]属于第一子序列,我们应该交换a[i]和key的值。a[i]被交换到首位置,key被交换到分界处。
并且我们把key并到第二序列里,这样可以在i = len - 1时不至于第二序列分不到元素。
2)否则说明a[i]属于第二子序列。
第一序列a[0]~a[i-1],第一序列a[i]~a[len-1];
简要来说就是
if( a[i] < key ) a[i]<-->a[0];
len_1 = i;