算法如图所示:
快速排序算法的实现依赖于按照枢轴元素x对待排序序列进行划分的过程。
对待排序序列进行划分的做法是:使用两个指针low和high分别指向待划分序列arr的范围
,取low所指向元素为枢轴,即int key=arr[low].划分首先从high所指向位置的元素起向前
逐一搜索到第一个比key小的元素,并将其设置到low所指的位置:然后从low所指位置的
元素起向后逐一搜索到第一个比key大的元素,并将其设置到high所指的位置;不断重复上述
两步直到low=high为止,最后将key设置到low与high共同指向的位置。
使用上述划分方法即可将待排序序列按枢轴元素key分成两个子序列,当然key的选择不一定
必须是arr[low],而可以是arr[low..high]之间的任何数据元素。
具体代码如下:- public class TestSort {
- public static void main(String[] args) {
- QuickSort qs=new QuickSort();
- int arr1[]={44,22,2,32,54,22,88,77,99,11};
- qs.arr1=arr1;
- qs.sort(0,qs.arr1.length-1);
- qs.printArray();
- }
- }
- //输入:数据元素数组arr,划分序列区间[low-high]
- //输出:将序列划分为两个子序列并返回枢轴元素key的位置
- class QuickSort{//算法partition实现了一次划分的过程。
- public int arr1[];
- private int partition(int[] arr,int low,int high){
- int key=arr[low];//使用arr[low]作为枢轴元素
- while(low<high){//从两端交替向内扫描
- while(low<high && arr[high]>=key)
- high--;
- arr[low]=arr[high];//将比key小的元素移向低端
- while(low<high && arr[low]<=key)
- low++;
- arr[high]=arr[low];//将比key大的元素移向高端
- }
- arr[low]=key;//设置枢轴
- return low; //返回枢轴元素位置
- }
- //在划分算法的基础上,快速排序算法的递归实现如算法sort所示
- //输入:数据元素数组arr1,数组arr1的待排序区间[low-high]
- //输出:数组arr1以关键字有序
- public void sort(int low,int high){
- if(low<high){
- int result=partition(arr1,low,high);
- sort(low,result-1);
- sort(result+1,high);
- }
- }
- public void printArray(){
- for(int i=0;i<=arr1.length-1;i++)
- System.out.print(arr1[i]+" ");
- }
- }
复制代码
|
|