快速排序（C语言实现）-创新互联

一.快排实现 二.快排优化     1.三数取中，随机取中      2..小区间优化

成都创新互联成立以来不断整合自身及行业资源、不断突破观念以使企业策略得到完善和成熟，建立了一套“以技术为基点，以客户需求中心、市场为导向”的快速反应体系。对公司的主营项目，如中高端企业网站企划 / 设计、行业 / 企业门户设计推广、行业门户平台运营、成都App定制开发、手机网站制作、微信网站制作、软件开发、成都多线机房等实行标准化操作，让客户可以直观的预知到从成都创新互联可以获得的服务效果。一.快排实现 快排的一趟目的，将一个数的移动到，左边都比他小，右边都比他大，这个数也相当于到了自己最终要到的位置。这样就能形成两部分，再进行递归左右区间，选数放到合适位置，这样就达到排序的目的了。 一趟排序的实现我们可以采用前后指针法达到目的 定义变量prev,cur和基准key，关键位置keyi

如果cur位置上的值小于key，我们先++prev,如果++prev后 prev==cur 我们就++cur,不交换； ++prev后不等于cur,我们要交换prev和cur位置的值，再++cur，这样我们就避免了原地交换。

如果cur位置上的值大于key,我们就只++cur 

重复上面过程，当cur走出数组时结束循环

最后我们再将prev上的值和关键位置上的值交换即可

这样我们就完成了一次交换接下来我们进行左右区间的递归即可。 下面是相关代码：

// 快速排序前后指针法
int PartSort(int* a, int left, int right)
{
	int keyi = left;
	int prev = left,cur = left + 1;
	while (cur<= right)
	{   
		//满足前一个判断，++prev,如果prev==cur不会进行交换
		if (a[cur]< a[keyi] && ++prev != cur)
		{
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	return keyi;
}

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int keyi = PartSort3(a, left, right);
    //不断的选key,划分区间我们就能实现排序的目的
	//[left,keyi-1] keyi [key+1,right]
	QuickSort(a, left, keyi-1);
	QuickSort(a, keyi + 1, right);
}
void testQuickSort()
{
	int a[] = { 9, 1, 2, 4, 7, 8, 6, 3, 5 };
    //注意我们要传数组最后一个值的下标
	QuickSort1(a, 0, sizeof(a) / sizeof(a[0]) - 1);
	PrintArray(a, sizeof(a) / sizeof(a[0]));
}

二.快排优化 1.三数取中，随机取中

我们排序时可能遇到有序或接近有序的数组，我们一直选取第一个数作为关键值key,可能会造成我们选到的数是大的或是最小的，这样成划分区间次数接近n,这样我们的快排此时的时间复杂度就是O（N^2）,为了避免这样选到这样数，我们可以进行三数取中，就是对我们要划分的区间第一个数，最后一个数，和中间的数进行比较，选到一个中间的数即可。 当然我们也可以交给电脑，随机进行取数，我们最后再交换到第一个位置上即可。

int GetMidIndexR(int* a, int left, int right)
{
    //三数取中 
    int mid = left + (right - left) / 2;

    // 三数取中  随机选key 
	//int mid = left + rand() % (right - left);

	if (a[mid] >a[left])
	{
		if (a[right] >a[mid])
		{
			return mid;
		}
		else if (a[left] >a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else
	{
		if (a[mid] >a[right])
		{
			return mid;
		}
		else if (a[right] >a[left])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
	int index = GetMidIndex(a, left, right);
	Swap(&a[index], &a[left]);

	int keyi = left;
	int prev = left,cur = left + 1;
	while (cur<= right)
	{   
		//满足前一个判断，++prev,如果prev==cur不会进行交换
		if (a[cur]< a[keyi] && ++prev != cur)
		{
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	return keyi;
}

2.小区间优化 我们知道递归调的过程会建立一层层的栈帧，浪费空间和时间，我们可以将区间长度较小的直接用其他排序帮我们排好，我们就省去了很大一部分的递归调用。如果我们每次都平均划分，数组长度为n,最后三层 2^(n-1)，2^(n-2)，2^(n-3)把他们加在一起就可以省去近70%的递归调用了。 一般来说小区间优化使我们一般使用插入排序，进行数组长度小于15时进行插入排序。

下面就是我们进行优化过的代码：

// 插入排序
void InsertSort(int* a, int n)
{   
	for (int i = 0; i< n - 1; i++)
	{
		int end = i;
		int tmp = a[end+1];
		while (end >= 0)
		{
			if (a[end] >tmp)
			{
				a[end+1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
	
}
int GetMidIndexR(int* a, int left, int right)
{
    //三数取中 
    int mid = left + (right - left) / 2;

    // 三数取中  随机选key 
	//int mid = left + rand() % (right - left);

	if (a[mid] >a[left])
	{
		if (a[right] >a[mid])
		{
			return mid;
		}
		else if (a[left] >a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else
	{
		if (a[mid] >a[right])
		{
			return mid;
		}
		else if (a[right] >a[left])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
// 快速排序前后指针法
int PartSort(int* a, int left, int right)
{
	int index = GetMidIndex(a, left, right);
	Swap(&a[index], &a[left]);

	int keyi = left;
	int prev = left,cur = left + 1;
	while (cur<= right)
	{   
		//满足前一个判断，++prev,如果prev==cur不会进行交换
		if (a[cur]< a[keyi] && ++prev != cur)
		{
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	return keyi;
}
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	//小区间优化    区间数量较小时，避免大量的分区间
	if ((right - left + 1)< 15)
	{
		InsertSort(a+left, right - left + 1);
	}
	else
	{
		int keyi = PartSort(a, left, right);
		//[left,keyi-1] keyi [key+1,right]
		QuickSort(a, left, keyi-1);
		QuickSort(a, keyi + 1, right);
	}
}

最后感谢观看！

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

当前名称：快速排序（C语言实现）-创新互联
标题来源：http://cqcxhl.com/article/ggchc.html