快速排序在每一轮挑选一个基准元素, 并让其他比它并让其他比它大的元素移动到数列一边, 比它小的元素移动到数列的另一边, 从而把数列分解成两个部分. 分而治之, 使用分治法. 在分治法的思想下, 原来数列的每一轮都被拆分成两个部分, 每个部分又分别被拆分成两部分, 知道其中一个部分只有一个元素不可再分.
一, 基准元素的选择
快速排序第一个步骤是基准元素的选择, 在分治的过程中, 以基准元素为中心, 把其他元素移动到基准元素的两边.
极端情况: 如果数列的第 1 个元素是最小值或者最大值, 那么时间复杂度变成了 O(n2)
解决方法: 随机选择一个元素作为基准值.
二, 元素的交换过程
具体实现有两种方法:
双边循环法, 单边循环法
1. 双边循环法:
实现原理: 左右两个指针同时往中间扫描, 如果右边的元素小于左边的元素, 则两个元素交换, 直到两个指针相遇.
第一步: 选定基准元素 pivot, 设置左指针 left 和右指针 right
第二步: 第 1 次循环, 从 right 指针开始, 让指针指向的元素与基准元素作比较.
第三步: 如果大于或等于 pivot 则指针左移, 否则停止移动转到 left 指针
第四步: 如果 left 指针指向的元素小于或等于 pivot, 则指针向左移动
第五步: 如果大于, 则转到 right 指针
第六步: 直到 left 指针和 right 指针相遇
代码实现:
- package algorithm;
- import java.util.Arrays;
- /*
- * 在每一轮挑选一个基准元素, 并让其他比它大的元素移动到数列一边, 比它小的元素移动到另一边, 分成两个部分
- * 对两个部分递归进行这个操作
- */
- public class Test {
- public static void quickSort(int[] arr,int startIndex,int endIndex) {
- // 递归的退出条件: 递归最后一层左边的元素小于或等于右边元素的位置
- if(startIndex>= endIndex) {
- return;
- }
- // 得到基准元素的位置
- // 取第一个位置的元素作为基准元素
- int pivot = arr[startIndex];
- int left = startIndex;
- int right = endIndex;
- /*
- * 第一步: 选定基准元素 pivot, 设置左指针 left 和右指针 right
- * 第二步: 第 1 次循环, 从 right 指针开始, 让指针指向的元素与基准元素作比较.
- * 第三步: 如果大于或等于 pivot 则指针左移, 否则停止移动转到 left 指针
- * 第四步: 如果 left 指针指向的元素小于或等于 pivot, 则指针向左移动
- * 第五步: 如果大于, 则转到 right 指针
- * 第六步: 直到 left 指针和 right 指针相遇
- */
- while(left != right) {
- while(left<right && arr[right]> pivot) {
- right--;
- }
- while(left<right && arr[left] <= pivot ) {
- left++;
- }
- if(left<right) {
- int p = arr[left];
- arr[left] = arr[right];
- arr[right] = p;
- }
- }
- //pivot 和指针重合点交换
- arr[startIndex] = arr[left];
- arr[left] = pivot;
- int pivotIndex = left;
- // 根据基准元素, 递归调用
- quickSort(arr,startIndex,pivotIndex-1);
- quickSort(arr,pivotIndex+1,endIndex);
- }
- /*
- * 分治 (双边循环)
- * arr 是代交换的数组
- * startIndex 是起始下标
- * endIndex 是结束下标
- */
- public static void main(String[] args) {
- int arr[] = {4,4,6,5,3,2,8,1};
- quickSort(arr,0,arr.length-1);
- System.out.println(Arrays.toString(arr));
- }
- }
2. 单边循环法:
与双边循环不同的是, 单边循环只有一个 mark 指针. 从第二个元素开始逐个遍历每个元素, 如果这个元素小于基准值, 则往后继续遍历, 如果这个元素大于基准值, 先把 mark 指针后移一位, 将最新遍历的元素与 mark 指针所在位置的元素交换位置.
第一步: 选定基准元素 pivot, 设置一个 mark 指针指向数列的起始位置. mark 指针代表小于基准元素的区域边界.
第二步: 从基准元素的下一个位置开始遍历数组
第三步: 如果遍历的元素大于基准元素, 就继续往后遍历, 否则, 需要做两件事, 一把 mark 右移一位, 二把新遍历到的元素和 mark 指针所在位置的元素交换位置.(mark 指针右移使得小于 pivot 的区域边界增大了 1, 交换位置是因为新遍历的元素小于 pivot)
第四步: 按照以上思路, 直到数列遍历完毕
- package algorithm;
- import java.util.Arrays;
- public class SingleQuickSort {
- public static void quickSort(int[] arr,int startIndex,int endIndex) {
- // 递归的退出条件: 递归最后一层左边的元素小于或等于右边元素的位置
- if(startIndex>= endIndex) {
- return;
- }
- // 得到基准元素的位置
- int pivotIndex = partition(arr,startIndex,endIndex);
- // 根据基准元素, 递归调用
- quickSort(arr,startIndex,pivotIndex-1);
- quickSort(arr,pivotIndex+1,endIndex);
- }
- /*
- * 分治 (单边循环)
- * arr 是代交换的数组
- * startIndex 是起始下标
- * endIndex 是结束下标
- * mark 是标志指针
- * 算法步骤:
- * 第一步: 将第数列第一个值定位基准值, 将 mark 指针指向基准值
- * 第二步: 循环遍历数列, 如果遍历到的值大于基准值, 则继续遍历. 否则, 将标志指针右移一位, 交换当前遍历到的元素的值和 mark 指针指向的值
- * 第三步: mark 指针右移使得小于 pivot 的区域边界增大了 1, 交换位置是因为新遍历的元素小于 pivot, 直到数列遍历完毕
- *
- */
- private static int partition(int[] arr, int startIndex, int endIndex) {
- // 取第一个位置的元素作为基准元素
- int pivot = arr[startIndex];
- int mark = startIndex;
- for(int i = startIndex+1; i <= endIndex; i++) {
- if(arr[i] < pivot) {
- mark++;
- int p = arr[mark];
- arr[mark] = arr[i];
- arr[i] = p;
- }
- }
- arr[startIndex] = arr[mark];
- arr[mark] = pivot;
- return mark;
- }
- public static void main(String[] args) {
- int arr[] = {4,4,6,5,3,2,8,1};
- quickSort(arr,0,arr.length-1);
- System.out.println(Arrays.toString(arr));
- }
- }
三, 非递归实现
来源: http://www.bubuko.com/infodetail-3070677.html