快速排序

Li_XiaoJin

发布于 2022-06-10 21:51:25

1220

发布于 2022-06-10 21:51:25

文章被收录于专栏：Lixj's BlogLixj's Blog

关于快速排序的相关内容

快速排序的思路：

从数组中选一个数做为基准值，一般选第一个数，或者最后一个数。
采用双指针(头尾两端)遍历，从左往右找到比基准值大的第一个数，从右往左找到比基准值小的第一个数，交换两数位置，直到头尾指针相等或头指针大于尾指针，把基准值与头指针的数交换。这样一轮之后，左边的数就比基准值小，右边的数就比基准值大。
对左边的数列，重复上面1，2步骤。对右边重复1，2步骤。
左右两边数列递归结束后，排序完成。

https://lixj.fun/upload/2021/07/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F-eadb58e4707d48d6a047cecc1b637849.gif

算法复杂度：O(nlogn)

算法空间复杂度：O(1)

算法稳定性：不稳定

public class QuickSort {

    public static void quickSort(int[] arr, int low, int high) {
        int i,j,temp;
        if (i > j) {
            return;
        }

        i = low;
        j = high;

        temp = arr[low];

        while (i < j) {
            while (arr[j] >= temp && i < j) {
                j--;
            }

            while (arr[i] <= temp && i < j) {
                i++;
            }

            if (i < j) {
                // 交换i和j的值
                swap(arr, i, j);
            }
        }
        // 交换low 和 i 的值
        swap(arr, low, i);

        quickSort(arr, low, i-1);
        quickSort(arr, i+1, high);

    }

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


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