排序7-快速排序

小咪咪 2022-12-23 12:28 12阅读 0赞

快速排序的核心思想也是分治法。它的实现方式是每次从序列中选出一个基准值，其他数依次和基准值做比较，比基准值大的放右边，比基准值小的放左边，然后再对左边和右边的两组数分别选出一个基准值，进行同样的比较移动，重复步骤，直到最后都变成单个元素，整个数组就成了有序的序列.

## 1. 动图演示: ##

![20201125104215808.gif][]

排序过程分解图:   以\[8,2,5,0,7,4,6,1\]为例

首先，我们随机选择一个基准值4：

![20201125104547478.jpg][]

与其他元素依次比较，大的放右边，小的放左边：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5neWluZ2NoZW5ncWk_size_16_color_FFFFFF_t_70][]

再以同样的方式排左边的数据

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5neWluZ2NoZW5ncWk_size_16_color_FFFFFF_t_70 1][]

继续排序左边的子序列0和1：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5neWluZ2NoZW5ncWk_size_16_color_FFFFFF_t_70 2][]

由于只剩下一个数，所以就不用排了，现在的数组序列是下图这个样子,4左边的序列已经排序成功：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5neWluZ2NoZW5ncWk_size_16_color_FFFFFF_t_70 3][]

4右边的子序列以同样的操作进行，即可排序完成.

## 2. java实现:         快速排序的关键之处在于切分，切分的同时要进行比较和移动， ##

1) 单边扫描

首先我们来看一种叫做单边扫描的做法。

我们随意抽取一个数作为基准值，同时设定一个标记mark代表左边序列最右侧的下标位置，当然初始为0，接下来遍历数组，如果元素大于基准值，无操作，继续遍历，如果元素小于基准值，则把mark+1，再将mark所在位置的元素和遍历到的元素交换位置，mark这个位置存储的是比基准值小的数据，当遍历结束后，将基准值与mark所在元素交换位置即可。

2) 双边扫描

随意抽取一个数作为基准值，然后从数组左右两边进行扫描，先从左往右找到一个大于基准值的元素，将下标指针记录下来，然后转到从右往左扫描，找到一个小于基准值的元素，交换这两个元素的位置，重复步骤，直到左右两个指针相遇，再将基准值与左侧最右边的元素交换.

public static void sort(int[] arr) {
            sort(arr, 0, arr.length - 1);
        }
    
        private static void sort(int[] arr, int startIndex, int endIndex) {
            if (endIndex <= startIndex) {
                return;
            }
            //切分
            int pivotIndex = partition(arr, startIndex, endIndex);
            sort(arr, startIndex, pivotIndex-1);
            sort(arr, pivotIndex+1, endIndex);
        }
    
         //只有这个方法是不同的.
        private static int partition(int[] arr, int startIndex, int endIndex) {
            int left = startIndex;
            int right = endIndex;
            int pivot = arr[startIndex];//取第一个元素为基准值
    
            while (true) {
    
                //从左往右扫描
                while (arr[left] <= pivot) {
                    left++;
                    if (left == right) {
                        break;
                    }
                }
    
                //从右往左扫描
                while (pivot < arr[right]) {
                    right--;
                    if (left == right) {
                        break;
                    }
                }
    
                //左右指针相遇
                if (left >= right) {
                    break;
                }
    
                //交换左右数据
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
    
            //将基准值插入序列
            int temp = arr[startIndex];
            arr[startIndex] = arr[right];
            arr[right] = temp;
            return right;
        }

3. 分析:

快速排序的时间复杂度和归并排序一样，O(n log n)，但这是建立在每次切分都能把数组一刀切两半差不多大的前提下，如果出现极端情况，比如排一个有序的序列，如\[9,8,7,6,5,4,3,2,1\]，选取基准值9，那么需要切分n-1次才能完成整个快速排序的过程，这种情况下，时间复杂度就退化成了O(n^2).

所以说，快速排序的时间复杂度是O(nlogn)，极端情况下会退化成O(n^2)，为了避免极端情况的发生，选取基准值应该做到随机选取，或者是打乱一下数组再选取。

[20201125104215808.gif]: /images/20221120/46aba99146e946529e1098d9bad92d1f.png
[20201125104547478.jpg]: https://img-blog.csdnimg.cn/20201125104547478.jpg
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5neWluZ2NoZW5ncWk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201125104635409.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5neWluZ2NoZW5ncWk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5neWluZ2NoZW5ncWk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201125104718808.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5neWluZ2NoZW5ncWk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5neWluZ2NoZW5ncWk_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201125104808183.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5neWluZ2NoZW5ncWk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5neWluZ2NoZW5ncWk_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201125104911227.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5neWluZ2NoZW5ncWk=,size_16,color_FFFFFF,t_70