大橙子网站建设,新征程启航

为企业提供网站建设、域名注册、服务器等服务

快速排序(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语言实现)-创新互联
URL地址:http://dzwzjz.com/article/ggchc.html
在线咨询
服务热线
服务热线:028-86922220
TOP