C语言实现快速排序

C语言实现快速排序

（升序）快速排序的核心思想：

定义个一个基准值，单次排序过后，大的在右边，小的在左边。

递归版本：

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

	int key = partion3(arr, left, right);//单次排列

	_quicksort(arr, left, key - 1);
	_quicksort(arr, key + 1,right);



}

上述代码，如果左边大于等于右边则停止递归，

进入partion。进行单次排列

此时小的均在Key的右边，大的均在Key的左边。再重复这个步骤。递归左边和右边。

从而实现排列

关于partion实现的3种方式

方式1：

int partion1(int*arr, int left, int right)
{
	int mid = find_mid_number(arr, left, right);//找中间值，提高递归效率
	swap(&arr[mid], &arr[left]);
	int key = left;

	while (left=arr[key] && left < right)//右边找小
		{
			right--;
		}
		while (arr[left] <= arr[key] && left < right)//左边找大
		{
			left++;
		}
		swap(&arr[left], &arr[right]);
	}
	swap(&arr[key], &arr[left]);
	return left;

}

 将左边第一个定义为基准值，然后从右边开始找（找大），找到后再到左边（找小）。交换

并循环这个过程，直到不满足循环条件。此时再将左边的值跟left对应的值交换。

则，left左边均是比arr[left]小的，右边则是大的

方式2：

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

	int mid = find_mid_number(arr, left, right);
	swap(&arr[left],&arr[mid]);
	int key = arr[left];
	int pivot = left;

	while (left < right)
	{
		while (left < right&&arr[right] >= key)
		{
			right--;
		}
		arr[pivot] = arr[right];
		pivot = right;
		while (left < right&&arr[left] <= key)
		{
			left++;
		}
		arr[pivot] = arr[left];
		pivot = left;
	}

	arr[pivot] = key;
	return pivot;

}

挖坑法。其核心思想与方式1类似，但较简单。原理是，制造出一个坑，然后右边开始找小。

找到后放进坑里，自身则边为坑，然后再左边再开始找大。找到后再放进坑里，自身再变为坑。如此循环。当循环结束时则坑位的左边均是比基准值小或等于的，

右边则是比基准值大或等于的

最后再把Key值放进坑里，return 坑位即可

方式3：

int partion3(int*arr, int left, int right)
{
	int mid = find_mid_number(arr, left, right);
	swap(&arr[mid], &arr[left]);
	int prev = left;
	int keyi = left;
	int cur = prev + 1;
	while (cur <= right)
	{
		if (arr[cur] < arr[keyi] && prev++ != cur)
		{
			swap(&arr[cur], &arr[prev]);
		}
		cur++;
	}
	swap(&arr[keyi], &arr[prev]);
	return prev;
}

指针法：定义一个搜索指针cur,跟一个接受指针prev。

cur从左往右找找小，如果找到且上一个不是prev，则交换。

从而prev往前的均是比基准值小的。prev往后的均是比cur大的，

最后基准值的位置与prev的位置交换，返回prev即可

关于快速排序的非递归实现

//非递归
void none_quicksort(int*arr, int left, int right)
{
	Stack p;
	StackInit(&p);
	StackPush(&p, left);
	StackPush(&p, right);

	while (!StackEmpty(&p))
	{
		int _right = StackTop(&p);
		StackPop(&p);
		int _left = StackTop(&p);
		StackPop(&p);
		int key=partion3(arr, _left, _right);

		if (key > _left+1)
		{
			StackPush(&p, _left);
			StackPush(&p, key - 1);
		}
		if (key < _right - 1)
		{
			StackPush(&p, key + 1);
			StackPush(&p, _right);
		}

	}

}

可以用栈模拟实现递归。代码如上图，用队列也可实现。