QuickSort(快速排序)&&MergeSort(归并排序)的效率比较[搭配LeetCode例题]

  • Post author:
  • Post category:其他




QuickSort(快速排序)&&MergeSort(归并排序)的效率比较



QuickSort代码

void quickSort(vector<int>& nums,int left,int right){
	if(left>=right)
	    return;
	int r=rand()%(right-left+1)+left;
	int x=nums[r];
	swap(nums[r],nums[right]);
	int i=left-1;
	for(int j=left;j<right;j++){
	    if(nums[j]<x)//由于随机数生成范围在[0,32768]之间,若生成数量大,则数重复率高,若此处改为nums[j]<=x,效率会变低很多很多
	        swap(nums[++i],nums[j]);
	}
	swap(nums[++i],nums[right]);
	quickSort(nums,left,i-1);
	quickSort(nums,i+1,right);
}



mergeSort代码

void mergeSort(vector<int>& nums,vector<int>& temp,int left,int right){
	if(left>=right)
	    return;
	int mid=(right+left)>>1
	mergeSort(nums,left,mid);
	mergeSort(nums,mid+1,right);
	for(int i=left;i<=right;i++)
	    temp[i]=nums[i];
	int i=left,j=mid+1;
	for(int k=left;k<=right;k++){
	    if(i==mid+1)
	        nums[k]=temp[j++];
	    else if(j==right+1||temp[i]<=temp[j])
	        nums[k]=temp[i++];
	    else    
	        nums[k]=nums[j++];
	}
}



比较结果

1W

10W

100W

1000W



总结

  1. 快速排序与归并算法都运用了

    分治思想

    ,将问题分成子问题(可以简单求解的子问题)解决后再合并,归并注重与如何



    (合并子问题),而快速排序着重于如何



    (分解子问题)

  2. 快速排序相对归并排序来说不够稳定,不稳定的因素有以下三点:

    1. 与基准数比较之后产生的swap(相同值的相对位置的交换)会导致排序的不稳定
    2. 基准数归位之后的swap也会导致不稳定
    3. 基准数的随机选取也会导致不稳定


    解决方案:用额外空间辅助空间实现稳定快速排序

def MySort(self , arr ):  
	if len(arr) <= 1:  
	    return arr  
	left, right = [], []  
	for i in range(1,len(arr)):  
	    if arr[i] < arr[0]:  
	        left.append(arr[i])  
	    else:  
	        right.append(arr[i])  
	return self.MySort(left) + [arr[0]] + self.MySort(right) 

大于等于(必须时大于等于)的放在右侧数组,小于的放在左侧数组,保证相同数字的相对位置,因为选用的是头部元素,相同的元素本来就在头部元素的右边,所以必须是大于等于。


保证了相同数字的相同数字的相对位置:



return self.MySort(left) + [arr[0]] + self.MySort(right)

  1. 而效率取决于元素的排列是否随机,若接近排列接近有序时时间复杂度会达到O(n^2),我们应该根据不同的情况使用不同的算法,int,double,且数组长度在一定阀值内,则使用快排,如果在阀值外,则用归并。


  2. 衍生出来的子问题:

    1. 求数组中第k大的元素

      215


      用快速排序即可快速得到答案,只需增加一个比较即可,返回选中的分割数的下标等于

      (nums.size()-k)

      即可,因为是顺序排序,所以第k大的元素的下标为元素总数-k,若为要找的元素为第k小的元素则下标为k,逆序排序则反之。这里使用快速排序的时间复杂度其实O(n),因为每次只递归一个部分,该算法也叫

      快速选择

      ,C++中的STL的

      nth_element()

      函数可以进行快速选择,此函数的效果为将数组第n小的元素放在数组的第n个位置,同时保证左侧元素不大于自身,右侧元素不小于自身。


      由快速选择引出的另一道题:

    2. 摆动排序

      324

      解法1:排序后分成两半,进行一小一大拉链合并,

      解法2:

      快速选择

      +

      Three way partition

      解决此题,时间复杂度为O(n),由于只需要找一个中位数,我们并不关心中位数的左右部分是否顺序,只需要满足左部分的元素小于中部分(中位数集合,因为中位数可能很多个),中部分的元素小于右部分即可。利用快速选择找出中位数,

      three way patition

      解决三部分问题


      当元素总数为奇数时mid=mid+1

    3. 求数组中的逆序对

      剑指Offer-51


      逆序对的意思按顺序从数组随机抽两个数,若后一个数比前一个大,则为逆序对。

      如何使用归并排序的思想解决这道题呢?举个例子,数组

      A[2,8,10,11]

      和数组

      B[4,6,7,9]

      ,我们设置一个归并后的数组为

      C

      ,当

      C数组为[2]

      时,

      数组B

      并无比2小的数,即2这个数字没有逆序对,当

      C数组



      [2,4,6,7]

      时,

      数组A



      二号元素8

      <

      数组B



      三号元素9

      ,此时到

      8

      入列为止之前

      B数组

      已经入列了三个元素分别为

      4、6、7

      ,这三个元素都处于8的后面,且比8小,符合逆序对的标准

      ,即

      数组A



      8

      能组成

      3个逆序对

      ,之后

      C数组



      [2,4,6,7,8,9]

      时,

      数组B

      已无元素可以归并,接下来依次将

      A数组

      的元素入列,入列的元素

      10



      11

      能组成的逆序对数量均为

      B数组

      已经入列的元素数量4,逆序对的总数量为

      3+4+4=11



版权声明:本文为qq_27277041原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。