共计 2668 个字符，预计需要花费 7 分钟才能阅读完成。
本文首发自「慕课网」，想理解更多 IT 干货内容，程序员圈内热闻，欢送关注！
作者 | 慕课网精英讲师 JdreamZhang
疾速排序（Quick Sort），是计算机科学与技术畛域中十分经典的一种排序算法，利用分治思维进行排序。疾速排序因为其工夫复杂度优于大部分的排序算法，因此命名为疾速排序。疾速排序实现的核心思想就是在待排序序列中抉择一个基准值，而后将小于基准值的数字放在基准值右边，大于基准值的数字放在基准值左边，而后左右两边递归排序，整个排序过程中最要害局部就是寻找基准值在待排序序列中的索引地位。1. 疾速排序过程明天咱们来看一下疾速排序的实现步骤具体是什么样的吧。同样地，和之前介绍归并排序时一样，这里咱们假如待排序的序列为 [9,2,11,7,12,5]，咱们依照从小到大的序列进行排序。1.1 算法形容疾速排序也是利用分治法解决问题，次要分为以下三步：步骤 1：从待排序序列中抉择一个元素，称之为基准（pivot)，在这里咱们抉择待排序序列中第一个元素作为基准。步骤 2：对整个待排序序列进行从新排序，小于基准的元素放在基准后面，大于基准的元素放在基准前面，基准放在序列两头，这个步骤个别称之为分区操作（partition)。Tips: 步骤 2 的执行其实就是给基准元素找到了适合的排序地位。分区操作的伪代码如下，最重要的就是双指针的利用，将待排序序列基于基准进行分区：// 对数组 A 进行一次分区操作
int pivot = A[0]
low = 0
high = A.length-1
// 进行分区操作，找到基准的地位
while (low < high){
while(low < high && A[high] >= pivot){high = high - 1}
A[low] = A[high]
while (low < high && A[low] <= pivot){low = low + 1}
A[high] = A[low]}
// 最初赋值基准
A[low] = pivot
代码块 1234567891011121314151617 步骤 3：递归的将小于基准的子序列和大于基准的子序列进行排序。其实，下面的排序步骤就是分治法的典型利用，抉择基准分拆序列造成子序列，在子序列中从新排序，实现排序之后进行合并，只是因为在这里实现子序列的排序后待排序序列曾经实现排序，所以无需进行合并的工作。这里，最须要留神的就是步骤 2 中的分区操作，这外面会用到一种最为经典的双指针操作，前后两个指针别离记录须要替换的元素地位，前面的代码示例中会具体阐明。接下来，让咱们用下面的待排序数字队列 [9,2,11,7,12,5] 进行整个算法步骤的排序演示工作。1.2 算法演示依照排序步骤，首先咱们从待排序序列中抉择一个基准 pivot，这里默认抉择待排序序列中的第一个元素，如下：[9,2,11,7,12,5] –> 9 // 抉择第一个元素 9 作为基准 pivot
代码块 1 接着，咱们用下图的示例来阐明步骤 2 中的分区操作，这里用到了双指针 low 和 high。具体示例如下图：
依照上图的示例，能够很分明地晓得，其实疾速排序的实质就是把比基准大的元素都放在基准数的左边，把比基准小的元素放在基准数的右边，这样就找到了基准数据在数组中的正确地位。当前采纳递归的形式别离对前半部分和后半局部排序，以后半局部和后半局部均有序时该数组就天然有序了。如前文中说到的疾速排序其实最次要的就是双指针的利用，就是体现在分区操作时候的双指针进行分区。2.Java 代码实现在阐明疾速排序的整个过程之后，接下来，咱们看看如何用 Java 代码实现疾速排序算法。import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
// 初始化须要排序的数组
int array[] = {9, 2, 11, 7, 12, 5};
// 疾速排序
quickSort(array,0,array.length-1);
// 打印出排序好的序列
System.out.println(Arrays.toString(array));
}
// 疾速排序private static void quickSort(int[] array,int low, int high){
if(low < high){
// 找到分区的地位，右边左边别离进行疾速排序
int index = partition(array,low,high);
quickSort(array,0,index-1);
quickSort(array,index+1,high);
}}
// 疾速排序分区操作
private static int partition(int[] array, int low, int high){
// 抉择基准
int pivot = array[low];
// 当左指针小于右指针时，反复操作
while (low < high){while(low < high && array[high] >= pivot){high = high - 1;}
array[low] = array[high];
while (low < high && array[low] <= pivot){low = low + 1;}
array[high] = array[low];
}
// 最初赋值基准
array[low] = pivot;
// 返回基准所在位置，基准地位曾经排序好
return low;}
}
代码块 12345678910111213141516171819202122232425262728293031323334353637383940414243444546 运行后果如下：[2, 5, 7, 9, 11, 12]
代码块 1 代码中的第 8 行初始化一个须要排序的数组，前面依照从小到大的排序规定，实现了数组的排序。第 15 行到底 22 行是疾速排序的内部构造，利用分治思维递归求解。代码 25 行至 43 行是分区操作，实现基于基准数据的左右分区，并将基准数据搁置在排序好的地位，并且返回基准所在的地位，进行后续的分治操作。3. 小结本篇文章次要帮大家介绍了疾速排序算法，疾速排序是一种十分典型的排序算法，在 Java 程序中，JDK 中的 Arrays.sort() 办法的外部实现就是利用到疾速排序的思维实现数组的排序工作。
对于算法，其实每种排序算法的实现思路都不雷同，对应的算法的工夫复杂度和空间复杂度也都不一样，心愿大家能够在学习这些根底排序算法的根底上多思考，思考每种排序算法的具体实现，可能熟练掌握这些根底的排序算法。欢送关注「慕课网」，发现更多 IT 圈优质内容，分享干货常识，帮忙你成为更好的程序员！
