大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
// 快速排序前后指针法
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元起,快前往官网查看详情吧