数据结构-快速排序

解题思路:

先从后面向前走，找到比5小的放前面，再从前面向后走，找到比5大的放后面，直到L=R;

得到：4 2 3 1 5 9 6 7 8   再这样下去

注意事项：看不懂去B站  https://www.bilibili.com/video/BV1nr4y1P7d6?share_source=copy_web

参考代码：

#include<bits/stdc++.h>
using namespace std;
int get_mid(int arr[],int left,int right)
{
	int pivot=arr[left];
	while(left<right)
	{
		while(arr[right]>pivot&&left<right)
		right--;
		arr[left]=arr[right];
		while(arr[left]<=pivot&&left<right)
		left++;
		arr[right]=arr[left];
	}
	arr[left]=pivot;
	return left;
}
void quick_sort(int arr[],int left,int right)
{
	if(left<right)
	{
		int mid=get_mid(arr,left,right);
		quick_sort(arr,left,mid-1);
		quick_sort(arr,mid+1,right);
	}
}
int main()
{
	int n,i,a[100000];
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{	
	    scanf("%d",&a[i]); 
    }
    quick_sort(a,0,n-1);
    for(i=0;i<n;i++)
    {
	    printf("%d ",a[i]);
    }
    return 0;
}