概述

快速排序算法借鉴的是二叉树前序遍历的思想，最终对数组进行排序。

优点：

对于数据量比较大的数组排序，因为采用的具备二叉树二分的思想，故排序速度比较快

局限

只适用于顺序存储结构的数据排序（数组 ，ArrayList等），不适用于链式的数据结构

算法实现思路

一.将目标数组转化为这样一个数组。数组中的某个位置左边的所有数据都比该位置的数据小，该位置右边的数据都比该位置数据大。

实现思路：

1.取出数组第0个数据

2.从数组最右边开始遍历，假如遍历位置的数据比第0个位置的数据小，将该位置的数据赋值给左边指针停留下的位置。

3.改变遍历方向，从左边开始开始遍历，假如发现左边的数据比第0个位置的数据大，将该位置的数据赋值给2步骤停留下来的位置，并变换方向。

4.循环2、3步骤直到左右遍历到的下标重合
5.将取出的第0个位置的值赋值给循环结束后左右指针停留下的位置

二.借鉴前序遍历的思路，递归，最终完成排序。

代码实现

private void quickSort(int[] array, int start, int end) {        if (start >= end) {            return;        }        int key = array[start];        int left = start;        int right = end;        boolean direction = true;        L1:        while (left < right) {            if (direction) {                for (int i = right; i > left; i--) {                    if (array[i] < key) {                        array[left++] = array[i];                        right = i;                        direction = !direction;                        continue L1;                    }                }                right = left;            } else {                for (int i = left; i < right; i++) {                    if (array[i] > key) {                        array[right--] = array[i];                        left = i;                        direction = !direction;                        continue L1;                    }                }                left = right;            }        }        array[left] = key;        quickSort(array, start, left - 1);        quickSort(array, left + 1, end);    }

结果测试

 @Test    public void testQuickSort() {        int[] array = new int[]{1, 3, 4, 10, 2, 5, 6, 9, 7, 8};        quickSort(array, 0, array.length - 1);        for (int i = 0; i < array.length; i++) {            System.out.println(array[i]);        }    }

结果打印

12345678910