105-对快速排序算法的实现和分析

比眉伴天荒 2022-12-29 06:35 79阅读 0赞

## 快速排序 ##

首先先引入需要用到的辅助函数

#include<stdio.h>
    
    /*辅助函数：
        1.打印数据
    	2.判断整个数据序列是否已经有序
    	3.交互两个数据swap方法
    */
    
    void Show(int *arr,int len)//打印数据
    {
        
    	for(int i=0;i<len;++i)
    	{
        
    		printf("%d  ",arr[i]);
    	}
    	printf("\n");
    }
    
    bool IsSort(int *arr,int len)//判断整个数据序列是否已经有序
    {
        
    	for(int i=0;i<len-1;++i)
    	{
        
    		if(arr[i]>arr[i+1])
    		{
        
    			return false;
    		}
    	}
    	return true;
    }
    
    void SwapValue(int *a,int *b)//交互两个数据swap方法
    {
        
    	int tmp=*a;
    	*a=*b;
    	*b=tmp; 
    }

***快速排序的思想***  
1、选择一个基准 以当前待排序序列的第一个数据作为基准  
2、通过操作使用基准数据将待排序数据序列划分成：  
左部分（比基准数据都小）  
右部分（比基准数据都大）  
3、对左部分和右部分分别执行以上过程，直到没有左部分和右部分或者两部分只剩下一个数据  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbnpleXU2NjY_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20201220194533187.png_pic_center]  
接下来对快速排序算法的实现

int OneQuick(int *arr,int left,int right)
    {
        
    	int tmp=arr[left];
    	while(left<right)
    	{
        
    		//从right向前找比基准数据小的
    		while(left<right&&arr[right]>=tmp)
    		{
        
    			right--;
    		}
    		arr[left]=arr[right];
    		//从left向后找比基准数据大的
    		while(left<right&&arr[left]<=tmp)
    		{
        
    			left++;
    		}
    		arr[right]=arr[left];
    	}
    	arr[left]=tmp;
        return left; 
    }
    
    void Quick(int *arr,int left,int right)
    {
        
    	int mid=OneQuick(arr,left,right);
    	if(mid-left>1)//左部分至少有两个数据
    	{
        
    		Quick(arr,left,mid-1);
    	}
    	if(right-mid>1)//右部分至少有两个数据
    	{
        
    		Quick(arr,mid+1,right);
    	}
    }
    
    void QuickSort(int *arr,int len)
    {
        
    	Quick(arr,0,len-1);
    }

最后完成主函数

int main()
    {
        
    	int arr[]={
        7,87,29,75,41,50,62,92,69,22,76,77,35};
    	Show(arr,sizeof(arr)/sizeof(arr[0]));
    	QuickSort(arr,sizeof(arr)/sizeof(arr[0])); 
    	Show(arr,sizeof(arr)/sizeof(arr[0]));
    	return 0;
    	
    }

运行结果如下  
![在这里插入图片描述][20201220194641448.png_pic_center]  
***快速排序算法的分析***  
时间复杂度： O(nlogn)  
空间复杂度： O(logn)  
稳定性： 不稳定

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbnpleXU2NjY_size_16_color_FFFFFF_t_70 1]

**优化方法**： 通过使用栈 让消耗空间变少 还可以及时对内存空间进行判满

void Quick2(int *arr,int left,int right)
    {
        
    	Stack st;//记录待排序序列的下标
    	InitStack(&st);
    	Push(&st,right);
    	Push(&st,left);
    	while(!IsEmpty(&st))
    	{
        
    		int start,end;
    		Top(&st,&start);
    		Pop(&st);
    		Top(&st,&end);
    		Pop(&st);
    		int mid=OneQuick(arr,start,end);
    		if(mid-start>1)
    		{
        
    			Push(&st,mid-1);
    			Push(&st,start);
    		}
    		if(end-mid>1)
    		{
        
    			Push(&st,end);
    			Push(&st,mid+1);
    		}
    	}
    	DestroyStack(&st); 
    }

**优化方法**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]  
实现方法如下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][20201223215720338.png_pic_center]  
**优化1**  
当待排序序列的长度分割到一定大小后，使用插入排序。  
原因：对于很小和部分有序的数组，快排不如插排好。当待排序序列的长度分割到一定大小后，继续分割的效率比插入排序要差，此时可以使用插排而不是快排  
截止范围：待排序序列长度N = 10，虽然在5~20之间任一截止范围都有可能产生类似的结果，这种做法也避免了一些有害的退化情形。

