Java 快排 (基于数组) 附图解

采用分而治之的技术

    步骤：

    1. 确定中心元素，然后将中心元素与表的第一个元素交换

        索引smallIndex 指向小于中心元素的最后一个元素，初始化为表中的第一个元素

    2.对于表中剩余的元素

        如果当前元素小于中心元素

            a. smallIndex加1

            b. 交换当前元素和由smallIndex指向的数组元素

    3.交换第一个元素(即中心元素)和由smallIndex指向的数组元素

 

public class QuickSort {      
    private int partition(int arr[], int first, int last) {      
        int pivot;      
        int index, smallIndex;      
     
        swap(arr, first, (first + last) / 2);      
        pivot = arr[first];      
        smallIndex = first;      
     
        for (index = first + 1; index <= last; index++) {      
            if (arr[index] < pivot) {      
                smallIndex++;      
                swap(arr, smallIndex, index);      
            }      
        }      
        swap(arr, first, smallIndex);      
        return smallIndex;      
    }      
    private void swap(int[] arr, int loc, int minIndex) {      
        int temp;      
        temp = arr[loc];      
        arr[loc] = arr[minIndex];      
        arr[minIndex] = temp;      
     
    }      
    public void quickSort(int arr[], int first, int last) {      
        int pivotLocation;      
        if (first < last) {      
            pivotLocation = partition(arr, first, last);      
            quickSort(arr, first, pivotLocation - 1);      
            quickSort(arr, pivotLocation + 1, last);      
        }      
    }      
    public static void main(String[] args) {      
        QuickSort qk = new QuickSort();      
        int arr[] = { 2, 568, 34, 46, 9, 23, 89, 43, 572, 684, 783, 543 };      
        qk.quickSort(arr, 0, arr.length - 1);      
        for (int i = 0; i < 12; i++) {      
            System.out.print(arr[i] + ",");      
        }      
        // 2,9,23,34,43,46,89,543,568,572,684,783,      
    }      
}   

 

 

图解：

中心元素位于第一个数组元素的位置，下层子表的元素均小于中心元素，上层子表的元素均大于或等于中心元素。变量smallIndex包含下层子表的最后一个元素的索引，变量index包含下一个需要移动的元素的索引。按照步骤2，如果表的下一个元素arr[index]小于中心元素，就将smallIndex向前移动到下一个数组单元，并交换arr[index]和arr[smallIndex]。

上层表位于两个索引index和smallIndex之间。