快速排序是最经典的排序之一，已经有各种各样经过论证的实现方式。
引用百度百科里的介绍：
快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
这里我也简单的记录一下学习到的一些实现方式。
一、单向扫描
单向扫描，顾名思义，就是从一个方向进行扫描以进行划分，可以从左，也可以从右。首先需要选择一个参考值，最简单的就是以第一个元素做为参考值，一趟扫描的结果就是所有大于参考值的元素位于参考值的右边，所有小于参考值的元素位为参考值的左边。
快速排序是一个不稳定排序，就是相同元素的值经过排序后的位置可能有交换，所以可以定义一个规则，例如所有相同的值都位于右边，或者是都位于左边。
代码实现如下：
/**
*
* @param array: 待排序数组
* @param firstIndex：待排序的起始下标（包括）
* @param lastIndex ：待排序的结束下标（不包括)
*/
public static void simplestQuickSort(int[] array, int firstIndex, int lastIndex) {
//如果元素个数小于或等于1个，就不用排了
if (lastIndex - firstIndex <= 1) {
return;
}
//选择第一个元素作为参考值，并从第二个元素开始向后扫描
int flagIndex = firstIndex;
for (int currentIndex = firstIndex + 1; currentIndex < lastIndex; currentIndex++) {
/*
* 如果当前值小于参考值，则进行交换
*/
if (array[currentIndex] < array[flagIndex]) {
if (flagIndex == currentIndex - 1) { //当当前值和参考值紧挨时，则直接交换
swap(array, flagIndex, currentIndex);
} else {
/*
* 当当前值和参考值非紧挨时，则表示他们之间所有的数
* 都是大于等于参考值的数，则在当前值，参考值和参考值
* 紧挨的下一个值三者间进行互换。
*/
swap(array, flagIndex, currentIndex, flagIndex + 1);
}
/*
* 每发现一个小于参考值的值后，都将参考值的下标后移
*/
flagIndex++;
}
}
simplestQuickSort(array, firstIndex, flagIndex);
simplestQuickSort(array, flagIndex + 1, lastIndex);
}
private static void swap(int[] array, int... indices) {
int tmp = array[indices[0]];
int last = indices.length - 1;
for (int i = 0; i < last; i++) {
array[indices[i]] = array[indices[i + 1]];
}
array[indices[last]] = tmp;
}
二、双向扫描
一般情况下，单向扫描的速度已经相当快了，但是在某些极端的情况下，会出现性能的倒退，例如当所有元素的值相同的时候，则排序效率降为O(n2)，因为每次划分都只能去掉最头或最尾的一个元素。
这个时候就可以考虑双向扫描了，就是从最前和最后两个方向扫描，算法大致描述如下：
- 用一个主循环和两个内循环来扫描
- 其中第一个内循环从右向左扫描，遇到不大于参考值的元素时则停止扫描
- 第二个内循环从左向右扫描，遇到不小于参考值的时候则停止扫描
- 然后交换两个元素的位置
- 重复1-4
代码实现如下：
/**
*
* @param array: 待排序数组
* @param firstIndex：待排序的起始下标（包括）
* @param lastIndex ：待排序的结束下标（不包括)
*/
public static void bidirQuickSort(int[] array, int firstIndex, int lastIndex) {
//如果元素个数小于或等于1个，就不用排了
if (lastIndex - firstIndex <= 1) {
return;
}
int flagIndex = firstIndex;
int i = firstIndex;
int j = lastIndex;
while (i < j) {
/*
* 从后向前，如果值比参考值大，则一直向前
* 因为j的初值为最后一个值的下一个，所以
* 可以先执行减一再比较，也保证了每次j的
* 值至少向前移动了一位。
*/
do {
j--;
} while (array[j] > array[flagIndex]);
/*
* 从前向后，如果值比参考值小，则一直向后
* 因为i的初值为第一个值，而第一个值设成了参考值的值，
* 所以可以先执行加一再比较，也保证了每次i的
* 值至少向后移动了一位。
*/
do {
i++;
} while (array[i] < array[flagIndex] && i <= j);
/*
* 然后交换i,j位置上的值，进行下一次扫描
*/
if (i <= j) {
swap(array, i, j);
}
}
/*
* 当停止的时候j处于所有比参考值大的位置之有
* （也即j上的值应该比参考值不大）
* 所以可以交换参考值和j上的值，以完成一趟扫描
*/
swap(array, flagIndex, j);
bidirQuickSort(array, firstIndex, j);
bidirQuickSort(array, j + 1, lastIndex);
}
private static void swap(int[] array, int... indices) {
int tmp = array[indices[0]];
int last = indices.length - 1;
for (int i = 0; i < last; i++) {
array[indices[i]] = array[indices[i + 1]];
}
array[indices[last]] = tmp;
}
可以看出当所有值相同的时候，双向扫描比单向扫描效率要高很多。
三、随机参考值
上面介绍的单向和双向扫描的参考值我们都选择了第一个元素做为参考值，一般情况下这个问题不大。然而在数组本身已经是排序好的情况下，这个参考值就会有问题，回退到算法1在元素都相等的情况了：先是第一个元素被处理，然后是第二个，然后是第三。。。
避免这种情况的一个方法就是使用随机参考值：随机选择待排序片段中的一个值作为参考值，然后把它和第一个元素进行交换，剩下的就和上面已经完成的是一要的了。所以重要的是怎么选择一个随机数。可以用一些随机算法，也可以通过某种计算。假设这里每次都选择中间位置的值作为参考值，则修改双向算法：
/**
*
* @param array: 待排序数组
* @param firstIndex：待排序的起始下标（包括）
* @param lastIndex ：待排序的结束下标（不包括)
*/
public static void bidirQuickSort(int[] array, int firstIndex, int lastIndex) {
//如果元素个数小于或等于1个，就不用排了
if (lastIndex - firstIndex <= 1) {
return;
}
/*
* 选择中间位置值作为随机值
* 并与第一个位置的值交换
*/
swap(array, firstIndex, (firstIndex+lastIndex)/2);
int flagIndex = firstIndex;
int i = firstIndex;
int j = lastIndex;
while (i < j) {
/*
* 从后向前，如果值比参考值大，则一直向前
* 因为j的初值为最后一个值的下一个，所以
* 可以先执行减一再比较，也保证了每次j的
* 值至少向前移动了一位。
*/
do {
j--;
} while (array[j] > array[flagIndex]);
/*
* 从前向后，如果值比参考值小，则一直向后
* 因为i的初值为第一个值，而第一个值设成了参考值的值，
* 所以可以先执行加一再比较，也保证了每次i的
* 值至少向后移动了一位。
*/
do {
i++;
} while (array[i] < array[flagIndex] && i <= j);
/*
* 然后交换i,j位置上的值，进行下一次扫描
*/
if (i <= j) {
swap(array, i, j);
}
}
/*
* 当停止的时候j处于所有比参考值大的位置之有
* （也即j上的值应该比参考值不大）
* 所以可以交换参考值和j上的值，以完成一趟扫描
*/
swap(array, flagIndex, j);
bidirQuickSort(array, firstIndex, j);
bidirQuickSort(array, j + 1, lastIndex);
}
private static void swap(int[] array, int... indices) {
int tmp = array[indices[0]];
int last = indices.length - 1;
for (int i = 0; i < last; i++) {
array[indices[i]] = array[indices[i + 1]];
}
array[indices[last]] = tmp;
}
四、混合排序
上面的快速排序将花大量的时间在很小片段的排序上（当划分越来越小时），并且那时数组已经是分成了一个个有序块了，是一个基本有序数组。对于小规模的，几乎有序的数组，用插入排序或者冒泡排序会效果更好。因此可以混合快速和插入或冒泡排序来排序数组：当待排序数组较长时使用快速排序，当待排序数组较小时，使用插入或冒泡排序。
代码如下：
/**
*
* @param array: 待排序数组
* @param firstIndex：待排序的起始下标（包括）
* @param lastIndex ：待排序的结束下标（不包括)
*/
public static void bidirQuickSort(int[] array, int firstIndex, int lastIndex) {
//如果元素个数小于6个，则用冒泡排序或插入排序
if (lastIndex - firstIndex < 6) {
//bubbleSort(array, firstIndex, lastIndex);
insertSort(array, firstIndex, lastIndex);
return;
}
/*
* 选择中间位置值作为随机值
* 并与第一个位置的值交换
*/
swap(array, firstIndex, (firstIndex + lastIndex) / 2);
int flagIndex = firstIndex;
int i = firstIndex;
int j = lastIndex;
while (i < j) {
/*
* 从后向前，如果值比参考值大，则一直向前
* 因为j的初值为最后一个值的下一个，所以
* 可以先执行减一再比较，也保证了每次j的
* 值至少向前移动了一位。
*/
do {
j--;
} while (array[j] > array[flagIndex]);
/*
* 从前向后，如果值比参考值小，则一直向后
* 因为i的初值为第一个值，而第一个值设成了参考值的值，
* 所以可以先执行加一再比较，也保证了每次i的
* 值至少向后移动了一位。
*/
do {
i++;
} while (array[i] < array[flagIndex] && i <= j);
/*
* 然后交换i,j位置上的值，进行下一次扫描
*/
if (i <= j) {
swap(array, i, j);
}
}
/*
* 当停止的时候j处于所有比参考值大的位置之有
* （也即j上的值应该比参考值不大）
* 所以可以交换参考值和j上的值，以完成一趟扫描
*/
swap(array, flagIndex, j);
bidirQuickSort(array, firstIndex, j);
bidirQuickSort(array, j + 1, lastIndex);
}
private static void insertSort(int[] array, int firstIndex, int lastIndex) {
for (int i = firstIndex + 1; i < lastIndex; i++) {
if (array[i - 1] > array[i]) {
int tmp = array[i];
int j = i;
while (j > 0 && array[j - 1] > tmp) {
array[j] = array[j - 1];
j--;
}
array[j] = tmp;
}
}
}
private static void bubbleSort(int[] array, int firstIndex, int lastIndex) {
for (int i = lastIndex - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (array[j] > array[j + 1]) {
swap(array, j, j + 1);
}
}
}
}
private static void swap(int[] array, int... indices) {
int tmp = array[indices[0]];
int last = indices.length - 1;
for (int i = 0; i < last; i++) {
array[indices[i]] = array[indices[i + 1]];
}
array[indices[last]] = tmp;
}
五、并发排序
快速排序也是一个极好的使用并发排序的例子，如方法四稍加修改就可以变成并发排序。可以选择线程池，也可以使用Java 7里介绍的分支/合并框架，以加速排序的进程。
相关推荐
快速排序的几种优化方法，对各种优化进行了代码实现，包括使用随机基准，中位数基准、聚集基准等方法。快速排序的几种优化方法，对各种优化进行了代码实现，包括使用随机基准，中位数基准、聚集基准等方法。
常见的几种排序方式，包括选择排序，冒泡排序，快速排序，希尔排序，堆排序，插入排序。vs2008实现，对话框方式，主要实现字符串的由小到大排序。点击“几种排序方法.vcproj“运行。字符集使用多字节集，不能用...
冒泡排序、快速排序、直接插入排序、简单选择排序 等经典算法的思想介绍，大白话简单易懂。并用java实现。代码拿去即可用，不需做任何修改! 部分内容： /** * 快排：O(n*logn)；如果是从小到大排序； * 思想：选...
python实现快速排序的几种方法.docx
用Java语言实现的各种排序，包括插入排序、冒泡排序、选择排序、Shell排序、快速排序、归并排序、堆排序、SortUtil等。 插入排序： package org.rut.util.algorithm.support; import org.rut.util.algorithm....
一些常用排序算法的C语言实现，包括直接选择排序，希尔排序，直接插入排序，快速排序，归并排序，冒泡排序，堆排序
只需两个时钟即可输出12个数据的排序结果，内容简单易懂
快排实现和优化，无需使用MFC，只在命令行中选择实现，提供选项执行随机数生成和规模测试，可以针对大学数据结构和算法课程使用，包括了相应的文档信息
几种排序算法的代码实现。c语言版的。排序算法 希尔排序 快速排序 堆排序 归并排序 计数排序
常见的几种排序算法的实现：选择排序、插入排序、冒泡排序、希尔排序、快速排序、归并排序。包括实现与局测试。
选择排序 冒泡排序 插入排序 合并排序 快速排序算法原理及代码实现 不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 当面临巨大数据量的排序的时候，还是优先选择合并排序算法和快速排序算法。...
几种内部排序算法的Java实现 各种内部排序方法的比较 直接插入排序 折半插入排序 希尔排序 起泡排序 快速排序 简单选择排序 树形选择排序 堆排序 归并排序 基数排序
用C#实现的几种典型排序算法，包括二叉树排序、快速排序、希尔排序、插入排序、冒泡排序、选择排序等，代码简单易懂，适合初学者，供学习教育用
数据结构报告c++，简单选择排序，冒牌排序，插入排序，快速排序，两路合并排序，堆排序，几种排序方法的比较，有详细的源代码和实验报告
php实现的几种排序方法，包括插入排序，选择排序，冒泡排序、快速排序
包括其中排序方法的实现,大数据时各种排序算法的速度比较!
Shell排序 快速排序 归并排序 插入排序 选择排序 冒泡排序
这里提供了冒泡排序，插入排序，递归排序，基数排序，快速排序，选择排序，希尔排序这几种排序算法。里面有大量的注释，可以理解实现思路
c实现，几种排序总结，面试笔试很有用的，用的是线性表的顺序存储结构，\(^o^)/~