算法设计与分析——递归与分治策略——快速排序

冷不防 2022-11-10 10:44 136阅读 0赞

快速排序——递归算法  
处理i,j的先后顺序不能改变  
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]  
函数：  
partition()函数实现了根据数组第一个元素区分这个数组，比这个元素小的放到mid的前面，比这个元素大的放到mid的后面  
quicksort()函数：实现了递归调用

#include<iostream>
    #include<bits/stdc++.h>
    using namespace std;
    vector<int> vec;
    int partition(vector<int> &vec,int left,int right);
    void QuickSort(vector<int> &vec,int left,int right)
    {
        
    	if(left<right)
    	{
        
    		int mid = partition(vec, left, right);
       	 	QuickSort(vec, left, mid-1);
        	QuickSort(vec, mid + 1, right);
    	}
        
    
    }
    int partition(vector<int> &vec,int left,int right)
    {
        
        int i=left, j=right;
        int temp = vec[left];
        while(i<j)
        {
        
            while(temp<=vec[j]&&i<j)//处理i,j的先后顺序不能改变 
            {
        
                j--;
            }
            while(vec[i]<=temp&&i<j)//处理i,j的先后顺序不能改变 
            {
        
                i++; 
            }
    			swap(vec[i],vec[j]);
        }
        vec[left] = vec[j];
        vec[j] = temp;
        return j;
    
    }
    
    int main()
    {
        
        vector<int> vec={
        6,1,2,7,9,3,4,5,10,8};
        cout<<"排序前的序列：";
    	 
        for (auto a:vec)
        {
        
            cout << a<<" ";
        }
        cout<<endl<<"排序后的序列：";
        int count = vec.size()-1;
        QuickSort(vec, 0, count);
        for (auto a:vec)
        {
        
            cout << a<<" ";
        }
        cout<<endl;
            system("pause");
    	return 0;
    }

![在这里插入图片描述][20210602201752299.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]: /images/20221023/d621ba197dc145a28709b6c394eb06c3.png
[20210602201752299.png]: /images/20221023/832b641fa9bd4425989bf9fe168e79d7.png