快速排序

发表于 分类于 ， 阅读次数： 本文字数： 3.8k 阅读时长 ≈ 3 分钟

快速排序

快速排序（Quick Sort）由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序也是分治法的经典实现，是不稳定的算法。

参考链接

算法描述

1、从数列中挑出一个元素，称为 “枢纽值”（pivot）。
2、重新排序数列，比枢纽值小的所有元素摆放在枢纽值前面，比枢纽值大的所有元素摆放在枢纽值后面（相同的数可以到任一边）。在这个分区退出之后，该枢纽值就处于数列的中间位置。
3、最后将两个排序好的子序列合并成一个最终的排序序列。

选取枢纽值

一般不选用第一个元素做枢纽值，因为如果输入有序序列那么快速排序将花费很多时间做无用功，这很尴尬。一种可取的做法是三数取中法，即把数列的起始、中间和末尾位置上的三个元素的中值作为枢纽值。
在这里插入图片描述
上图中枢纽值为6，把6放在arr.length-1的位置以便后续分割。
图片来源

分割策略

具体分割实现步骤如下所示：
在这里插入图片描述
在这里插入图片描述
图片来源

代码实现

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
package com.test;

import java.util.Arrays;

public class QuickSort {

public static void main(String[] args) {
    int[] arr = {1,2,5,3,4,0,9,8,15,20,7};
    quickSort(arr,0,arr.length-1);
    System.out.println("排序结果："+ Arrays.toString(arr));
}

/**
 * 快速排序具体实现
 * i和枢纽值交换注释if(i<right),改为while中添加i<pivot
 * @param arr 待排序数组
 * @param left 左指针
 * @param right 右指针
 */
public static void quickSort(int[] arr,int left,int right){
    if(left<right){
        //1、获取枢纽值，并将其放在当前待处理序列倒数第二位
        getPivot(arr,left,right);
        //2、定义枢纽值位置、左指针i、右指针j
        int i = left;
        int j = right-1;
        int pivot = right-1;
        //3、移动指针：确保左指针前的元素小于枢纽值；右指针后的元素大于枢纽值
        while(true){
            while(i<pivot&&arr[++i]<arr[pivot]){};
            while(j>0&&arr[--j]>arr[pivot]){};
            if(i<j)// i指向的元素比枢纽值大且j指向的元素比枢纽值小
                swapReferences(arr,i,j);
            else
                break;
        }
        //4、restore pivot：将i和枢纽值交换
        //if(i<right)
            swapReferences(arr,i,pivot);
        //5、分治法：左右部分递归
        quickSort(arr,left,i-1);
        quickSort(arr,i+1,right);
    }
}

/**
 * 获取枢纽值，并将其放在当前待处理序列倒数第二位
 * @param arr 待处理数组
 * @param left 左指针
 * @param right 右指针
 */
private static void getPivot(int[] arr,int left,int right){
    //1、排序：确保arr[left]<arr[center]<arr[right]
    int center = (left+right)/2;
    if(arr[left]>arr[center])
        swapReferences(arr,left,center);
    if(arr[left]>arr[right])
        swapReferences(arr,left,right);
    if(arr[center]>arr[right])
        swapReferences(arr,center,right);
    //2、把枢纽值放在倒数第二个位置
    swapReferences(arr,center,right-1);
}

/**
 * 交换数组元素值
 * @param arr 待交换数组
 * @param index0 下标
 * @param index1 下标
 */
private static void swapReferences(int[] arr,int index0,int index1){
    int tmp = arr[index0];
    arr[index0] = arr[index1];
    arr[index1] = tmp;
}
}

排序结果：[0, 1, 2, 3, 4, 5, 7, 8, 9, 15, 20]

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/**
* 快速排序具体实现
* i和枢纽值交换注释if(i<right),改为while中添加i<pivot
* @param arr 待排序数组
* @param left 左指针
* @param right 右指针
*/
function quickSort(arr,left,right){
   if(left<right){
       //1、获取枢纽值，并将其放在当前待处理序列倒数第二位
       getPivot(arr,left,right);
       //2、定义枢纽值位置、左指针i、右指针j
       var i = left;
       var j = right-1;
       var pivot = right-1;
       //3、移动指针：确保左指针前的元素小于枢纽值；右指针后的元素大于枢纽值
       while(true){
           while(i<pivot&&arr[++i]<arr[pivot]){};
           while(j>0&&arr[--j]>arr[pivot]){};
           if(i<j)// i指向的元素比枢纽值大且j指向的元素比枢纽值小
               swapReferences(arr,i,j);
           else
               break;
       }
       //4、restore pivot：将i和枢纽值交换
       //if(i<right)
           swapReferences(arr,i,pivot);
       //5、分治法：左右部分递归
       quickSort(arr,left,i-1);
       quickSort(arr,i+1,right);
   }
}

/**
* 获取枢纽值，并将其放在当前待处理序列倒数第二位
* @param arr 待处理数组
* @param left 左指针
* @param right 右指针
*/
function getPivot(arr,left,right){
   //1、排序：确保arr[left]<arr[center]<arr[right]
   var center = Math.floor((left+right)/2);//注意js的"/"非取余运算
   if(arr[left]>arr[center])
       swapReferences(arr,left,center);
   if(arr[left]>arr[right])
       swapReferences(arr,left,right);
   if(arr[center]>arr[right])
       swapReferences(arr,center,right);
   //2、把枢纽值放在倒数第二个位置
   swapReferences(arr,center,right-1);
}

/**
* 交换数组元素值
* @param arr 待交换数组
* @param index0 下标
* @param index1 下标
*/
function swapReferences(arr,index0,index1){
   var tmp = arr[index0];
   arr[index0] = arr[index1];
   arr[index1] = tmp;
}

var arr = [1,2,5,3,4,0,9,8,15,20,7];
quickSort(arr,0,arr.length-1);
console.log(arr);

(11) [0, 1, 2, 3, 4, 5, 7, 8, 9, 15, 20]