排序算法之-快速

算法原理

丛待排序的数列中选择一个基准值，通过遍历数列，将数列分成两个子数列：小于基准值数列、大于基准值数列，准确来说还有个子数列：等于基准值即：

算法图解

1. 选出基准元素pivot（可以选择最左侧元素），设置两个指针（Java中可看成是数组索引）left和right,left指向数列最左边的元素，right指向最右侧元素
2. 进行第一次遍历，先丛right指针开始，让其指向的元素和pivot作比较，大于或等于则指针向左移动一个位置，小于则停止移动，等待left指针移动
3. 轮到left指针移动，同样先让left指向的元素和pivot做比较，小于或等于则指针向右移动，大于则停止移动
4. 此时left和right都停止移动，判断left和right是否在同一个位置，否则交换位置元素。
5. 继续丛2开始，直至left和right相交，将pivot值与left指向的元素进行交换，第一次遍历结束，获得分区指针left。
6. 再将两个子数列按照1到6的步骤继续执行，直至所有子数列排序完成。
   

算法实现

public class QuickSort {

    public void sort(int []arr){
        doSort(arr,0,arr.length-1);
    }

    public void doSort(int []arr,int left,int right){
        if(left >= right){
            return;
        }
        int partitionIndex = partition(arr, left, right);
        doSort(arr,left,partitionIndex-1);
        doSort(arr,partitionIndex+1,right);
    }

    /**
     * 右指针先往左移动
     * @param arr
     * @param left
     * @param right
     * @return
     */
    public int partition(int []arr,int left,int right) {
        int startIndex = left;
        int pivot = arr[startIndex];
        while (left < right) {
            while (left < right && arr[right] >= pivot) {
                right--;
            }
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            if (left < right) {
                swap(arr, left, right);
            }
        }
        swap(arr, startIndex, left);
        return left;
    }

    private void swap(int arr[],int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


}
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
46
47
48

测试

  public static void main(String[] args) {
       int arr[] = {9, 7, 1991, 27, -1, -10, 0,10,9,8,-1,27,-1, 2, 65, -100};

        new QuickSort().sort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "\t");
        }
    }
1
2
3
4
5
6
7
8

结果

分区实现2

  /**
     * 左指针先往右移动
     * @param arr
     * @param left
     * @param right
     * @return
     */
    public int partition(int []arr,int left,int right){
        int startIndex = left;
        int pivot = arr[startIndex];
        while (left < right) {
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            while (left < right&&arr[right] >= pivot){
                right --;
            }

            if(left < right){
                swap(arr,left,right);
            }
        }
        if(arr[left] >= pivot){
            swap(arr,startIndex,left-1);
            return left-1;
        }
        swap(arr,startIndex,left);
        return left;
    }
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