個人主頁：https://chengang.plus/

文章將會同步到個人微信公眾號：Android部落格

1.1 描述

快速排序算法通過多次比較和交換來實現排序，其排序流程如下：

• (1)首先設定一個分界值，通過該分界值將數組分成左右兩部分。
• (2)將大于或等于分界值的數據集中到數組右邊，小于分界值的數據集中到數組的左邊。此時，左邊部分中各元素都小于或等于分界值，而右邊部分中各元素都大于或等于分界值。
• (3)然后，左邊和右邊的數據可以獨立排序。對于左側的數組數據，又可以取一個分界值，將該部分數據分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側的數組數據也可以做類似處理。
• (4)重復上述過程，可以看出，這是一個遞歸定義。通過遞歸將左側部分排好序后，再遞歸排好右側部分的順序。當左、右兩個部分各數據排序完成后，整個數組的排序也就完成了。

1.2 代碼

public class HelloWorld {
    static int[] numbers = {5,4,3,7,2,1,8,9,6,2};
    
    public static void quickSort(){
        int size = numbers.length;
        sort(0,size - 1);
    }
    
    public static void sort(int left,int right){
        int front = left;
        int later = right;
        int standardNumber = numbers[left];
        while(front < later){
            //front large number to later,and later small number at front
            while(numbers[front] < standardNumber && front < later){
                ++front;
            }
            //later small number to front, and front large number to later
            while(numbers[later] > standardNumber && front < later){
                --later;
            }
            if(numbers[front] == numbers[later] && front < later){
                ++front;
            } else {
                int temp = numbers[front];
                numbers[front] = numbers[later];
                numbers[later] = temp;
            }
        }
        if(front - 1 > left){
            sort(left ,front - 1);
        }
        if(later + 1 < right){
            sort(later + 1 ,right);
        }
    }
    public static void main(String []args) {
        quickSort();
        for(int value : numbers){
            System.out.println("quick value is:" + value);
        }
    }
}

1.3 總結

5437218962

2437218965

2435218967

2435218967

2431258967

• 1挪到了5前面，導致后面的序號小于前面的序號，此時發(fā)生了第一次遞歸。

• 遞歸范圍是：24312，按照上述步驟繼續(xù)排序，排序完成之后，得到12234。

• 在歸的過程中，再一次調用sort(later + 1,right)發(fā)生遞歸，其實是比較右半部分：8967，此時繼續(xù)上面的排序步驟，得到6789。

• 最終排序完成。

過程如下圖所示：

快速排序.jpg