[Java] Java中的快速排序(二分排序)算法实现

作者：admin，发布日期：2021-08-25
阅读：605；评论：0

快速排序由 C. A. R. Hoare（东尼霍尔，Charles Antony Richard Hoare）在 1960 年提出，之后又有许多人做了进一步的优化。该算法是冒泡排序的一种改进，同样也用到了元素交换，快速排序也是通过逐渐消除待排序的无序序列中逆序元素来实现排序的。

算法思想

1. 拿到数组后，我们会将数组中的第一个元素（通常）作为基准元素，将比基准元素小的元素放到数组左边，比基准元素大的数组右边。

   为此，我们会从基准元素开始查找比基准元素大的数，同时从另外一边开始查找比基准元素小的数，当找到这样两个数时，将其交换顺序，这样数组中的数字会被基准数分割开来，以此类推，直到左边下标=右边下标。

2. 此时基准数并不在中间，所以我们需要将当前下标的数和基准数交换，这样就就完成了第一次排序。

3. 将排序后的数组根据基准数的位置拆开，再进行同样的操作（直接递归），直到left > right结束

4. 输出结果

具体实现

import java.util.Arrays;

public class QuickSort {
    public static void quickSort(int[] arr, int left, int right) {
        if (left > right) {
            return;
        }
//        获得基准数
        int base = arr[left];
//        获得i和j,也就是最左边和最右边的索引
        int i = left;
        int j = right;
//        循环交换数字
        while (i != j) {
//            找到比基准数小的数和比基准数大的数
            while (arr[j] >= base && i < j) {
                j--;
            }
            while (arr[i] <= base && i < j) {
                i++;
            }
            // 交换这两个数
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
//        交换基准数
        arr[left] = arr[i];
        arr[i] = base;
//        递归继续对左右数组进行排序
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }

    public static void main(String[] args) {
        int[] arr = {6, 3, 7, 9, 5, 1, 4, 8};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

交换结果

[6, 3, 7, 9, 5, 1, 4, 8]
base=6
[5, 3, 4, 1, 6, 9, 7, 8]
base=5
[1, 3, 4, 5, 6, 9, 7, 8]
base=1
[1, 3, 4, 5, 6, 9, 7, 8]
[1, 3, 4, 5, 6, 9, 7, 8]
base=3
[1, 3, 4, 5, 6, 9, 7, 8]
[1, 3, 4, 5, 6, 9, 7, 8]
base=4
[1, 3, 4, 5, 6, 9, 7, 8]
[1, 3, 4, 5, 6, 9, 7, 8]
[1, 3, 4, 5, 6, 9, 7, 8]
[1, 3, 4, 5, 6, 9, 7, 8]
base=9
[1, 3, 4, 5, 6, 8, 7, 9]
base=8
[1, 3, 4, 5, 6, 7, 8, 9]
base=7
[1, 3, 4, 5, 6, 7, 8, 9]
[1, 3, 4, 5, 6, 7, 8, 9]
[1, 3, 4, 5, 6, 7, 8, 9]
[1, 3, 4, 5, 6, 7, 8, 9]
[1, 3, 4, 5, 6, 7, 8, 9]