【排序算法】-快排算法

﹏ヽ暗。殇╰゛Y 2022-04-23 11:44 219阅读 0赞

## 前言 ##

笔者也是近期猜对算法感兴趣的，可能对刚入门的同学来说，算法接触不到，但是对于有一些经验的程序员来说，算法的技能是必备的，尤其是面试的时候，动不动就让你手写算法，其实考验的就是你的基础知识。第一篇我就来讲解**快排算法，**开发中用到的并不多，大家先理解快排思路，然后在背代码的时候就很容易了，核心代码不到十行，所以也是一个很简单的算法。

## 正文 ##

快排利用了一个重要的概念就是“分治法”，所谓“分治”就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并，简单的说就是从整体到部分。

分治法不仅在快排中体现，还在归并排序，傅立叶变换（快速傅立叶变换）等等都有所体现。

**快排的思想是，令数组第一位最为初始值（也叫基准数），通过第一次循环完成后把整个数组拆分成左右两部分，左边的数均小于基准数，右边数均大于基准数，然后把这个基准数赋给arr\[i\] = index;， 然后递归重复上述步骤达到整个数据变成有序序列。**

下面我就给定一个数组，然后分析快排是如何进行排序的，

int[] arr = {2, 6, 9, 1};

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODAwMzM4OQ_size_16_color_FFFFFF_t_70][]

令 i 和 j 分别是数组的头和尾，令基准数index = arr\[i\] = 2，

循环，令arr\[j\]（值1）与index（值2）对比，若最后一位（值1）大于等于index（值2），则取arr\[j-1\]再次与index对比，直到取到的数小于基准数才会把这个数赋给基准数，然后i++，此时数组变成了

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODAwMzM4OQ_size_16_color_FFFFFF_t_70 1][]

再次循环，用index（值2）与i++后的值（值6）做对比，小于基准数（值2），则取arr\[j+1\]再次于index对比，直到娶到的数大于基准数才会把这个数赋给arr\[j\]，然后j--，此时数组变成了

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODAwMzM4OQ_size_16_color_FFFFFF_t_70 2][]

本次两个核心循环代码执行后把最初设定的index（值2）赋值给arr\[i\]，此时数组变成了

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODAwMzM4OQ_size_16_color_FFFFFF_t_70 3][]

然后，通过分治的思想把数组变成两个数组再次重复上述的循环，最终达到整个数据变成有序的。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODAwMzM4OQ_size_16_color_FFFFFF_t_70 4][]

**上述描述整合代码如下**

public void sort(int[] arr, int low, int high) {
            if (low >= high) {
                return;
            }
            int i = low;
            int j = high;
            int index = arr[i];//取左边第一位为基准数
            while (i < j) {
                while (i < j && arr[j] >= index) {//从右寻第一个大于等于index的数
                    j--;
                }
                if (i < j) {
                    arr[i++] = arr[j];//将小于index的数赋给arr[i]，然后i向右移位
                }
                while (i < j && arr[i] < index) {//从左寻第一个小于index的数
                    i++;
                }
                if (i < j) {
                    arr[j--] = arr[i];//将大于index的数赋给arr[j]，然后j向左移位
                }
            }
            arr[i] = index;//将基准数填入坑
            sort(arr, low, i - 1);//分治
            sort(arr, i + 1, high);//分治
        }

有喜欢算法的小伙伴可以加我个人微信  15524579896

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODAwMzM4OQ_size_16_color_FFFFFF_t_70]: /images/20220319/e271f673a50a4370bad87d8db4c8f3fa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODAwMzM4OQ_size_16_color_FFFFFF_t_70 1]: /images/20220319/59cc6748a7cf4def9f9fe509ade02332.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODAwMzM4OQ_size_16_color_FFFFFF_t_70 2]: /images/20220319/79fddd91348747e2b65d5a79d943bfd9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODAwMzM4OQ_size_16_color_FFFFFF_t_70 3]: /images/20220319/ca1544cbd8c340ef8d555570a1ab3cba.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODAwMzM4OQ_size_16_color_FFFFFF_t_70 4]: /images/20220319/34d30d638cd042ca91e3cf10d54707d2.png