算法四：快速排序

* 快速排序
* 设一组初始记录关键字序列为（49,38,65,97,76,13,27,49）
* 则关键字49为基准而得到的一趟快速排序结果是？

网上快速排序的说明很多，这里摘抄一个作为说明：

　　快速排序是冒泡排序的改进版，也是最好的一种内排序，在很多面试题中都会出现，也是作为程序员必须掌握的一种排序方法。

思想:1.在待排序的元素任取一个元素作为基准(通常选第一个元素，但最的选择方法是从待排序元素中随机选取一个作为基准)，称为基准元素；

2.将待排序的元素进行分区，比基准元素大的元素放在它的右边，比其小的放在它的左边；

3.对左右两个分区重复以上步骤直到所有元素都是有序的。

　　所以我是把快速排序联想成东拆西补或西拆东补，一边拆一边补，直到所有元素达到有序状态。

下面再看看示图理解下吧：

算法四：快速排序

　　6.对元素5两边的元素也重复以上操作，直到元素达到有序状态。

算法实现：

public class QuickSort {
    
    //方式一,该方法不符合分治算法
    private static int[] getQuickSortImport(int[] datas){
        //下标，左下标lindex,右下标rindex
        int lindex=1,rindex=datas.length-1;
        if(datas!=null){
            for (int i = 0; i < datas.length; i++) {
                if(lindex<=rindex){
                    System.arraycopy(getQuickSort(datas,datas[i],lindex,rindex,i),0,datas,0,datas.length-1);
                    lindex+=1;
                }else{
                    break;
                }
            }
        }
        return datas;
    }
    
    private static int[] getQuickSort(int[] datas,int key,int lindex,int rindex,int params){
        boolean flag=true;
        if(datas!=null && lindex<=rindex && rindex<datas.length){
            while (lindex<=rindex) {
                if(flag){
                    //从后向前取，比key小的数值
                    if(datas[rindex]<key){
                        datas[lindex-1]=datas[rindex];
                        datas[rindex]=key;
                        lindex+=1;
                        flag=false;
                    }
                    rindex-=1;
                }else{
                    //从前向后取，比key大的数值
                    if(datas[lindex]>=key){
                        datas[rindex]=datas[lindex];
                        datas[lindex]=key;
                        rindex-=1;
                        flag=true;
                    }
                    lindex+=1;
                }
            }
            System.out.println("输出第"+params+"趟数组信息====="+Arrays.toString(datas));
        }
        return datas;
    }
    //方式二
    public static void quickSort(int[] arr){
        qsort(arr, 0, arr.length-1);
    }
    private static void qsort(int[] arr, int low, int high){
        if (low < high){
            int pivot=partition(arr, low, high);        //将数组分为两部分
            qsort(arr, low, pivot-1);                   //递归排序左子数组
            qsort(arr, pivot+1, high);                  //递归排序右子数组
        }
    }
    private static int partition(int[] arr, int low, int high){
        int pivot = arr[low];     //枢轴记录
        while (low<high){
            while (low<high && arr[high]>=pivot) --high;
            arr[low]=arr[high];             //交换比枢轴小的记录到左端
            while (low<high && arr[low]<=pivot) ++low;
            arr[high] = arr[low];           //交换比枢轴小的记录到右端
        }
        System.out.println("输出数组信息====="+Arrays.toString(arr));
        //扫描完成，枢轴到位
        arr[low] = pivot;
        //返回的是枢轴的位置
        return low;
    }
    //方式三
    public static void quickSort2(int[] arr){
        qsort2(arr, 0, arr.length-1);
    }
    private static void qsort2(int[] arr, int low, int high){
        if (low < high){
            int pivot=partition2(arr, low, high);        //将数组分为两部分
            qsort2(arr, low, pivot-1);                   //递归排序左子数组
            qsort2(arr, pivot+1, high);                  //递归排序右子数组
        }
    }
    private static int partition2(int[] arr, int low, int high){
        int mid=(low+high)/2;
        int pivot = getMidValues(arr[low],arr[mid],arr[high]);     //枢轴记录
        while (low<high){
            while (low<high && arr[high]>=pivot) --high;
            arr[low]=arr[high];             //交换比枢轴小的记录到左端
            while (low<high && arr[low]<=pivot) ++low;
            arr[high] = arr[low];           //交换比枢轴小的记录到右端
        }
        System.out.println("输出数组信息====="+Arrays.toString(arr));
        //扫描完成，枢轴到位
        arr[low] = pivot;
        //返回的是枢轴的位置
        return low;
    }
    private static int getMidValues(int low,int mid,int high){
        if(low>mid){
            return (low>high)?(mid>high?mid:high):low;
        }else{
            return (mid>high)?(low>high?low:high):mid;
        }
    }
    
    public static void main(String[] args) {
        int[] datas={49,38,65,97,76,13,27,49};
        System.out.println("===========开始===========");
//        int[] datas2=getQuickSortImport(datas);
        quickSort2(datas);
        System.out.println("===========结束===========");
    }
}

结果：

===========开始===========
输出数组信息=====[27, 38, 13, 97, 76, 97, 65, 49]
输出数组信息=====[13, 38, 38, 49, 76, 97, 65, 49]
输出数组信息=====[13, 27, 38, 49, 49, 65, 65, 97]
输出数组信息=====[13, 27, 38, 49, 49, 65, 76, 97]
===========结束===========

算法四：快速排序

相关推荐