快速排序（Quick Sort）
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
1 算法描述
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下： 从数列中挑出一个元素，称为 “基准”（pivot）； 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作； 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
原理
通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。最好将基准数划分的很均匀，O(N*log2N)。当待排序的序列为正序或逆序排列时，且每次划分只得到一个比上一次划分少一个记录的子序列，最坏O(N2)
特点
快速排序越有序越慢，它要从后到前遍历找比基准小的，时间复杂度达到O(n) 快速排序的过程是选出一个作为基准，大的放在基准的右边，小的放在基准的左边，然后递归实现，所以： 基准是可以放在最终的位置的。
概述
快速排序的递归分治，可以将一个大数组切分成两部分，并可以在一个函数栈中处理独立的这两部分。当切分元素每次都刚好能将数组切分成两部分时，递归函数栈是最浅的 lgN 层，当元素以有序时，切分元素每次都只能分解一个空子序和一个包含 n-1 个元素的子序列，此时我们需要n-1此分解，即函数调用深度为 n - 1 层，而每一层都进行若干次独立的切分(partiton)算法，时间复杂度为O(N)。 这时整个排序的时间复杂度就为： O(n * n)。
3.时间空间复杂度
空间复杂度
快速排序空间复杂度为logn(因为递归调用了) ,
时间复杂度
几乎有序时， 快排的时间复杂度退化到O(nn)。 无序时， 快排才比较省时间O(nlogn) 快速排序最坏情况时间复杂度为N^2 快速排序平均复杂度为O（nlogn）；
4. 代码实现
public class QuickSort {
public static void main(String[] args) {
int[] numbers = new int[]{23, 3, 10, 0, 11, 4, 9, 1, 100, 234};
quickSort(numbers, 0, numbers.length - 1);
System.out.println(numbers);
}
public static void quickSort(int[] arry, int first, int last) {
if (last > first) {
int sentry = sort(arry, first, last);
quickSort(arry, first, sentry - 1); // 前半部分
quickSort(arry, sentry + 1, last); // 后半部分
}
}
public static int sort(int[] arry, int first, int last) {
int sentry = arry[first]; // 哨兵
int low = first + 1;
int high = last;
while (low < high) {
// 从左边开始，找到比哨兵大的数
while (low <= high && arry[low] <= sentry) {
low++;
}
// 从右边开始，找到比哨兵大的数
while (low <= high && arry[high] >= sentry) {
high--;
}
// 交换左边的比哨兵大的数和右边比哨兵小的数
if (high > low) {
int temp = arry[high];
arry[high] = arry[low];
arry[low] = temp;
}
// 继续循环，止到左右游标相遇
}
// 右边游标向左移，止到找到比哨兵小的数
while (high > first && arry[high] >= sentry) {
high--;
}
// 如果哨兵比右边游标所在数大，交换两数
if (sentry > arry[high]) {
arry[first] = arry[high];
arry[high] = sentry;
return high;
} else {
return first;
}
}
}
5.快排有两种方法
1、从第一个元素后面一个开始与后序交换，最后将停止位与第一位交换。
2、直接第一个就和后序交换，直到交换完毕。
