学习：三路快速排序

╰半橙微兮° 2023-03-12 12:10 10阅读 0赞

## 学习：三路快速排序 ##

![在这里插入图片描述][2020050818055518.png]C语言版：

#include <stdio.h>
    
    void swap(int *a, int *b)
    { 
    	int t=*a;
    	*a=*b;
    	*b=t;
    }
    
    //三路快排，a[l...lt-1]<pivot,a[lt...gt-1]=pivot,a[gt...r]>pivot
    void __quickSort(int a[], int l, int r)
    { 
    	int lt=l,gt=r+1,i=l+1,pivot=a[l];
    	if(l >= r)
    		return;
    	while( i < gt )
    	{ 
    		if(a[i] < pivot)
    		{ 
    			swap( &a[lt+1], &a[i] );
    			lt++;
    			i++;
    		}
    		else if(a[i] == pivot)
    		{ 
    			i++;
    		}
    		else
    		{ 
    			swap(&a[gt-1], &a[i]);
    			gt--;
    		}
    	}
    	swap(&a[l], &a[lt]);
    	__quickSort(a,l,lt-1);
    	__quickSort(a,gt,r);
    }
    
    void quickSort(int a[], int n)
    { 
    	__quickSort(a,0,n-1);
    }
    
    int main()
    { 
    	int i,a[10]={ 90,88,97,76,45,44,63,25,10,40};
    	quickSort(a,10);
    	for(i=0; i<10; i++)
    		printf("%d ",a[i]);
    	return 0;
    }

c++版：

#include <iostream>
    #include <ctime>
    #include <cstdlib>
    using namespace std;
    
    template <class T>
    void __quickSort(T a[], int l, int r)
    { 
    	if(l >= r)
    		return;
    	T pivot=a[l];
    	int lt=l,gt=r+1,i=l+1;
    	while(i < gt)
    	{ 
    		if(a[i] < pivot)
    		{ 
    			swap(a[lt+1] , a[i]);
    			i++;
    			lt++;
    		}
    		else if(a[i] == pivot)
    		{ 
    			i++;
    		}
    		else
    		{ 
    			swap(a[gt-1] , a[i]);
    			gt--;
    		}
    	}
    	swap(a[l] , a[lt]);
    	__quickSort(a, l, lt-1);
    	__quickSort(a, gt, r);
    }
    
    template <class T>
    void quickSort(T a[], int n)
    { 
    	__quickSort(a,0,n-1);
    }
    int main()
    { 
    	int a[15]={ 0};
    	srand(time(NULL));
    	for(int i=0; i<15; i++)
    	{ 
    		a[i]=rand()%100;
    		cout<<a[i]<<" ";
    	}
    	cout<<endl;
    	
    	quickSort(a,15);
    	for(int i=0; i<15; i++)
    		cout<<a[i]<<" ";
    	cout<<endl;
    	return 0;
    }

[2020050818055518.png]: /images/20230312/9f39fb779f7142ea90d2404232681a9e.png