快速排序

发布于 2021-08-26  299 次阅读


今天面武汉的一家公司被问到了快速排序的知识,特此记录,快排在排序算法中用的还蛮多的。

 

排序算法相关概念介绍:

0.1 算法分类

十种常见排序算法可以分为两大类:

  • 比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此也称为非线性时间比较类排序。
  • 非比较类排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此也称为线性时间非比较类排序。

0.2 算法复杂度

0.3 相关概念

  • 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面。
  • 不稳定:如果a原本在b的前面,而a=b,排序之后 a 可能会出现在 b 的后面。
  • 时间复杂度:对排序数据的总的操作次数。反映当n变化时,操作次数呈现什么规律。
  • 空间复杂度:是指算法在计算机

内执行时所需存储空间的度量,它也是数据规模n的函数。

 

快速排序(Quick Sort)

概述:

快速排序是一种不稳定的比较排序算法

基本思想:

通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

快速排序是对冒泡排序算法的一种改进,同冒泡排序一样,快速排序也属于交换排序,通过元素之间的比较和交换位置来达到排序的目的。不同的是,冒泡排序在每一轮只把一个元素冒泡到数列的一端,而快速排序在每一轮挑选一个基准元素,并让其他比它大的元素移动到数列一边,比它小的元素移动到数列的另一边,从而把数列拆解成了两个部分,这种思路就叫做分治法
快速排序是基于“分治法”原理实现,所谓分治法就是不断的将原数组序列按照一定规律进行拆分,拆分后各自实现排序直到拆分到序列只剩下一个关键字为止。快速排序首先选取一个关键字为标志位(关键字的选取影响排序效率),然后将序列中小于标志位的关键字移动至标志位左侧,大于标志位的关键字移动至右侧。一趟比较完成后,整个序列以选取的标志位为界,左侧均小于标志位,右侧均大于关键字。但左右两侧内部并不是有序的(左右两侧关键字个数也不一定相同)。进而继续将左右两侧分别再以这种方式进行排序,直到将序列拆分的剩余一个关键字为止,整个序列即变成有序。

算法描述

快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下:

  • 从数列中挑出一个元素(一般挑第一个元素),称为 “基准”(pivot);
  • 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
  • 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

针对快速排序我的理解始终有些模糊,因此本次我决定编写快排代码并一步步调试,弄懂其原理:(偷懒转自知乎)

1.首先,随机生成十个数字

作者:汇智知了堂
链接:https://zhuanlan.zhihu.com/p/363421644
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

 Random rd = new Random();
        int[] num = new int[10];
        for (int i = 0; i < num.length; i++) {
            num[i] = rd.nextInt(100)+1;
        }
        System.out.println(Arrays.toString(num));

所得如下:

我们便以这十个数字进行对快速排序思想的说明。

我们需要选定基准数,这里,我们选择第一个数字为基准数,即15。

我们用L存储第一个元素的下标,用R存储最后一个元素的下标,如图所示:

我们从R开始往前找,找第一个小于val的数字,放到L的位置,L++。

我们发现,8小于val,则变动如下图所示:

然后我们从L开始往后找,找到第一个大于val的数字,放到R的位置,R- -。

我们发现,46大于val,则变动如下图所示:

2、之后循环这两步,直到L与R相等,我们将基准数放在他们为下标的位置

即如下图所示:

这样,我们就将小于基准数的数字全部放在了基准数的左边,大于基准数的全部放在了基准数的右边。

我们将基准数的左边的数字和基准数右边的数字分别进行上述所有步骤如下图,直至一个分支只有一个元素。

作者:汇智知了堂
链接:https://zhuanlan.zhihu.com/p/363421644
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

3、后面的步骤就是前面步骤的重复,我就不一一描述

直接给出最后的图如下:

4、排序结果为:8 15 36 46 51 55 82 86 89 96

快排代码如下所示,仅供参考:

public class testSort {
    public static void main(String[] args) {
        Random rd = new Random();
        int[] num = new int[10];
        for (int i = 0; i < num.length; i++) {
            num[i] = rd.nextInt(100)+1;
        }
        System.out.println(Arrays.toString(num));
        quickSort(num,0,num.length-1);
        System.out.println(Arrays.toString(num));
    }
    /**
     * 实现快速排序
     * @param num
     * @param i
     * @param j
     */
    public static void quickSort(int[] num,int i,int j){
        if(i >= j){//只剩一个元素不用处理直接结束。
            return;
        }
        //选取基准数
        int val =num[i];
        int l = i;
        int r = j;
        while(l < r){//当l == r时,就是调整完成时
            //从后往前找第一个小于val的数字
            while (l < r && num[r] > val){
                r --;
            }
            if(l < r){//找到了数字
                num[l++] = num[r];
            }
            //从前往后找第一个大于val的数字
            while (l < r && num[l] < val){
                l ++;
            }
            if(l < r){//找到了数字
                num[r--] = num[l];
            }
        }
        //l==r,基准数放进去
        num[l] = val;
        quickSort(num,i,l-1);
        quickSort(num,l+1,j);
    }
}

5、运行结果如下:


她喜欢所以就做咯