快速排序（c语言）

文章目录

• • 1. hoare版本
  • 2.挖坑法
  • 3.前后指针法
  • 4.快速排序
  • 5.优化
  • 6.模拟栈进行非递归实现

1. hoare版本

效果：使key的左边都小于key，key的右边都大于key

// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{
	int keyi = left;
	while (left < right)
	{
		//从右找小
		while (left<right && a[right] >= a[keyi])
		{
			right--;
		}
		//从左找大
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}

		Swap(&a[left], &a[right]);
	}
	Swap(&a[keyi], &a[left]);
	return left;
}

2.挖坑法

效果：使key的左边都小于key，key的右边都大于key

// 快速排序挖坑法版本
int PartSort2(int* a, int left, int right)
{
	int key = a[left];
	while (left < right)
	{
		//从右找小
		while (left < right && a[right]>= key )
		{
			right--;
		}
		a[left] = a[right];
		
		//从左找大
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[right] = a[left];
	}
	a[right] = key;
	return right;

}

3.前后指针法

效果：使key的左边都大于key，key的右边都小于key
ps（若当cur key的左边都小于key，key的右边都大于key）

//快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
	int keyi = left;
	int cur = left + 1;
	int prev = left;
	while (cur <= right)
	{
		if (a[cur] < a[keyi])
		{
			prev++;
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	Swap(&a[keyi], &a[prev]);
	return prev;
}

4.快速排序

上述三种方法都是使key的左边都小于key，key的右边都大于key，所以若key的左边和右边都为有序，那么就可以得到一个有序数组

此时我们可以把key的左边单独拿出来利用上面三种方法的一种进行排序，

得到有序的数组，key的右边也是一样这样就得到有序数组

void QuickSort(int* a, int begin, int end)
{
	if (begin<end)
		return;

	int keyi = PartSort3(a, begin, end);

	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1 , end);
}

5.优化

若将此数组改为降序，采取上述方法，则会分治成这样，时间复杂度为O（N^2）

因此我们采取三数取中，是数组尽量等分来进行分治

int GetMidIndex(int* a, int left, int right)
{
	int mid = (left + right) / 2;

	if (a[left] > a[right])
	{
		if (a[right] > a[mid])
			return right;

		//a[mid]>a[right]
		else if (a[left] > a[mid])
			return mid;
		else
			return left;
	}
	
	//a[left]
	else
	{
		if (a[mid] < a[left])
			return left;

		//a[mid]>a[left]
		else if (a[mid] > a[right])
			return right;

		else
			return mid;

	}
}

6.模拟栈进行非递归实现

void QuickSortNonR(int* a, int begin, int end)
{
	Stack ST;
	InitStack(&ST);
	StackPush(&ST, begin);
	StackPush(&ST, end);
	while (!StackEmpty(&ST))
	{
		int right = StackTop(&ST);
		StackPop(&ST);
		int left = StackTop(&ST);
		StackPop(&ST);
		int key = PartSort2(a, left, right);

		//[left,key-1]
		if (key - 1 > left)
		{
			StackPush(&ST, left);
			StackPush(&ST, key-1);
		}
		//[key+1,right]
		if (right > key + 1)
		{
			StackPush(&ST, key + 1);
			StackPush(&ST, right);
		}
	}
	DestoryStack(&ST);
}