快速排序入门

妖狐艹你老母 2022-05-17 02:56 63阅读 0赞

一共两种写法：

一、

![Center][]

#include<iostream>
    #include<assert.h>
    using namespace std;
    
    int OnceSort(int *a, int left, int right)
    {
    	int i = 0;
    	int middle = right;
    	right -= 1;
    
    	while (left < right)
    	{
    		//left找大于middle的数
    		while (left < right && *(a + left) <= *(a + middle))
    			left++;
    
    		//right找小于middle的数
    		while (left < right && *(a + right) > *(a + middle))
    			right--;
    
    		if (left < right)
    		{
    			swap(*(a + left), *(a + right));
    		}
    		else
    		{
    			break;
    		}
    	}
    	if (*(a + left) < *(a + middle))
    	{
    		i = left + 1;
    	}
    	else
    	{
    		i = left;
    	}
    	while (i < middle)
    	{
    		swap(*(a + middle - 1), *(a + middle));
    		middle--;
    	}
    	return i;
    }
    
    void QuickSort(int* a, int left, int right)
    {
    	assert(a);
    	int middle = 0;
    	if (left < right)
    	{
    		middle = OnceSort(a, left, right);
    		QuickSort(a, left, middle - 1);
    		QuickSort(a, middle + 1, right);
    	}
    }

二、

![Center 1][]

这种写法 设置最左为key值，然后从右找比key小的和a【left】互换，从左找比key大的和a【righ】互换，再使用递归。

本人不赞成直接看教程一点一点撸思路的写法，直接看代码代入数据可能学的更快。话不多说，撸码：

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    using namespace std;
     
     int once(int a[],int l,int r){
     	int left = l,key=a[l];
     	while(l<r){
     		while(l<r&&a[r]>=key)  r--;
     		if(l<r&&a[r]<key)
     		swap(a[l],a[r]);
     		while(l<r&&a[l]<=key)  l++;
     		if(l<r&&a[l]<key)  
     		swap(a[l],a[r]);
    	 }
     	a[l] = key;
     	return l;
     }
     
     
     void re(int a[],int l,int r){
     	int mid= 0;
     	if(l<r){
     		mid=once(a,l,r);
     		re(a,l,mid-1);
     		re(a,mid+1,r);
    	 }
     }
     
     int main()
    {
    	int a[]={8,1,4,9,6,3,5,2,7,0};
    	re(a,0,9);
    	for(int i=0;i<10;i++)
    		cout<<a[i]<<endl;
    	
    	return 0;
    	
     }

[Center]: /images/20220517/c7832e98486447948450c62f4e831f1d.png
[Center 1]: /images/20220517/8c1182f05e3a4dc4bfa6b69414ff9e5d.png