两种快速排序的总结

1.分治法+交换

#include
int a[101], n;
void quicksort(int left, int right)
{
	int i, j, temp, t;
	i = left, j = right;
	temp = a[left];
	if (left > right)//当只有一个数时，下一次递归时i就会大于j,所以必须写此if
		return;
	while (i != j)
	{
		while (a[j] >= temp && i < j)//若没有i 
2.分治法+挖坑填数
 
#include
int a[101], n;
void quicksort(int left, int right)
{
	if (left > right)//当只有一个数时，下一次递归时i就会大于j,所以必须写此if
		return;
	
	int temp,x,i,j;
	i = left;
	j = right;
	temp = a[left];
	x = temp;
	while (i != j)
	{
		while (a[j] >= temp && i < j)
			j--;
		a[i] = a[j];
		while (a[i] <= temp && i < j)
			i++;
		a[j] = a[i];
	}
	
	a[i] = temp;
	quicksort(left, i - 1);
	quicksort(i + 1, right);
}
int main()
{
	int i;
	scanf_s("%d", &n);
	for (i = 1; i <= n; i++)
		scanf_s("%d", &a[i]);
	quicksort(1, n);
	for (i = 1; i <= n; i++)
		printf("%d ", a[i]);
	return 0;
}
 
 
通过洛谷P1177可以了解到快速排序的缺点：在本身有序的数组中时间复杂度仅为O（n²）；
 
所以需要对快排进行优化 ：找到合适的基准值与第一个数交换。
 
方法是定义一个函数 GetMidNum()在第一个数、最后一个数、中间数中选择中间大小的数
 
代码如下：
 
int GetMidNum(int* a,int begin,int end)
{
    int mid = begin + (end - begin)/2;
    //找出个数中处于中间位置的数
    // a[begin] > a[mid]
    if(a[begin] > a[mid])
    {
       if(a[mid] > a[end])//a[begin] > a[mid] > a[end]
           return mid;
       //a[begin] > a[mid] < a[end]
       else if(a[begin] > a[end])//a[begin] > a[end] > a[mid]
           return end;
       else  //  a[end] > a[begin]> a[mid]
           return begin;
    }
    //a[mid]> a[begin]
    else
    {
       if(a[begin] > a[end])//a[mid]> a[begin]> a[end]
           return begin;
       //a[mid]> a[begin]< a[end]
       else if(a[mid] > a[end])//a[mid] > a[end]> a[begin]
           return end;
       else     //a[end] > a[mid] > a[begin]
           return mid;
    }
}
 
与第二种方法整合后代码如下：
 
#include
int a[1000001], n;
int GetMidNum(int* a, int begin, int end)
{
	int mid = begin + (end - begin) / 2;
	//找出个数中处于中间位置的数
	// a[begin] > a[mid]
	if (a[begin] > a[mid])
	{
		if (a[mid] > a[end])//a[begin] > a[mid] > a[end]
			return mid;
		//a[begin] > a[mid] < a[end]
		else if (a[begin] > a[end])//a[begin] > a[end] > a[mid]
			return end;
		else  //  a[end] > a[begin]> a[mid]
			return begin;
	}
	//a[mid]> a[begin]
	else
	{
		if (a[begin] > a[end])//a[mid]> a[begin]> a[end]
			return begin;
		//a[mid]> a[begin]< a[end]
		else if (a[mid] > a[end])//a[mid] > a[end]> a[begin]
			return end;
		else     //a[end] > a[mid] > a[begin]
			return mid;
	}
}

void quicksort(int left, int right)
{
	if (left > right)
		return;
	int i, j, t,x,temp;
	i = left;
	j = right;
	t = GetMidNum(a,left,right);
	temp = a[t];
	a[t] = a[i];
	a[i] = temp;
	x = a[i];
	while (i != j)
	{
		while (a[j] >= temp && i < j)
			j--;
		a[i] = a[j];
		while (a[i] <= temp && i < j)
			i++;
		a[j] = a[i];
		
		
	}
	a[i] = x;
	quicksort(left, i - 1);
	quicksort(i + 1, right);

}
int main()
{
	int i;
	scanf_s("%d", &n);
	for(i=1;i<=n;i++)
		scanf_s("%d", &a[i]);
	quicksort(1, n);
	for (i = 1; i <= n; i++)
		printf("%d ", a[i]);
	return 0;

}
 
两种方法分别修改和参考于 (9条消息) 快速排序（过程图解）_第一楼主的博客-CSDN博客_快速排序
 
以及(10条消息) 白话经典算法系列之六 快速排序 快速搞定_MoreWindows Blog-CSDN博客_快速排序 
 
优化方法参考于(14条消息) 排序算法（五）快速排序多种版本_天涯海角-CSDN博客