快速排序是最经典的排序之一，已经有各种各样经过论证的实现方式。
引用百度百科里的介绍：
快速排序（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里介绍的分支/合并框架，以加速排序的进程。
相关推荐
在实际编写C语言实现链表快速排序的代码时，需要注意以下几点： - 避免空链表或只有一个节点的链表，这需要特别处理。 - 在处理链表时，避免丢失指针，确保正确地链接节点。 - 快速排序在最坏情况下的时间复杂度是O...
快速排序是一种高效的排序算法，由C.A.R. Hoare在1960年提出。它的基本思想是通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别...
常见的几种排序方式，包括选择排序，冒泡排序，快速排序，希尔排序，堆排序，插入排序。vs2008实现，对话框方式，主要实现字符串的由小到大排序。点击“几种排序方法.vcproj“运行。字符集使用多字节集，不能用...
快速排序是一种高效的排序算法，由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法（Divide and Conquer），通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的...
快速排序是一种高效的排序算法...以上就是快速排序的几种优化方法，它们在不同的场景下能提升快速排序的效率和稳定性。通过这些优化，快速排序在实际应用中展现出强大的性能，成为许多编程语言内置排序函数的首选算法。
快速排序的步骤可以分为以下几步：首先从序列中选取一个基准元素；然后进行分区操作，将序列分为两部分，一部分包含所有小于基准的元素，另一部分包含所有大于基准的元素；最后递归地对这两部分进行快速排序。分区...
在实现快速排序时，有几种常见的策略和优化方法： 1. **三数取中法**：选取基准元素时，不是简单地取首、尾或中间元素，而是从三个端点（首、尾、中间）选取中值作为基准，这样可以减少最坏情况的发生概率。 2. **...
快速排序是一种高效的排序算法，由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法（Divide and Conquer），通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的...
快速排序的核心算法可以分为以下几步： a. 选取基准值：通常选择数组的第一个元素。 b. 分区操作：遍历数组，将小于基准值的元素移到数组前面，大于基准值的移到后面。此过程完成后，基准值位于正确的位置，数组被...
冒泡排序、快速排序、直接插入排序、简单选择排序 等经典算法的思想介绍，大白话简单易懂。并用java实现。代码拿去即可用，不需做任何修改! 部分内容： /** * 快排：O(n*logn)；如果是从小到大排序； * 思想：选...
### Python实现快速排序的几种方法 #### 快速排序算法简介 快速排序是一种非常高效的排序算法，采用分治策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。该算法的基本思想是：选择一个基准...
在C语言中实现快速排序，我们需要以下几个关键步骤： 1. **选择基准**: 通常可以选择待排序数组的第一个元素或者最后一个元素作为基准，但更优的方式是随机选取，以减少最坏情况的发生概率。 2. **分区操作**: 将...
快速排序的实现主要包括以下几个步骤： 1. **选择基准元素（Pivot）**：通常选择数组的第一个元素或者最后一个元素作为基准，也可以用随机选择的方式。 2. **分区操作（Partition）**：将数组中的元素根据基准元素...
在Java中，快速排序通常采用分治策略实现。它选取一个基准元素，将数组分为两部分，一部分所有元素都比基准小，另一部分所有元素都比基准大，然后递归地对这两部分进行快速排序。 ```java package org.rut.util....
一些常用排序算法的C语言实现，包括直接选择排序，希尔排序，直接插入排序，快速排序，归并排序，冒泡排序，堆排序
在《算法导论》中，快速排序的实现通常会涉及到以下几个关键步骤： 1. **选择基准**：在C语言实现中，描述中提到的基准选择是随机的。这种方法可以避免最坏情况的发生，即每次划分得到的两个子序列都只有一个元素，...
快速排序的基本思想可以概括为以下几个步骤： 1. **选择基准值**：从序列中挑选一个元素作为基准值。 2. **分区操作**：重新排列序列，所有小于基准值的元素都排在基准前面，所有大于基准值的元素都排在基准后面。...
快速排序是一种高效的排序算法，其基本思想是通过选取一个"枢轴"元素，将数组划分为两部分，使得一部分的所有元素都小于枢轴，另一部分的所有元素都大于枢轴，然后对这两部分再进行同样的排序操作，直至整个数组有序...