简介
快速排序（Quicksort）是对冒泡排序的一种改进。
创始人：C. A. R. Hoare
出现的时间：1960年
快速排序算法的原理
基本思想
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序
简单说明
- 通过设置分界值将原序列分为两部分，（现在讨论升序的情况，降序则相反）左边部分的所有值都小于或等于分界值，右边部分的所有值都大于或等于分界值。然后进行步骤2。
- 对步骤1中产生的两部分分别再次按步骤1执行一次。（这里其实已经产生了递归）
具体步骤
首先设定一个分界值，通过该分界值将数组分成左右两部分。
将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
对具体步骤的解释
对上面具体步骤的抽象解释如下：
- 对与一个数组设置一个分界值，然后用分界值与数组中的每一个元素（除分界值自己外）比较，所有满足条件的（比如升序，被对比元素的元素应该小于分界值）元素应该从数组头部开始依次往尾部方插入；相反，所有-不满足条件的元素应该从数组的尾部开始依次往头部方向插入。
- 分界值自己除了作为对比值，还充当了空位置的角色，用于安置（实际上就是交换）满足或不满足条件的元素。
例
有了上面的介绍，相信你已经对快速算法有了一个基本的认识，下面来看一个例子：
对数组[3,1,4,2,5]使用快速排序算法（升序），主要说明一趟排序（相当于递归调用的第一层）过程：
- 设置临界值为
3 - 3和5比较，满足升序，不交换
- 3和2比较，不满足升序，交换，数组变为：
[2,1,4,3,5] - 3和1比较，满足升序，不交换
- 3和4比较，不满足升序，交换，数组变为：
[2,1,3,4,5] - 一趟排序完成
（说白了就是临界值一直充当被交换的角色，不断的把在前的不满足条件的元素往后挪，在后的满足条件的元素往前挪，所以它自己也要不断的前后移动，直到找到真正属于它的位置）
快速排序算法的Java实现
核心代码
public void sort(boolean isAscending) {
int[] data = super.getData();
if (data == null || data.length < 2) {
return;
}
//一趟排序
this.quickSort(0, data.length - 1, isAscending);
}
//快速排序方法需要三个关键参数，设置排序区间的头、尾数组下标和排序方式标志
private void quickSort(int headIndex, int tailIndex, final boolean isAscending) {
if (tailIndex - headIndex < 0) return;
int[] data = super.getData();
int key = data[headIndex];
int i = headIndex, j = tailIndex;
boolean isTail = true;
while (i != j) {
if (isTail) {
boolean c1 = isAscending && data[j] < key;
boolean c2 = !isAscending && data[j] > key;
if (c1 || c2) {
swap(data, i, j);
i++;
isTail = false;
continue;
}
j--;
} else {
boolean c1 = isAscending && data[i] > key;
boolean c2 = !isAscending && data[i] < key;
if (c1 || c2) {
swap(data, i, j);
j--;
isTail = true;
continue;
}
i++;
}
}
//递归排序
this.quickSort(headIndex, i - 1, isAscending);
this.quickSort(i + 1, tailIndex, isAscending);
}
全部代码（包导入信息自己设置）
AbstractSort.java
public abstract class AbstractSort {
private int[] data;
public AbstractSort(int[] data) {
this.data = data;
}
public abstract void sort(boolean isAscending);
public void sort() {
this.sort(true);
}
public int[] getData() {
return data;
}
public void print() {
for (int i : this.data) {
System.out.println(i);
}
}
protected void swap(int[] data, int indexA, int indexB) {
int temp = data[indexA];
data[indexA] = data[indexB];
data[indexB] = temp;
}
}
QuickSort.java
public class QuickSort extends AbstractSort {
public QuickSort(int[] data) {
super(data);
}
@Override
public void sort(boolean isAscending) {
int[] data = super.getData();
if (data == null || data.length < 2) {
return;
}
this.quickSort(0, data.length - 1, isAscending);
}
private void quickSort(int headIndex, int tailIndex, final boolean isAscending) {
if (tailIndex - headIndex < 0) return;
int[] data = super.getData();
int key = data[headIndex];
int i = headIndex, j = tailIndex;
boolean isTail = true;
while (i != j) {
if (isTail) {
boolean c1 = isAscending && data[j] < key;
boolean c2 = !isAscending && data[j] > key;
if (c1 || c2) {
swap(data, i, j);
i++;
isTail = false;
continue;
}
j--;
} else {
boolean c1 = isAscending && data[i] > key;
boolean c2 = !isAscending && data[i] < key;
if (c1 || c2) {
swap(data, i, j);
j--;
isTail = true;
continue;
}
i++;
}
}
this.quickSort(headIndex, i - 1, isAscending);
this.quickSort(i + 1, tailIndex, isAscending);
}
}
