排序算法 #7 双路快排

动画演示

定义变量b，指向数组中的第一个元素；定义变量e指向数组的末尾元素。

定义变量i，指向变量b所指向的下一个元素；定义变量j指向末尾元素。

我们将变量b所指向的元素4作为基准元素。

接着，我们先看变量i所指向的元素，在这里变量i指向元素2小于基准元素4，不做操作。

变量i向后移动一个位置，此时变量i指向的元素4等于基准元素4，不做操作。

变量i继续向后移动一个位置，此时变量i指向的元素9大于基准元素4，从左往右的考察先停止。

接着看变量j所指向的元素。在这里变量j指向的元素4等于基准元素4，不做操作。

变量j继续向前移动一个位置，此时变量j所指向的元素6大于基准元素4，不做操作。

变量j继续向前移动一个位置，此时变量j所指向的元素3小于基准元素4，从右往左的考察停止。

接下来需要做的就是将变量i和变量j所指向的元素进行位置交换。

交换位置之后，数组元素顺序如下图。

接着分别将变量i向后移动一个位置，变量j向前移动一个位置。

此时，变量i的值大于变量j的值。需要做的是将变量b所指向的基准元素4和变量j所指向的元素3进行位置交换。

完成位置交换后，基准元素4前面的元素都是小于等于基准元素的，而其后面的元素都是大于等于基准元素的。

对于小于等于基准元素的部分和大于等于基准元素的部分，分别重复上述过程，直到每一部分为空或只包含一个元素时双路快排结束。

02代码实现

public static void sort(int[] arr) {    quickSort(arr, 0, arr.length - 1);}
public static void quickSort(int[] arr, int b, int e) {    if (b >= e) {        return;    }
    int p = partition(arr, b, e);    // 对基准元素的前面元素进行快排    quickSort(arr, 0, p - 1);    // 对基准元素的后面元素进行快排    quickSort(arr, p + 1, e);}
private static int partition(int[] arr, int b, int e) {    // 基准元素    int basicValue = arr[b];
    int i = b +1, j = e;
    while (true) {        // 从左往右考察        while (i <= e && arr[i] - basicValue <= 0) {            i++;        }
        // 从右往左考察        while (j >= b + 1 && arr[j] - basicValue >= 0) {            j--;        }
        // 如果i大于j，则表示所有元素考察完毕        if (i > j) {            break;        }
        swap(arr, i, j);        i++;        j--;    }
    swap(arr, b, j);    return j;}

private static void swap(int[] arr, int m, int n) {    int temp = arr[m];    arr[m] = arr[n];    arr[n] = temp;}

更多相关文章

随机推荐