238-快速排序算法(递归，非递归，随机取）

Love The Way You Lie 2022-11-12 01:44 206阅读 0赞

## 快速排序算法（递归）的实现 ##

int Parition(int* ar, int left,int right)
    {
        
    	assert(ar != nullptr);
    	int tmp = ar[left];
    	while (left < right)
    	{
        
    		while (left < right && ar[right] > tmp) --right;
    		ar[left] = ar[right];
    		while (left < right && ar[left] <= tmp) ++left;
    		ar[right] = ar[left];
    	}
    	ar[left] = tmp;
    	return left;
    }
    
    void QuickPass(int* ar, int left, int right)
    {
        
    	if (left < right)	
    	{
        
    		int pos = Parition(ar, left, right);
    		QuickPass(ar, left, pos - 1);
    		QuickPass(ar, pos + 1, right);
    	}
    }
    
    void QuickSort(int* ar, int n)
    {
        
    	NiceQuickPass(ar, 0, n - 1);
    }
    
    int main()
    {
        
    	int ar[] = {
         56,12,89,90,23,34,100,56,45,78,67 };
    	int n = sizeof(ar) / sizeof(ar[0]);
    	for (auto& x : ar) {
         cout << x << " "; }
    	cout << endl;
    	QuickSort(ar, n);
    	for (auto& x : ar) {
         cout << x << " "; }
    
    	return 0;
    }

![在这里插入图片描述][2021032120564518.png_pic_center]

## 快速排序算法（非递归）的实现 ##

#include<iostream>
    #include<limits.h>
    #include<vector>
    #include<assert.h>
    #include<queue>
    using namespace std;
    
    int Parition(int* ar, int left,int right)
    {
        
    	assert(ar != nullptr);
    	int tmp = ar[left];
    	while (left < right)
    	{
        
    		while (left < right && ar[right] > tmp) --right;
    		ar[left] = ar[right];
    		while (left < right && ar[left] <= tmp) ++left;
    		ar[right] = ar[left];
    	}
    	ar[left] = tmp;
    	return left;
    }
    
    void NiceQuickPass(int* ar, int left, int right)
    {
        
    	std::queue<int> qu;
    	qu.push(left); qu.push(right);
    	while (!qu.empty())
    	{
        
    		left = qu.front(); qu.pop();
    		right = qu.front(); qu.pop();
    		int pos = Parition(ar, left, right);
    		if (left < pos - 1)
    		{
        
    			qu.push(left);
    			qu.push(pos - 1);
    		}
    		if (pos + 1 < right)
    		{
        
    			qu.push(pos + 1);
    			qu.push(right);
    		}
    	}
    }
    
    void QuickSort(int* ar, int n)
    {
        
    	NiceQuickPass(ar, 0, n - 1);
    }
    int main()
    {
        
    	int ar[] = {
         56,12,89,90,23,34,100,56,45,78,67 };
    	int n = sizeof(ar) / sizeof(ar[0]);
    	for (auto& x : ar) {
         cout << x << " "; }
    	cout << endl;
    	QuickSort(ar, n);
    	for (auto& x : ar) {
         cout << x << " "; }
    
    	return 0;
    }

## 随机取法 ##

int RandParition(vector<int>& br, int left, int right)
    {
        
    	srand(time(nullptr));
    	int index = rand() % (right - left+1)+ left;
    	std::swap(br[left], br[index]);
    	return Parition(br, left, right);
    }

[2021032120564518.png_pic_center]: /images/20221022/d69c7f0838ed427f918427dcf37587ec.png