交换排序——快速排序

一.基本算法

1）选择一个基准元素,通常选择第一个元素或者最后一个元素；
2）通过一趟排序讲待排序的记录分割成独立的两部分，其中基准元素左边的元素均比基准元素小，右边的元素均比基准元素大；
3）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

排序>快速排序示例">二.排序>快速排序示例

1.一趟排序的过程
这里写图片描述
2.排序的全过程

排序>快速排序的java实现">三.排序>快速排序的Java实现

java">    javadoc">/**
     * 排序>快速排序
     *javadoctag"> @param array
     */
    public static void quickSort(int[] array){
        quickSort(array,0,array.length-1);
    }

    javadoc">/**
     * 递归形式的分治排序算法
     *javadoctag"> @param array
     *javadoctag"> @param low
     *javadoctag"> @param high
     */
    public static void quickSort(int[] array, int low, int high){
        if(low < high){//递归出口
            int middle = getMiddle(array,low,high);
            quickSort(array,low,middle);
            quickSort(array,middle+1,high);
        }
    }

    javadoc">/**
     * 一趟比较，使得中轴左边的元素都比中轴小，右边的元素都比中轴大
     *javadoctag"> @param array
     *javadoctag"> @param low
     *javadoctag"> @param high
     *javadoctag"> @return  中轴的位置
     */
    public static int getMiddle(int[] array, int low, int high){
        int privot = array[low];    //数组的第一个元素作为中轴
        while(low < high){
            while(low < high && array[high]>privot){
                --high;
            }
            array[low] = array[high];   //比中轴小的记录往前移
            while(low < high && array[low]<privot){
                ++low;
            }
            array[high] = array[low];   //比中轴大的记录往后移
        }
        array[low] = privot;
        return low; //中轴的位置
    }