介绍

排序是非常基础的算法问题，快速排序又是排序中的经典，这里用简单易懂的方式阐述一下快速排序的思想与具体实现。

核心思想

快速排序的核心在于选择一个中轴点，将数组中所有的值与此中轴点比较，比中轴点小的移动到左侧，比中轴点大的移动到右侧，再将数组的左右侧进行递归，最后就可以得到排序完成的数组，这是一种典型的分治思想。
递归函数中的核心步骤：

1. 选择中轴点；
2. 遍历数组中的值与中轴点比较；
3. 交换位置。

实现

先根据上面的思想，写出一个基本的函数结构：

/* * @param nums 需要排序的数组* @param left 左边界* @param right 右边界*/public static void quickSort(int[] nums, int left, int right) {//当前需要排序的范围小于1，结束递归    if (left < right) { //分片排序，并返回中轴点最终位置 int partition = partition(nums, left, right); quickSort(nums, left, partition-1); quickSort(nums, partition+1, right);    }}

partition()函数中主要做的事就是选取左侧点为中轴点，然后遍历left+1到right范围内的所有值，并与中轴点进行比较，根据比较结果进行交换。

选择一个中轴点，此处本文选择最左侧为中轴点(该点可以为任一点，不影响排序，为方便取值，选择最左侧)。
定义一个中轴点坐标标记index，当遍历值大于中轴点时，index不动；当遍历值大于中轴点时，index进位，这样可以保证index左侧的值永远小于中轴点，遍历完成后，中轴点与index-1位置的值交换位置，此时可保证中轴点左侧均小于等于中轴点，右侧同理。

图解举例：

当前，有一个数组[10,7,23,12,7,1,3]，p为中轴点，i为遍历点， index为中轴点坐标标记点

p  i10 7 23 12 7 1 3   index   7  10   //此时继续遍历pi10 7 23 12 7 1 3     index12 > 10  //此时继续遍历p   i10 7 23 12 7 1 3     index7 < 10   //此时i和index处值进行交换,index进位p     i10 7 7 12 23 1 3index1 < 10   //此时i和index处值进行交换,index进位p    i10 7 7 1 23 12 3  index3 < 10  //此时i和index处值进行交换,index进位p      i10 7 7 1 3 12 23    indexswap  //中轴点与index-1位置交换 p     i3 7 7 1 10 12 23    index

此时可以看出中轴点的左侧均小于等于中轴点，右侧均大于等于中轴点，根据这个思路，将左右两侧分别再次进行此方法排序，最终可得到排序完成的数组。

综上所述，partition()函数应这样设计：

/* * @param nums 需要排序的数组* @param left 左边界* @param right 右边界*/public static int partition(int[] nums, int left, int right) {    int pivot = left;    int index = pivot + 1;    for (int i = index; i <= right; i++) { if (nums[i] < nums[pivot]) {     swap(nums, i, index);     index++; }    }    swap(nums, pivot, index-1);    return index-1;}

代码

public class QuickSort {    public static void main(String[] args) { int[] nums = {10,7,23,12,7,1,3}; quickSort(nums, 0, nums.length-1); System.out.println(Arrays.toString(nums)); // [1, 3, 7, 7, 10, 12, 23]    }    public static void quickSort(int[] nums, int left, int right) { if (left < right) {     int partition = partition(nums, left, right);     quickSort(nums, left, partition-1);     quickSort(nums, partition+1, right); }    }    public static int partition(int[] nums, int left, int right) { int pivot = left; int index = pivot + 1; for (int i = index; i <= right; i++) {     if (nums[i] < nums[pivot]) {  swap(nums, i, index);  index++;     } } swap(nums, pivot, index-1); return index-1;    }    public static void swap(int[] nums, int n1, int n2) { int temp; temp = nums[n1]; nums[n1] = nums[n2]; nums[n2] = temp;    }}

总结

一个人的知识积累，往往从最基础开始，打好一个夯实的地基，日后才能盖起万丈摩天大楼，本文若有不对的地方，请在评论中指出，如果有更好的实现方法也欢迎分享，知识无界。

科普知事网