快速排序作为分治法的一种,也同样遵循分治法的基本步骤---分解、治之、合并。我们在分解之前得选一个元素元素作为分解的依据,相当于一个基本点。
分解:以支点为界将序列分解为两个子序列,其中一个子序列里的元素小于等于支点,另一个子序列的元素大于支点。
治之:对两个子序列进行快速排序(递归)。
合并:将排好序的两个子序列合并成一个大序列。
例如有一个数组A[p,r],p代表数组首元素的下标,而r则代表数组末元素的下标。则对其进行快速排序的过程为:
- quick(A,p,r)
- {
- if(p<r)
- {
- q = partition(A,p,r);
- quick(A,p,q-1);
- quick(A,q+1,r);
- }
- }
上面这个排序过程的关键就是partion这个过程,它对数组A进行就地重排。下面我们来看看partion这个过程的实现::
- partition(A,p,r)
- {
- x = A[r];
- i = p-1; //i初始化为子序列第一个元素的下标减1
- for(j=p;j<r;j++)
- {
- if(A[j]<=x)
- {
- i++;
- exchange A[i]<-->A[j]
- }
- }
- exchange A[i+1]<-->A[r]
- return i+1;
- }
在这里我们取子序列中最后一个元素作为支点元素:下面的图为上面算法过程的图示
在执行到 h 的时候循环已跳出,交换A[i+1] 与A[r] 。至此所有比支点小的元素都已放在了支点的左边,而所有比支点元素大的数也都放在了其右边,将i+1返回,partition函数的功能完成。则第一个子序列为 (2,1,3) 第二个子序列为(7,5,6,8)。下面对这两个子序列分别进行quick(),当p不小于 r 时递归结束,下面进行合并,由于我们这儿排序
是就地排序所以合并这个环节也就可以省去了。。
阅读(1021) | 评论(0) | 转发(0) |