快速排序是对冒泡排序的一种改进。快速排序由C. A. R. Hoare在1962年提出。它的主要思想是：将一个待排序序列分成两个部分，以其中的一个数据作为分界线，其中一部分小于这个分界线的数据，另一部分大于这个分界线的数据。因为采用递归的思想，再对这两个序列进行快速排序，直到所以的数据都是有序的。

基本步骤

假设待排序的数组为a[0...n-1]

一般都将第一个数a[i] (i = 0) 作为关键数，即快速排序的分界数。先从数组的后面开始即初值j = n-1，逐个向前进行遍历与选的的关键数进行比较(j--)，若大于等于关键数则继续遍历，否则将其与关键数所在的位置进行交换，并停止遍历且i++记录此时的i、j。
停止前面的遍历，再从数组的第i个位置开始向后进行遍历，逐个与关键数进行比较(i++)，若小于等于关键数则继续遍历，否则将其与关键数所在的位置进行交换，并停止遍历且j--记录此时的i、j。
重复上面的步骤，直到i==j就结束本次快速排序。
此时已经将其按关键数分成两个部分，再重复前面的步骤，对划分的部分进行快速排序，直到划分的组中的数据个数为1即此时所有数据有序。

根据上面的步骤，先进行关键字划分的实现

实现

排序

按照上面的步骤1、2、3实现关键字的划分即一趟完整的快速排序。
我这里没有使用数据的频繁交换，因为每次都是与关键字进行交换，所以我们可以在最后这趟快速排序完了以后再将其放到他所在的位置上。相当于数据的传递a=b,b=c,c=d,d=e最终就是a=e。

public static int sort(int[] arr, int low, int height) {
        int i = low;
        int j = height;
        int k = arr[low];//记录开始的关键数
        while (i < j) {
            while (i < j && arr[j] >= k) //先从右向左找到第一个小于k的位置
                j--;
            if (i < j) {
                arr[i] = arr[j];//将找到的数替换到i位置
                i++;
            }

            while (i < j && arr[i] <= k) //再从左向右找到第一个大于k的位置
                i++;
            if (i < j) {
                arr[j] = arr[i];//将找到的数替换到j位置
                j--;
            }
        }
        arr[i] = k;//当i == j 时,最后将最初的关键数替代到i位置
        return i;
    }

分治递归

然后就是对整个待排序数组进行分治递归逐个进行快速排序,直到划分的序列中的个数为1为止。

ublic static void quickSort(int[] arr, int low, int height) {
        if (low < height) {
            int mid = sort(arr, low, height);
            quickSort(arr, low, mid - 1);
            quickSort(arr, mid + 1, height);
        }
    }

总结

当然对于关键数的选取，也可以改变，例如选取中间的值作为关键数，至于实现原理都是一样的。快速排序的最好时间复杂度为O(logn)，最坏的时间复杂度为O(n^2)且其为不稳定排序。

转载请指明出处 idisfkj博客：https://idisfkj.github.io