基础数据结构：快速排序

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。

(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。

(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

//一次划分函数  核心函数  //返回基准值最终所在下标
int Partition(int *arr, int left, int right)
{
	//先讲arr数组里的[left， right]的第一个值 作为基准值
	int tmp = arr[left];

	while(left < right)
	{
		while(left<right && arr[right] > tmp)//左右边界没有相遇且当前右边的值大于基准值tmp
		right--;

		if(left < right)//如果此时，左右边界没有相遇，那就只能证明右边right找到了一个小于等于基准值tmp的值
		{
			arr[left] = arr[right];
		}
		else
		{
			break;
		}
		

		while(left<right && arr[left] <= tmp)//左右边界没有相遇且当前左边的值小于等于基准值tmp
		left++;

		if(left < right)//如果此时，左右边界没有相遇，那就只能证明左边left找到了一个大于基准值tmp的值
		{
			arr[right] = arr[left];
		}
		else
		{
			break;
		}
		
	}

	arr[left] = tmp;//此时 因为 left == right
	return left;//return right ok
}

void Quick(int *arr, int left, int right)
{
	if(left < right)//通过left <right  保证[left, right]这个范围内至少两个数据
	{
		int par = Partition(arr, left, right);

		if(left < par-1)//基准值左半部分  至少有两个值才有必要去递归
		{
			Quick(arr, left, par-1);
		}
		if(par+1 < right)//基准值右半部分  至少有两个值才有必要去递归
		{
			Quick(arr, par+1, right);
		}
	}

}
//快速排序：时间复杂度O（nlogn） 空间复杂度O（1）  稳定性：不稳定 
void QuickSort(int *arr, int len)
{
	Quick(arr, 0, len-1);
}
void Show(int arr[], int len)
{
	for(int i=0; i<len; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("
");
}

int main()
{
	int arr[] = {12,2,39,88,4,6,25,232,62,221};
	QuickSort(arr, sizeof(arr)/sizeof(arr[0]));
	Show(arr, sizeof(arr)/sizeof(arr[0]));
	return 0;
}

运行结果为：