如何实现快速排序
本篇内容介绍了“如何实现快速排序”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！
创新互联建站是一家朝气蓬勃的网站建设公司。公司专注于为企业提供信息化建设解决方案。从事网站开发，网站制作，网站设计，网站模板，微信公众号开发，软件开发，小程序设计，十余年建站对混凝土搅拌罐车等多个方面，拥有丰富的网站维护经验。
概述
快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。
算法步骤
从数列中挑出一个元素，称为 "基准"（pivot）;
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
先来看一下分区操作：
原始数组：
我们把数组的第一个元素 ‘5’ 作为"基准"，然后在基准后面第一个元素的位置定义两个指针 “i”、“j” 指针“i”从左至右移动，每移动一下，需要比较“i”位置元素与基准值的大小，如果小于基准值，则执行一次“swap”，即交换“i”，“j”这两个位置的元素的值；另外，每执行一次“swap”，“j”的值加一。
ok，“j”暂时不动，“i”往后移动，当“i”移动到“1”的位置时， 
此时，“1”小于基准值“5”，需要执行一次“swap”,同时"j"加一
以此类推，当“i”移动到最右侧时，结果如下：
此时我们只需要，交换“基准值”和“j”的前一个位置的值（也就是交换5 和 2），就能达到”分区“的效果，
我看可以看到所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面；
仔细观察会发现，指针“i”用来扫描数组元素，指针“j”的左侧始终时比基准小的元素，这也是为什么基准值要与“j”前一个元素交换。
至此，一轮“分区”操作完成。
我们来看整个过程：
代码：
public static int[] sort(int[] arr) {
return quickSort(arr, 0, arr.length - 1);
}
private static int[] quickSort(int[] arr, int left, int right) {
if (left < right) {
//分区
int partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
return arr;
}
private static int partition(int[] arr, int left, int right) {
int pivot = left;
//指针 j
int j = pivot + 1;
for (int i = j; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, j);
j++;
}
}
swap(arr, pivot, j - 1);
return j - 1;
}
private static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}“如何实现快速排序”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注创新互联网站，小编将为大家输出更多高质量的实用文章！
文章名称：如何实现快速排序
文章分享：http://6mz.cn/article/jhsoed.html