如何实现快速排序
本篇内容介绍了"如何实现快速排序"的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！
概述
快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。
算法步骤
从数列中挑出一个元素，称为 "基准"（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; }"如何实现快速排序"的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注网站，小编将为大家输出更多高质量的实用文章！
