【算法狂想曲】排序 之 快速排序

2020-03-31   118 次阅读


天天水博客,今天特别水
在LeetCode做题做到一题关于排序的,题目非常简单,就是简单的对C++容器中的数据进行排序

题目描述

给你一个整数数组 nums,请你将该数组升序排列。

提示:
1 <= nums.length <= 50000
-50000 <= nums[i] <= 50000

一看到这个提示本人立刻就绷紧了神经,这个提示意味着这题有百分之99的几率会在时间复杂度上出幺蛾子,因此本人很行云流水的安排了一段冒泡排序上去探探风

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        for(int i=0;i<nums.size()-1;i++)
        {
            for(int j=i+1;j<nums.size();j++)
            {
                if(nums[i]>nums[j])
                {
                    int temp = nums[i];
                    nums[i]=nums[j];
                    nums[j]=temp;
                }
            }
        }
        return nums;
    }
};

别骂了别骂了,很简单的一个基础冒泡排序,时间复杂度O(N2),当时心想百分之99.9会超时,果不其然,超时了,查看数据状况时,10组数据过了9组,还有一组那丧心病狂的数据量我都懒得数了,因此冒泡排序绝对性不通的

思路

这时我才想到了老朋友——快速排序
这玩意从刚开始学数据结构到现在就一直一知半解,裸写模板也写的不是很好,但是在网上了解了一下,快速排序是面试经常会考的东西
有些人可能会说了,快速排序这么简单的东西面试值得考?

前提是你要会啊
如果你连这最基础的东西都不会,那肯定秒挂
现在就是很多考试九十多分的快速排序都不会写

因此今天菜鸡我就来好好巩固一下

快速排序原理(注意,这里默认是从小到大排序,从大到小排序直接修改就行了)

在网上查询了部分资料后
本人大概了解了快速排序的基本原理
首先给定一组数据,你要先确定一个数作为中间比较数,随后要找出这个数在数组中的位置
这个位置要满足什么条件呢?

  • 这个位置左边的数都比这个数小或等于
  • 这个位置右边的数都比这个数大或等于

比如给定一组数据4,6,3,5,3,42,6
将4设为中间比较数,确定的位置就是数组下标为2的位置
3,3,4,6,5,42,6
但是我们发现只有中间比较数的位置变更了,两边的数的相对位置并没有发生变化
确定了4的位置后,我们再把左侧与右侧的数据都看作是一组数据,套用刚才的方法
3,3
6,5,42,6
确定位置完成后
3,3
5,6,6,42
总数据:3,3,4,5,6,6,42
6,42
确定完成
排序后数据为
3,3,4,5,6,6,42
类似二叉树遍历

大体思路原理完成后,我们就开始设计算法
首先我们可以设定两个变量lowhigh
分别设定为数据的开头与结尾
这里我们设定中间比较数为数据开头的数(实际上这个数的确定是有讲究的,感兴趣的大佬可以上网查询,这里只是为了方便)
设立一个临时变量temp来存储该数
随后开始操作

while(low<high){
	while(low<high && arr[high]>=temp)    //在数组索引为high的数如果大于等于temp,就将该数留在原地,high索引减1
		high--;
	arr[low]=arr[high];                   //否则将该数扔到中间比较数位置的前面
	while(low<high && arr[low]<=temp)      //在数组索引为low的数如果小于等于temp,就将该数留在原地,low索引加1
		low++;
	arr[high]=arr[low];                    //否则将该数扔到中间比较数位置的后面
	}
	arr[low]=temp;                         //当中间比较数放入确定的位置

这样就完成了对中间比较数的位置的确定,随后我们就只需要一个递归就可以完成对左右两侧数据的操作了

完整AC代码

按照思路修改了代码果然AC了,虽然排名不是很理想,但是至少AC了,菜鸡正常水平

class Solution {
public:
    void QuickSort(vector<int>& nums,int low,int high)
    {
        int L=low;          //因为修改了low和high所以在这边定义两个临时变量存储原来的low和high
        int H=high;
        if(low>=high)        //如果low大于等于high直接return
        return;
        int temp = nums[low];  //储存中间比较数
        while(low<high)
        {
            while(low<high && nums[high]>=temp)
            high--;
            nums[low]=nums[high];
            while(low<high && nums[low]<=temp)
            low++;
            nums[high]=nums[low];
        }
        nums[low]=temp;
       
        QuickSort(nums,L,low-1);    //对左侧数据进行快排
        QuickSort(nums,low+1,H);    //对右侧数据进行快排
    }
    vector<int> sortArray(vector<int>& nums) {
       QuickSort(nums,0,nums.size()-1);
        return nums;
    }
};

结论

终于会快排了,很开心

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议