一.快排实现
二.快排优化
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://cdkjz.cn/article/ggchc.html
