快速排序算法的学习

思路

快速排序是采用分治的思路

1. 从数组中选中一个元素a，遍历数组

2. 把比a大的元素交换a后面，比a小的元素交换到a前面

3. 交换结束后，可以把数组分成两部分，a前面的（<=a）和a后面的(>=a)

4. 分别将这两部分排好序后，数组也就有序了

5. 对两部分还是进行一样的操作，选中元素a，交换，分割。

6. 就是不停的交换后分割数组，一直到分割后的部分都只有一个元素，无法再交换，整个数组有序

实现

错误代码

使用递归的方式实现分割下面是关于我根据这个思路后写出来第一版（错误）的快速排序，其中有两个bug需要修复

    public static void quickSort(int[] arr,int left,int right){
        // 被分割到只剩下一个元素了
        if (left >= right) {
            return;
        }

        // 选了第一个元素
        int pivot = left;

        while (left < right){
            /*
            left>=right时退出循环
            说明此时的left == right == pivot
            pivot已经满足了将数组分成两部分的条件
             */
            while (arr[right] >= arr[pivot]){
                right--;
            }
            // 交换之后pivot要变，left和right只改变值，下标依旧遍历数组
            if(right > pivot){
                swap(arr,right,pivot);
                pivot = right;
            }

            while (arr[left] <= arr[pivot]){
                left++;
            }
            if (left < pivot) {
                swap(arr,left,pivot);
                pivot = left;
            }
        }
        // 使用递归的方式进行分割
        quickSort(arr,0,pivot-1);
        quickSort(arr,pivot+1,arr.length-1);
    }

View Code

在代码中这两行没有考虑到数组越界的问题

            while (arr[right] >= arr[pivot]){
                right--;
            }
            while (arr[left] <= arr[pivot]){
                left++;
            }

最后的递归代码没有确定边界，当被分割的两部分进行排序时会互相干扰

        quickSort(arr,0,pivot-1);
        quickSort(arr,pivot+1,arr.length-1);

不完全实现

将这两个bug修复后的代码，算是完成了算法的实现。

public static void quickSort(int[] arr,int left,int right){
        // 被分割到只剩下一个元素了
        if (left >= right) {
            return;
        }

        // 保存开始和结束下标
        int start = left , end = right;
        
        // 选了第一个元素
        int pivot = left;

        while (left < right){
            /*
            left>=j时退出循环
            说明此时的i == right == pivot
            pivot已经满足了将数组分成两部分的条件
             */
            // 交换之后pivot要变，i和j依旧遍历数组
            while (right > pivot && arr[right] >= arr[pivot]){
                // 在后面的元素并且比pivot小
                right--;
            }
            if(arr[right] < arr[pivot]){

                swap(arr,right,pivot);
                pivot = right;
            }

            while (left < pivot && arr[left] <= arr[pivot]){
                left++;
            }
            if (arr[left] > arr[pivot]) {
                swap(arr,left,pivot);
                pivot = left;
            }
        }
        // 使用递归的方式进行分割
        quickSort(arr,start,pivot-1);
        quickSort(arr,pivot+1,end);
    }

View Code

但是还有很多可以优化的地方。

在循环中有left和right两个分别和pivot交换的地方，可以进一步优化
- 可以将两次交换过程，简化成一个三方交换
- 再使用一个循环外的临时变量保存值，将交换变成单向赋值过程
pivot选的是数组的第一个元素，在极端情况下会导致时间复杂度高
- 如果数组原本是倒序的，要将数组变成正序的，快速排序的分割数组阶段完全不生效，总过程类似冒泡排序
- pivot可以取left和right中间的一个随机值

正经实现

首先是pivot获取从left到right之间的随机值的方法

    // 在区间中获取一个随机值
    public static int getRandom(int upperBound,int lowerBound){
        return new Random().nextInt(upperBound - lowerBound + 1) + lowerBound;
    }

然后是两次交换简化成一个三方交换的过程，思路如下：

原本先交换的是right和pivot，然后交换left和pivot，但是不改变left和right这两个下标值，而pivot需要改变
所以 pivot跟left交换时，其实用的是从right那里换来的值
相当于 arr[right] 变成 arr[pivot] , arr[left] 变成 arr[right] , arr[pivot] 变成 arr[left]

所以交换的代码变成这样

        while (left < right){

            while (right > pivot && arr[right] >= arr[pivot]){
                right--;
            }

            while (left < right && arr[left] <= arr[pivot]){
                left++;
            }
            if(pivot == left && pivot == right){
                continue;
            }
            /*
            将两次交换变成三方交换
            首先交换的是right和pivot，然后交换left和pivot，但是不改变left和right这两个下标值，而pivot需要改变
            所以交换过程是(如果没有交换，有left==right==pivot，也成立)
             也就是   arr[right]  <-->  arr[pivot]   再   arr[left]  <-> arr[pivot]
            相当于 arr[right] ->arr[pivot]  , arr[left] -> arr[right]  , arr[pivot] -> arr[left]
             */
           int tmp = arr[pivot];
           arr[pivot] = arr[right];
           arr[right] = arr[left];
           arr[left] = tmp;
           pivot = left;
        }

View Code

再通过保存一个变量value 将这个三方交换简化成单向赋值

然后完整的快速排序算法如下

 1     public static void quick_sort(int[] arr,int left,int right){
 2         if (left >= right) {
 3             return;
 4         }
 5 
 6         // 保存开始和结束下标
 7         int start = left , end = right;
 8 
 9         //使用一个在i和j之间的随机数字
10         int pivot = getRandom(right,left);
11         // 保存pivot下标对应的值
12         int value = arr[pivot];
13 
14         /*
15         使用left和right两个指针，
16         首先移动right指针，遇到小于pivot的就进行交换，
17         然后移到left指针，遇到大于pivot的就进行交换，
18         实现 大的元素放到它后面，小的元素放到它前面
19          */
20 
21         while (left < right){
22             /*
23             值使用value比较
24             下标使用pivot比较
25             所以不需要更新pivot下标在数组的值
26             只要在循环外面赋值即可
27              */
28             while (right > pivot && arr[right] >= value){
29                 // 在后面的元素并且比pivot大
30                 right--;
31             }
32             while (left < right && arr[left] <= value){
33                 left++;
34             }
35             if(pivot == left && pivot == right){
36                 continue;
37             }
38             /*
39             pivot的值通过交换变成left，
40             但是暂时不改变arr[left]，因为（如果有）下一次交换会让它赋值为arr[right]，并不需要它本身的值
41              */
42             arr[pivot] = arr[right];
43             arr[right] = arr[left];
44             pivot = left;
45         }
46         arr[pivot] = value;
47 
48         quick_sort(arr,start,pivot-1);
49         quick_sort(arr,pivot+1,end);
50     }