快速排序(代码+图解)

快速排序就是先根据一个值，把小于它的放在一边，大于它的放在另一边，自己在中间

然后两边再进行快排，需要进行排序的无序数组长度为1则停止

下面是以最后一个数98为例进行的一次快排

快排图解
代码

#include<bits/stdc++.h>
using namespace std;

void show(int a[],int n)//显示
{
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
    cout<<endl;
}

void change(int &a,int &b)//两个数交换赋值
{
    int t=a;
    a=b;
    b=t;
}

void sortFast(int a[],int l,int r)//快速排序
{
    if(l>=r) return ;

    int start=l,end=r;
    int target = r;
    while(l<r)
    {
        while(a[l]<a[target])
        {
            l++;
        }
        if(l<r)
        {
            change(a[l],a[target]);
            target=l;
        }
        while(a[r]>=a[target])
        {
            r--;
        }
        if(l<r)
        {
            change(a[r],a[target]);
            target=r;
        }
    }
    sortFast(a,start,l-1);//递归快排左侧
    sortFast(a,l+1,end);//递归快排右侧
}

void sortFast(int a[],int l,int r)//改进版
{
    if(l>=r) return ;
    int start=l;
    int end =r;
    int base = a[end];
    while(l<r)
    {
        if(l<r && a[l]<=base) l++;
        if(l<r && a[r]>=base) r--;

        int tmp=a[l];
        a[l]=a[r];
        a[r]=tmp;
    }
    a[end]=a[l];
    a[l]=base;
    sortFast(a,start,l-1);
    sortFast(a,l+1,end);
}
int main()
{
    int arr[]={290,662,307,997,151,423,890,717,640,703,566,883,661,659,245,386};
    int len = sizeof (arr)/sizeof (arr[0]);
    sortFast(arr,0,len-1); 
    show(arr,len);
}