快速排序算法

一、快速排序

快速排序的最坏情况是O(n^2)，比如说顺序 数列的快排。但它的平均期望是O(nlogn)，且(nlogn)记号中隐含的常数因子很小，比复杂度稳定等于O(nlogn)的归并排序要小很多，所以，对绝大数顺序性较弱的随机数列而言，快速排序总要优于归并排序。

算法步骤的思想

1.从数列中挑出一个元素，称为“基准”，（pivot）。一般指定为最左边的元素。

2.重新排序数列，所有比基准值小的放在基准前面，所有元素比基准大的放在基准后面。（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区 （partition）操作。

3.递归（recursive）把小于基准值元素的子数列和大于基准元素的子数列排序。

二、动画演示

https://v.qq.com/x/page/w01315ff3b6.html   

三、代码实现 

import java.util.Arrays;

public class Sorts {
    //快速排序，递归的思想，将小于pivat的元素放在基准的左侧，将小于pivat的元素放在基准的右侧，然后分别对基准左右的序列进行快排
    public void fastSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        //递归
        fastSort(arr, 0, arr.length - 1);
    }

    private void fastSort(int[] arr, int left, int right) {
        //递归终止条件
        if (left >= right) {
            return;
        }
        //递归操作
        //1.确定基准点（指定最左边的元素）
        int pivot = arr[left];
        //2.定义两个索引i,j。分别指向序列最左边和左右边
        int i = left;
        int j = right;
        //3.再序列中找基准点的位置
        while (i < j) {
            //从右边找比基准点小的第一个元素
            while (i < j && arr[j] > pivot) {
                j--;
            }
            if (i < j) {
                //找到之后放到i的位置
                arr[i] = arr[j];
                i++;
            }
            // 从左边找比基准点大的第一个元素
            while (i < j && arr[i] < pivot) {
                i++;
            }
                if (i < j) {
                    arr[j] = arr[i];
                    j--;
                }
            }
        //存放基准点的位置
        arr[i]=pivot;
        fastSort(arr, left, i-1);
        fastSort(arr, i+1, right);
        }
        //4.对基准左右的序列进行快排
        public static void main(String[] args) {
            Sorts sorts = new Sorts();
            int[] arr = {34, 21, 5, 67, 8, 18, 90, 56};
            sorts.fastSort(arr);
            System.out.println(Arrays.toString(arr));

        }
    }

相关博客：

史上最详细图解快速排序_快速排序图解r-CSDN博客 

十大排序之冒泡排序与快速排序（详解）-CSDN博客