快速排序简介

快速排序是对冒泡排序的一种改进,通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据比另外一部分所有的数据都小,然后按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序列。

思路分析

以{5,3,7,6,8,2,9}为例,我们这里以中间数6为基数进行快速排序（下面红色数字表示基数）
初始数据 {5,3,7,6,8,2,9}
第1轮划分后的数据 {5,3,2}6 {8,7,9}
第2轮划分后的数据 {2} 3 {5}6 {8,7,9}
第3轮划分后的数据 {2} 3 {5}6 7 {8,9}
第3轮划分后的数据 {2} 3 {5}6 7 8 {9}
有序序列{2,3,5,6,7,8,9}

代码实现

public class QuickSort {
    public static void main(String[] args) {
        int[] array = {5,3,7,6,8,2,9};
        quick(array,0,array.length-1);
        System.out.println(Arrays.toString(array));
    }

    public static void quick(int[] array,int left,int right){
        int l = left;
        int r = right;
        //基数
        int pivot = array[(left+right)/2];
        int temp;
        while(l<r){
            //找一个不大于基数的元素
            while(array[r]>pivot){
                r--;
            }
            //找一个不小于基数的元素
            while(array[l]<pivot){
                l++;
            }
            if(l == r){
                //当l==r时说明遍历完了所有的元素就退出循环
                break;
            }
            //如果l<r 找个了两个符合条件的元素
            //调换这两个元素的位置
            temp = array[r];
            array[r] = array[l];
            array[l] = temp;
            //如果l指向的元素刚好等于基数就让r向前移动一格
            if (array[l] == pivot){
                r--;
            }
            //如果r指向的元素刚好等于基数就让l向后移动一格
            if (array[r] == pivot){
                l++;
            }
        }
        //程序运行到这l和r的值是相等的
        if(left<r){
        	//递归调用排序左边部分
            quick(array,left,r-1);
        }
        if (right>l){
        	//递归调用排序右边部分
            quick(array,l+1,right);
        }
    }
}

结果输出

[2, 3, 5, 6, 7, 8, 9]

Process finished with exit code 0