**优化2**  
在一次分割结束后，可以把与Key相等的元素聚在一起，继续下次分割时，不用再对与key相等元素分割  
举例：  
待排序序列 1 4 6 7 6 6 7 6 8 6  
三数取中选取枢轴：下标为4的数6  
转换后，待分割序列：6 4 6 7 1 6 7 6 8 6  
枢轴key：6  
本次划分后，未对与key元素相等处理的结果：1 4 6 6 7 6 7 6 8 6  
下次的两个子序列为：1 4 6 和 7 6 7 6 8 6  
本次划分后，对与key元素相等处理的结果：1 4 6 6 6 6 6 7 8 7  
下次的两个子序列为：1 4 和 7 8 7  
经过对比，我们可以看出，在一次划分后，把与key相等的元素聚在一起，能减少迭代次数，效率会提高不少  
具体过程：在处理过程中，会有两个步骤  
第一步，在划分过程中，把与key相等元素放入数组的两端  
第二步，划分结束后，把与key相等的元素移到枢轴周围  
举例：  
待排序序列 1 4 6 7 6 6 7 6 8 6  
三数取中选取枢轴：下标为4的数6  
转换后，待分割序列：6 4 6 7 1 6 7 6 8 6  
枢轴key：6  
第一步，在划分过程中，把与key相等元素放入数组的两端  
结果为：6 4 1 6(枢轴) 7 8 7 6 6 6  
此时，与6相等的元素全放入在两端了  
第二步，划分结束后，把与key相等的元素移到枢轴周围  
结果为：1 4 66(枢轴) 6 6 6 7 8 7  
此时，与6相等的元素全移到枢轴周围了  
之后，在1 4 和 7 8 7两个子序列进行快排

1.void QSort(int arr[],int low,int high)  
    2.{
          
    3.    int first = low;  
    4.    int last = high;  
    5.  
    6.    int left = low;  
    7.    int right = high;  
    8.  
    9.    int leftLen = 0;   // 记录左边与基准元素相等的个数
    10.    int rightLen = 0;  // 记录右边与基准元素相等的个数
    11.  
    12.    if (high - low + 1 < 10)  
    13.    {
          
    14.        InsertSort(arr,low,high);  
    15.        return;  
    16.    }  
    17.      
    18.    //一次分割  
    19.    int key = SelectPivotMedianOfThree(arr,low,high);//使用三数取中法选择枢轴  
    20.          
    21.    while(low < high)  
    22.    {
          
    23.        while(high > low && arr[high] >= key)  
    24.        {
          
    25.            if (arr[high] == key)//处理相等元素  
    26.            {
          
    27.                swap(arr[right],arr[high]);  
    28.                right--;  
    29.                rightLen++;  
    30.            }  
    31.            high--;  
    32.        }  
    33.        arr[low] = arr[high];  
    34.        while(high > low && arr[low] <= key)  
    35.        {
          
    36.            if (arr[low] == key)  
    37.            {
          
    38.                swap(arr[left],arr[low]);  
    39.                left++;  
    40.                leftLen++;  
    41.            }  
    42.            low++;  
    43.        }  
    44.        arr[high] = arr[low];  
    45.    }  
    46.    arr[low] = key;  
    47.  
    48.    //一次快排结束  
    49.    //把与枢轴key相同的元素移到枢轴最终位置周围  
    50.    int i = low - 1;  
    51.    int j = first;  
    52.    while(j < left && arr[i] != key)  
    53.    {
          
    54.        swap(arr[i],arr[j]);  
    55.        i--;  
    56.        j++;  
    57.    }  
    58.    i = low + 1;  
    59.    j = last;  
    60.    while(j > right && arr[i] != key)  
    61.    {
          
    62.        swap(arr[i],arr[j]);  
    63.        i++;  
    64.        j--;  
    65.    }  
    66.    QSort(arr,first,low - 1 - leftLen);  
    67.    QSort(arr,low + 1 + rightLen,last);  
    68.}

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbnpleXU2NjY_size_16_color_FFFFFF_t_70]: /images/20221120/40a7d232cd3649df97259a543f9dae87.png
[20201220194533187.png_pic_center]: /images/20221120/1a5e043071ca4b96869b0e18df0b5e12.png
[20201220194641448.png_pic_center]: /images/20221120/40fffc7ce0b04459a9ccc75ce28c1fd8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbnpleXU2NjY_size_16_color_FFFFFF_t_70 1]: /images/20221120/bb07c61893654e12a0a55463dd2f689a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/5bb98fd9aba349819c97843f928e56d7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/5ac753f8d0c14f1585bbece8643044bb.png
[20201223215720338.png_pic_center]: /images/20221120/d04405a4be10443ea54bbce07214bc3c.png