快速排序（Quick Sort）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

import java.sql.Array;
import java.util.Arrays;
/**
     * 快速排序
     *
     * @param array
     * @param left
     * @param right
     * @return
     */
class QuickSort{
    public static int partition(int [] arr,int left,int right) {
      
        int pivot=arr[left];// 以最左边的数(left)为基准
        
        while(left<right){
            while(left<right && arr[right]>=pivot){// 从序列右端开始，向左遍历，直到找到小于base的数
                right--;
            }
            arr[left]=arr[right];// 找到了比base小的元素，将这个元素放到最左边的位置
            while(left<right && arr[left]<=pivot ){// 从序列左端开始，向右遍历，直到找到大于base的数
                left++;
            }
            arr[right]=arr[left];// 找到了比base大的元素，将这个元素放到最右边的位置
        }
        // 最后将base放到left位置。此时，left位置的左侧数值应该都比left小；
        // 而left位置的右侧数值应该都比left大。
        arr[left]=pivot;
        return left;
        
    }
    public static void quicksort(int [] arr,int left,int right) {
        // 左下标一定小于右下标，否则就越界了
        if(left<right){
        int p=partition(arr, left, right);// 对数组进行分割，取出下次分割的基准标号
        quicksort(arr, left, p-1);// 对“基准标号“左侧的一组数值进行递归的切割，以至于将这些数值完整的排序
        quicksort(arr, p+1, right);// 对“基准标号“右侧的一组数值进行递归的切割，以至于将这些数值完整的排序
        }
    }
    public static void main(String[] args) {
        int arr[] = { 6, 4, 8, 9, 2, 3, 1 };
        quicksort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
}