图解快速排序

怼烎@ 2023-07-04 06:28 8阅读 0赞

### 文章目录 ###

*  什么是快速排序？
 *  思路
 *  完整的动画演示
 *  代码实现

# 什么是快速排序？ #

快速排序（Quicksort）是对冒泡排序的一种改进

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

# 思路 #

假设我们现在对 （6 1 2 7 9 3 4 5 10 8 ）这 10 个数字进行排序。首先在这个序列中随便找一个数最为 **轴心点**。为了方便，就让第一个数 6 作为基准数吧。接下来，需要将这个序列中所有比基准数大的数放在 6 的右边，比基准数小的数放在 6 的左边，类似下面这种排序  
![在这里插入图片描述][20200209115314284.png]  
在初始状态下，数字 6 在序列的第一位。我们的目标是将6 挪到序列中间的某个位置，假设这个位置是 k，现在就需要寻找这个 k，并且以第 k 位为分界点，左边的是都小于等于 6，右边的书都大于等于 6

方法其实很简单：分别从初始序列 （6 1 2 7 9 3 4 5 10 8 ）两端开始探测。先从 **右** 往 **左** 找一个小于 6 的数，再从 **左** 往 **右** 找一个大于 6 的数，然后交换它们。

# 完整的动画演示 #

相信聪明的你们看了这动画之后都已经会了  
![在这里插入图片描述][20200209124339136.gif]  
快速排序之所以比较快，是因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候  
设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全  
部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样只能在相邻的数之间进  
行交换，交换的距离就大得多了。因此总的比较和交换次数就少了，速度自然就提高了。当  
然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和  
冒泡排序是一样的，都是 O(N 2 )，它的平均时间复杂度为 O (NlogN)。其实快速排序是基于一  
种叫做“二分”的思想

# 代码实现 #

package com.java.springtest.sort;
    
    /** * @author Woo_home * @create by 2020/2/8 */
    public class Demo { 
    
        public static int[] sort(int[] num,int left,int right) { 
            if (left > right) { 
                return null;
            }
            int temp = num[left];
            int i = left;
            int j = right;
            while (i < j) { 
                while (num[j] >= temp && i < j) { 
                    j--;
                }
                while (num[i] <= temp && i < j){ 
                    i++;
                }
                if (i < j) { 
                    int t = num[i];
                    num[i] = num[j];
                    num[j] = t;
                }
            }
            num[left] = num[i];
            num[i] = temp;
    
            sort(num,left,i-1);
            sort(num,i+1,right);
            return num;
        }
    
        public static void main(String[] args) { 
            int[] num = { 6,1,2,7,9,3,4,5,10,8};
            int[] sort = sort(num, 0, num.length-1);
            for (int i : sort) { 
                System.out.print(i + " ");
            }
        }
    }

输出：  
![在这里插入图片描述][20200209150300587.png]

[20200209115314284.png]: https://img-blog.csdnimg.cn/20200209115314284.png
[20200209124339136.gif]: https://img-blog.csdnimg.cn/20200209124339136.gif
[20200209150300587.png]: https://img-blog.csdnimg.cn/20200209150300587.png