1、快速排序
創(chuàng)新互聯(lián)公司專(zhuān)注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于成都網(wǎng)站制作、網(wǎng)站設(shè)計(jì)、外貿(mào)網(wǎng)站建設(shè)、潞城網(wǎng)絡(luò)推廣、微信小程序定制開(kāi)發(fā)、潞城網(wǎng)絡(luò)營(yíng)銷(xiāo)、潞城企業(yè)策劃、潞城品牌公關(guān)、搜索引擎seo、人物專(zhuān)訪、企業(yè)宣傳片、企業(yè)代運(yùn)營(yíng)等，從售前售中售后，我們都將竭誠(chéng)為您服務(wù)，您的肯定，是我們最大的嘉獎(jiǎng)；創(chuàng)新互聯(lián)公司為所有大學(xué)生創(chuàng)業(yè)者提供潞城建站搭建服務(wù)，24小時(shí)服務(wù)熱線：18980820575，官方網(wǎng)址：www.cdcxhl.com
通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序?？梢杂眠f歸和非遞歸的方法分別實(shí)現(xiàn)。
平均狀況下，排序n個(gè)項(xiàng)目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況并不常見(jiàn)。事實(shí)上，快速排序通常明顯比其他Ο(n log n) 算法更快。
重慶分公司
重慶分公司
int _QuickSort(int* a,int left,int right,int key)
{
while (left < right)
{
while (left < right&&a[left] <=a[key])
{
left++; //找出比a[key]大的下標(biāo)
}
while (left < right&&a[right] >=a[key])
{
right--; //找出比a[key]小的下標(biāo)
}
swap(a[left], a[right]); //交換
}
if (a[left] > a[key]) //如果需要排序的序列都小于a[key]值
swap(a[left],a[key]);//把 key-1 當(dāng)邊界，如圖中當(dāng)?shù)诙蝍[key]為5時(shí)。
return left;
}
return key;
}
int _QuickSort2(int* a, int left, int right, int key)
{
int cur = left;
int prev = left - 1;
while (cur <= right)
{
if (a[cur] <= a[key])
{
prev++;
if(prev!=cur)
swap(a[prev], a[cur]);
}
cur++;
}
swap(a[prev+1],a[key]);
return prev+1;
}void QuickSort(int* a, int left, int right)
{
assert(a);
if (left < right)
{
int mid = FindMid(a,left,right);//3位取中，把左邊右邊和中間的數(shù)比較，找出中間的數(shù)作為key
swap(a[mid],a[right]);
int key = right;
int boundary=_QuickSort2(a,left,right-1,key);//一趟排序后找出邊界值
//int boundary=_QuickSort(a,left,right-1,key);//有兩種方法找出邊界值
QuickSort(a,left,boundary-1);
QuickSort(a, boundary+1,right);
}
}
//非遞歸借用棧來(lái)完成
void NORQucikSort(int* a,int left,int right)
{
stack s1;
s1.push(left);
s1.push(right);
while (!s1.empty())
{
int key = s1.top();
int _right = s1.top();
s1.pop();
int _left = s1.top();
s1.pop();
if (_left >= _right)
continue;
int boundary = _QuickSort(a, _left, _right - 1, key);
//int boundary = _QuickSort2(a, _left, _right - 1, key);
s1.push(boundary + 1); //先壓key右邊的序列
s1.push(_right);
s1.push(_left);
s1.push(boundary-1);
}
}
//優(yōu)化快速排序 三數(shù)取中
int FindMid(int* a, int left, int right)
{
int mid = left + (right - left) / 2;
if (a[left] > a[right])
{
if (a[left] < a[mid])
return left;
else if (a[mid]>a[right])
return mid;
return right;
}
else
{
if (a[left] > a[mid])
return left;
else if (a[mid] < a[right])
return mid;
return right;
}
} 2、堆排序
堆排序的思想就是如果是升序排序，則建最大堆，反之，則建最小堆。
建堆之后，從第一個(gè)數(shù)開(kāi)始和最后一個(gè)數(shù)交換，縮小堆的范圍（去除最后一個(gè)數(shù)），然后第一個(gè)數(shù)向下調(diào)整，則最大的數(shù)已在最后。直到堆里只有一個(gè)數(shù)。
建堆過(guò)程就是從最后一個(gè)非葉子節(jié)點(diǎn)直到跟節(jié)點(diǎn)向下調(diào)整。假設(shè)我們現(xiàn)在要升序排序。即就是向下調(diào)整時(shí)，把小的交換到父節(jié)點(diǎn)。
堆排序的時(shí)間復(fù)雜度是O(N*lgN),空間復(fù)雜度是O(1)。
void AdjustDown(int *a,int size,int parent) //向下對(duì)齊
{
int child = parent * 2 + 1; //把左孩子的下標(biāo)給child
while (child < size) //保證向下對(duì)齊直到child超出范圍
{
if (child + 1 < size&&a[child + 1] > a[child]) //當(dāng)右孩子>左孩子時(shí),child變?yōu)橛液⒆酉聵?biāo)
{
child++;
}
if (a[parent] < a[child])
{
swap(a[parent],a[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void HeapSort(int *a, int size)
{
assert(a);
for (int i = (size - 2) / 2; i >= 0; i--)
{
AdjustDown(a,size,i); //從圖中下標(biāo)為4的非葉子節(jié)點(diǎn)開(kāi)始，進(jìn)行向下對(duì)齊
}
for (int i = size - 1; i > 0; i--)
{
swap(a[0],a[i]); //把最大堆中的第一個(gè)元素和最后一個(gè)元素交換，此時(shí)最后一個(gè)元素最大
AdjustDown(a,i,0);//把剩余的元素建成最大堆
}
}3、歸并排序
歸并排序時(shí)的時(shí)間復(fù)雜度為O（nlgn) 其主要思想是分治法(divide and conquer)，分就是要將n個(gè)元素的序列劃分為兩個(gè)序列，再分為4個(gè)序列，直到每個(gè)序列只有一個(gè)數(shù)，然后合并兩個(gè)有效序列為一個(gè)有效序列，直到整個(gè)序列為有序序列。
歸并排序的時(shí)間復(fù)雜度O(N*lgN),空間復(fù)雜度是O(N)。
遞歸實(shí)現(xiàn)：
void MergeSort(int *a, int size)
{
assert(a);
int *tmp = new int[size];
int left = 0, right = size - 1;
_MergeSort(a,tmp,left,right);
}
void _MergeSort(int* a, int* tmp, int left, int right)
{
if (left < right)
{
int mid = left + (right - left) / 2;//取中間下標(biāo)
_MergeSort(a,tmp,left,mid); //遞歸進(jìn)行
_MergeSort(a, tmp, mid+1, right); //直到遞歸到左右序列只有一個(gè)元素
Combine(a,tmp,left,mid,mid+1,right);//2個(gè)有序序列合并成一個(gè)
memcpy(a+left,tmp,(right-left+1)*sizeof(int));//把有序序列拷給原數(shù)組
}
}
void Combine(int* a, int* tmp, int begin1, int end1,int begin2, int end2)
{
int index = 0;
while (begin1 <= end1&&begin2 <= end2)
{
while (a[begin1] <= a[begin2]&&begin1<=end1)
{
tmp[index++] = a[begin1];
begin1++;
}
while (a[begin1] > a[begin2] && begin2 <= end2)
{
tmp[index++] = a[begin2];
begin2++;
}
}
while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}
}而遞歸排序的非遞歸實(shí)現(xiàn)，則采取相反的思路，先把整個(gè)數(shù)組分成n個(gè)序列，每次兩個(gè)序列合并。每?jī)蓚€(gè)序列有序后，合4個(gè)序列，以此類(lèi)推。
void MergeSort2(int *a, int size)
{
assert(a);
int gap = 0;
int *temp = new int[size];
int count = 0;
//gap指begin1和end1每次的差值 所差次數(shù)依次為，0,1,3,7（2^n-1）
while (gap < size)
{
int begin1 = 0, end1 = gap, begin2 = end1 + 1, end2 = begin2 + gap;
for (; end2 < size; begin1=end2+1,end1=begin1+gap,begin2=end1+1,end2=begin2+gap)
{
Combine(a,temp,begin1,end1,begin2,end2);
memcpy(a+begin1,temp,(end2-begin1+1)*sizeof(int));
}
if (begin2 < size)
{
end2 = size - 1;
Combine(a, temp, begin1, end1, begin2, size-1);
memcpy(a + begin1, temp, (end2 - begin1 + 1)*sizeof(int));
}
count++;
gap=pow(2,count)-1;
}
}
