C语言实现快速排序

以整形数据

且以升序为例

快速排序核心思想：

在待排序数组中找一个key值

单次排序后，左边放比key小的，右边放比key大的值

左右两遍不断重复此操作。从而实现排序。

由于递归深度为logN，且数据为N。易得出时间复杂度为N*logN

实现基本框架

void _quick_sort(int left, int right, int*arr)
{
	if (left >= right)
	{
		return;
	}

	int mid=find_mid(arr,left,right);//找到中间值

	swap(&arr[mid], &arr[left]);//使中间值位于左边


	int key=partion(arr,left, right);//进行单次排序

//进行一次后，左边均是小于或等于arr[key]的，右边则是大于或等于arr[key]的
	_quick_sort(left, key-1,arr);//进行左边

	_quick_sort(key + 1, right,arr);//进行右边
	

}

解释：find_mid 用于找左右中三个之间的中间值，并把他放在左边（为何放左边需要先看partion的实现，而不断的找中间值是为了提高效率）。

partion 进行单次排序（具体实现看下文）

根据partion返回的key值。重复对左边或右边进行相同操作。

递归终止条件：如果left 大于right.则返回。

pation的实现。

实现的方式很多，这里只展示一种，其核心思想是类似的。

int partion(int*arr,int left,int right)
{

	int key = arr[left];
	int prev = left;
	int cur = prev+1;
	while (cur <= right)
	{
		if (arr[cur] < key&&(++prev) != cur)
		{
			swap(&arr[cur], &arr[prev]);
		}
		cur++;
	}

	swap(&arr[left], &arr[prev]);

	return prev;
}

走读代码：第一步：key获取arr最左边的值。并以这个值为基准

循环初始化：prev=left. cur=prev+1

cur开始往右找小的。如果找到小的。且prev的下一个位置并不是cur，因为已经++了prev。

所以直接交换arr[prev]跟arr[cur]的值（如果下一个位置是cur,则没有交换的必要）

当循环结束时

prev前面一定都是比key小的值（包括arr[prev]）。然后交换arr[prev]跟arr[left]。

返回prev。

此时完成一次排序

若能理解上述代码实现，则大概率能明白为什么要放左边

---

至于在三个数直接找中间值。以及交换函数比较简单，这里就不再展示。

拓展：可实现非递归版本

根据队列和栈的结构特点，模拟上述代码的递归。

即可实现。