手撕快速排序

分手后的思念是犯贱 2024-04-06 15:40 25阅读 0赞

## 定义 ##

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法. 其基本思想为:**任取待排序的某个元素作为基准值,按照该排序码将待排序集合分割成两个子序列, 左子序列中所有元素均小于基准值,右子序列均大于基准值,然后左右子序列重复该过程,知道所有元素都有序为止. (核心就是递归的思想,本质上它就是个递归...)**

**先不考虑如何找到划分的位置**, 来看一下快速排序最核心的部分(递归)->

//假设按照升序对array数组中[left, right)区间中的元素进行划分
        public void quickSort(int[] arr, int left, int right) {
            if(left - right >= 1) {
                return;
            }
            
            //按照基准值对array数组的[left, right)区间进行划分
            int div = partition(arr, left, right);
            
            //划分成功后以div为边界形成了左右两部分 -> [left, div), [div + 1, right)
            //递归排[left, div)
            quickSort(arr, left, div);
            
            //递归排[div + 1, right)
            quickSort(arr, div + 1, right);
        }

上述为快速排序递归实现的主框架, 通过代码, 我们发现:**该过程与二叉树的前序遍历有异曲同工之处**, 所以我们在写递归框架时可以想想二叉树的前序遍历规则即可快速写出来,后序只需要分析如何按照基准值来对区间中数据进行划分的方式即可.

## 两种方法 ##

将区间按照基准值划分为左右两半部分的常见方式有:

1.Hoare版

来看一下详细过程:

![eae1a9bc36244f638e84269e610f16f1.png][]

选取最左边的元素作为基准元素.

![bd83fd16609d4c748cfafea65f797dd7.png][]

右指针先向左移动,找到一个比基准值小的元素. 然后左指针向右移动,找到一个比基准值大的元素,等到两个都找到后,彼此交换.

![7792ca81f69a481e847885e27b9660c3.png][]

重复上述过程.

![60c06f0f13a444eea3c879139d99c496.png][] 当左指针和右指针相遇时,交换相遇点与基准元素.

![07b8ad3132aa4fd69335e4d808ef6e61.png][]

这样就分成了两部分.

让我们来看一下代码实现:

private int partition(int[] arr, int left, int right) {
            int i = left, j = right;
            int pivot = arr[left];
            while (i < j) {
                while (i < j && arr[j] >= pivot) {
                    j--;
                }
                while (i < j && arr[i] <= pivot) {
                    i++;
                }
                swap(arr, i, j);
            }
            swap(arr, i, left);
            return i;
        }

2.挖坑法:

顾名思义:就是挖坑.  **即先将第一个(最左边的数据)存放在临时变量中,这时最左边就成了"坑位", 然后移动右指针,找到一个比基准元素小的, 把它放到坑位中,此时右指针的位置就形成了一个"坑位",再移动左指针,找到一个比基准元素大的,放入右指针的"坑位中".重复上述过程即可, 直到左右指针重合.**

private int partition1(int[] arr, int left, int right) {
            int i = left, j = right;
            //确定一个基准值(第一个坑位)
            int pivot = arr[left];
            while(i < j) {
                while(i < j && arr[j] >= pivot) {
                    j--;
                }
                //填左指针的坑(比基准元素小的)
                arr[i] = arr[j];
                while(i < j && arr[i] <= pivot) {
                    i++;
                }
                //填右指针的坑(比基准元素大的)
                arr[j] = arr[i];
            }
            //将基准元素填入左右指针相遇的坑位
            arr[i] = pivot;
            return i;
        }

3.大声发:

![c033dbf731a74bfd82725b2e6bf2305b.png][]

## 快速排序总结 ##

> 1.快速排序整体的综合性和使用场景都是比较好的,所以才敢叫快速排序.
> 
> 2.时间复杂度O(N\*LogN):这个东西可以类比为之前学过的归并排序,它们都是树形结构
> 
> 3.空间复杂度:O(LogN)
> 
> 4.稳定性:不稳定

注:**快速方法有个致命的问题就是:数组越有序,时间复杂度越高,因为当它越有序时,按照之前的方法,就会把数组分成很小的小块,形成单枝的链表结构! 此时时间复杂度高达O(N^2)!**

[eae1a9bc36244f638e84269e610f16f1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/0b34eac27b884a73b3b6a7fb30adad4e.png
[bd83fd16609d4c748cfafea65f797dd7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/963ff9c5b3fc490aa89beea00344e907.png
[7792ca81f69a481e847885e27b9660c3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/763c4bf3d02d4ff18e9a4b899a6afff8.png
[60c06f0f13a444eea3c879139d99c496.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/5fe40a5e9e19465dad8adace50263bf2.png
[07b8ad3132aa4fd69335e4d808ef6e61.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/1b8cdcf8df85421182fdd42061dee9b6.png
[c033dbf731a74bfd82725b2e6bf2305b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/66c16f492d7649beac9ed0ceeaa03936.png