大理网站设计百度网盘网页版
基本思想
快速排序Quicksort）是对冒泡排序的一种改进。 基本思想是分治的思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序算法的平均时间复杂度是 O(nlogn)
快速排序法示意图：
代码实现
思路：**左右双指针移动 **
例（从小到大排序下面的数组元素）
-
选择最右侧数值作为基准（pivot），并将该位置作为坑；左指针（left）指向最左侧数字，右指针（right）指向最右侧数字
-
左指针向右移动。当左指针与右指针相遇（指向同一数字）时停下来，或者左指针指向数字大于pivot时也停下来，将该值填入坑中，将坑改为此位置
-
右指针向左移动。左指针与右指针相遇时停下来，或者右指针指向数字小于pivot时也停下来，将该值填入坑中，将坑改为此位置
-
循环2、3步直至两指针相遇。如果此时左指针与右指针相遇，此时该位置为坑，将pivot填入该坑中，这样pivot的位置就找好了。
-
递归（以上步骤）基准左、右两旁的数列，直至数列不可再分则完成排序
备注：
- 递归的出口必须仔细考虑清楚，否则就会陷入无穷循环从而使栈溢出；
- 这里如果pivot 选在左侧，就要先从右侧开始遍历，反之则先从左侧开始
- 记得考虑到数值相同的情况
代码落地
public static void quickSort(int[] arr,int startIndex, int endIndex) {if (startIndex >= endIndex) {return;}int left = startIndex, right = endIndex, pivot = arr[endIndex];while (left < right) {while (left < right && arr[left] <= pivot) {left++;}arr[right] = arr[left];while (left < right && arr[right] >= pivot) {right--;}arr[left] = arr[right];}arr[left] = pivot;quickSort(arr, startIndex, left - 1);quickSort(arr, left + 1, endIndex);
}
参考文章
快速排序法（详解）
五分钟学会一个高难度算法：快速排序
排序算法之快速排序(Java实现)