一、简介
快速排序是一种基于分治法的排序算法，其中
- 通过选择枢轴元素（从数组中选择的元素）将数组划分为子数组。
在划分数组时，枢轴元素的位置应使小于枢轴的元素保留在左侧，大于枢轴的元素位于枢轴的右侧。 - 左右子阵列也使用相同的方法进行划分。这个过程一直持续到每个子数组包含一个元素。
- 此时，元素已经排序。最后，将元素组合成一个排序数组。
二、快速排序算法步骤
（一）选择枢轴元素
快速排序有不同的变体，其中枢轴元素是从不同的位置选择的。在这里，我们将选择数组最右边的元素作为枢轴元素。
选择一个枢轴元素
（二）重新排列数组
现在数组的元素被重新排列，使小于枢轴的元素放在左边，大于枢轴的元素放在右边。
下面是我们如何重新排列数组：
- 指针固定在枢轴元素上。枢轴元素与从第一个索引开始的元素进行比较。
- 如果元素大于枢轴元素，则为该元素设置第二个指针
- 现在，将枢轴与其他元素进行比较。如果到达小于枢轴元素的元素，则将较小的元素与先前找到的较大元素交换
- 同样，重复该过程以将下一个更大的元素设置为第二个指针。并且，将其与另一个较小的元素交换。
- 该过程一直持续到到达倒数第二个元素。
- 最后，枢轴元素与第二个指针交换。
（三）划分子数组
再次分别为左侧和右侧子部分选择枢轴元素。并且，重复步骤 2 。子数组被划分，直到每个子阵列由单个元素形成。至此，数组已经排好序了。
（四）快速排序算法的可视化插图
您可以借助下图了解快速排序算法的工作原理。
使用递归对枢轴左侧的元素进行排序
使用递归对枢轴右侧的元素进行排序
Java实现快速排序
importjava.util.Arrays; classQuicksort { // method to find the partition positionstaticintpartition(intarray[], intlow, inthigh) { // choose the rightmost element as pivotintpivot=array[high]; // pointer for greater elementinti= (low-1); // traverse through all elements// compare each element with pivotfor (intj=low; j<high; j++) { if (array[j] <=pivot) { // if element smaller than pivot is found// swap it with the greatr element pointed by ii++; // swapping element at i with element at jinttemp=array[i]; array[i] =array[j]; array[j] =temp; } } // swapt the pivot element with the greater element specified by iinttemp=array[i+1]; array[i+1] =array[high]; array[high] =temp; // return the position from where partition is donereturn (i+1); } staticvoidquickSort(intarray[], intlow, inthigh) { if (low<high) { // find pivot element such that// elements smaller than pivot are on the left// elements greater than pivot are on the rightintpi=partition(array, low, high); // recursive call on the left of pivotquickSort(array, low, pi-1); // recursive call on the right of pivotquickSort(array, pi+1, high); } } } classMain { publicstaticvoidmain(Stringargs[]) { int[] data= { 8, 7, 2, 1, 0, 9, 6 }; System.out.println("Unsorted Array"); System.out.println(Arrays.toString(data)); intsize=data.length; // call quicksort() on array dataQuicksort.quickSort(data, 0, size-1); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); } }
