// 快速排序前后指針?lè)?int PartSort(int* a, int left, int right)
{
int keyi = left;
int prev = left,cur = left + 1;
while (cur<= right)
{
//滿足前一個(gè)判斷,++prev,如果prev==cur不會(huì)進(jìn)行交換
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,劃分區(qū)間我們就能實(shí)現(xiàn)排序的目的
//[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 };
//注意我們要傳數(shù)組最后一個(gè)值的下標(biāo)
QuickSort1(a, 0, sizeof(a) / sizeof(a[0]) - 1);
PrintArray(a, sizeof(a) / sizeof(a[0]));
}
二.快排優(yōu)化
1.三數(shù)取中,隨機(jī)取中我們排序時(shí)可能遇到有序或接近有序的數(shù)組,我們一直選取第一個(gè)數(shù)作為關(guān)鍵值key,可能會(huì)造成我們選到的數(shù)是大的或是最小的,這樣成劃分區(qū)間次數(shù)接近n,這樣我們的快排此時(shí)的時(shí)間復(fù)雜度就是O(N^2),為了避免這樣選到這樣數(shù),我們可以進(jìn)行三數(shù)取中,就是對(duì)我們要?jiǎng)澐值膮^(qū)間第一個(gè)數(shù),最后一個(gè)數(shù),和中間的數(shù)進(jìn)行比較,選到一個(gè)中間的數(shù)即可。
當(dāng)然我們也可以交給電腦,隨機(jī)進(jìn)行取數(shù),我們最后再交換到第一個(gè)位置上即可。int GetMidIndexR(int* a, int left, int right)
{
//三數(shù)取中
int mid = left + (right - left) / 2;
// 三數(shù)取中 隨機(jī)選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;
}
}
}
// 快速排序前后指針?lè)?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)
{
//滿足前一個(gè)判斷,++prev,如果prev==cur不會(huì)進(jìn)行交換
if (a[cur]< a[keyi] && ++prev != cur)
{
Swap(&a[cur], &a[prev]);
}
cur++;
}
Swap(&a[prev], &a[keyi]);
keyi = prev;
return keyi;
}
2.小區(qū)間優(yōu)化
我們知道遞歸調(diào)的過(guò)程會(huì)建立一層層的棧幀,浪費(fèi)空間和時(shí)間,我們可以將區(qū)間長(zhǎng)度較小的直接用其他排序幫我們排好,我們就省去了很大一部分的遞歸調(diào)用。如果我們每次都平均劃分,數(shù)組長(zhǎng)度為n,最后三層 2^(n-1),2^(n-2),2^(n-3)把他們加在一起就可以省去近70%的遞歸調(diào)用了。
一般來(lái)說(shuō)小區(qū)間優(yōu)化使我們一般使用插入排序,進(jìn)行數(shù)組長(zhǎng)度小于15時(shí)進(jìn)行插入排序。下面就是我們進(jìn)行優(yōu)化過(guò)的代碼:
// 插入排序
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)
{
//三數(shù)取中
int mid = left + (right - left) / 2;
// 三數(shù)取中 隨機(jī)選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;
}
}
}
// 快速排序前后指針?lè)?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)
{
//滿足前一個(gè)判斷,++prev,如果prev==cur不會(huì)進(jìn)行交換
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;
}
//小區(qū)間優(yōu)化 區(qū)間數(shù)量較小時(shí),避免大量的分區(qū)間
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);
}
}
最后感謝觀看!你是否還在尋找穩(wěn)定的海外服務(wù)器提供商?創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源,準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性,企業(yè)級(jí)服務(wù)器適合批量采購(gòu),新人活動(dòng)首月15元起,快前往官網(wǎng)查看詳情吧
當(dāng)前題目:快速排序(C語(yǔ)言實(shí)現(xiàn))-創(chuàng)新互聯(lián)
轉(zhuǎn)載來(lái)源:http://vcdvsql.cn/article42/ggchc.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供動(dòng)態(tài)網(wǎng)站、自適應(yīng)網(wǎng)站、微信公眾號(hào)、搜索引擎優(yōu)化、網(wǎng)站改版、App設(shè)計(jì)
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請(qǐng)盡快告知,我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如需處理請(qǐng)聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來(lái)源: 創(chuàng)新互聯(lián)
猜你還喜歡下面的內(nèi)容