?
目錄
一、常見排序算法的實現(xiàn)?
?1.1?交換排序
1.1.1?基本思想
1.1.2?冒泡排序?
1.1.3?快速排序
1.2 歸并排序
1.3 非比較排序
二、排序算法復(fù)雜度及穩(wěn)定性分析
?人總得為過去的懶惰而付出點代價！
一、常見排序算法的實現(xiàn)?
?1.1?交換排序
1.1.1?基本思想
基本思想：所謂交換，就是根據(jù)序列中兩個記錄鍵值的比較結(jié)果來對換這兩個記錄在序列中的位置，交換排序的特點是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動。
1.1.2?冒泡排序?
詳細(xì)內(nèi)容見：冒泡排序鏈接
冒泡排序：
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)//趟數(shù)
{
int end = n - i - 1;
for (int j = 0; j < end; ++j)//交換次數(shù)
{
if (a[j] > a[j + 1])
{
Swap(&a[j], &a[j + 1]);
}
}
}
}
冒泡排序優(yōu)化：【當(dāng)?shù)谝惶诉M行交換的時候，沒有進行交換，說明數(shù)組是有序的，那么就不需要進行后面幾趟的冒泡了】?
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)//趟數(shù)
{
int exchange = 0;
int end = n - i - 1;
for (int j = 0; j < end; ++j)//交換次數(shù)
{
if (a[j] > a[j + 1])
{
exchange = 1;
Swap(&a[j], &a[j + 1]);
}
}
if (exchange == 0)
{
break;
}
}
}把直接插入排序和優(yōu)化后的冒泡排序進行比較：?如果順序是有序的，兩者是一樣的；但是，如果是局部有序，或者接近有序，那么插入適應(yīng)性和比較次數(shù)更少
1. 冒泡排序是一種非常容易理解的排序
2. 時間復(fù)雜度：O(N^2)
3. 空間復(fù)雜度：O(1)
4. 穩(wěn)定性：穩(wěn)定
1.1.3?快速排序
快速排序是Hoare于1962年提出的一種二叉樹結(jié)構(gòu)的交換排序方法，其基本思想為：任取待排序元素序列中的某元素作為基準(zhǔn)值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準(zhǔn)值，右子序列中所有元素均大于基準(zhǔn)值，然后最左右子序列重復(fù)該過程，直到所有元素都排列在相應(yīng)位置上為止。
?單趟排序：選出一個key，一般是第一個數(shù)或者是最后一個數(shù)，排序之后要求左邊的值都比key小，右邊的值都比key大
將區(qū)間按照基準(zhǔn)值劃分為左右兩半部分的常見方式有（單趟排序）：
（1）hoare版本（霍爾）
key在左邊（第一個數(shù)）
先右邊的right找比key小的數(shù)據(jù)，找到就停止，然后左邊的left找比key大的數(shù)據(jù)，找到就停止，然后進行交換數(shù)據(jù)，一直到left和right相遇，將該位置的值和key進行交換
【因為，交換完之后【left是小的】，右面先走，所以相遇的位置一定是比key小的數(shù)字】
【相遇的情況只有兩種，left主動和right碰面和right主動和left碰面，這兩種情況，都是在比key小的位置停下來】
key在右邊（最后一個數(shù)）
先左邊的left找比key大的數(shù)據(jù)，找到就停止，然后右邊的right找比key小的數(shù)據(jù)，找到就停止，然后進行交換數(shù)據(jù)，一直到left和right相遇，將該位置的值和key進行交換
【因為，交換完之后【left是小的】，左面先走，所以相遇的位置一定是比key大的數(shù)字】
【相遇的情況只有兩種，left主動和right碰面和right主動和left碰面，這兩種情況，都是在比key大的位置停下來】
代碼1展示：
void PartSort1(int* a, int left, int right)
{
int keyi = left;
while (left < right)
{
while (left < right && a[right] >= a[keyi])
right--;
while (left < right && a[left] <= a[keyi])
left++;
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[keyi]);
}細(xì)節(jié)問題：（1）【key在左面】如果right在走得時候，遇到左面的數(shù)字一直小于等于key，就會一直--，就會越界，所以加上left<right
（2）挖坑法
key在左邊（第一個數(shù)）
邊首先，把key值保存，然后這個位置成為一個坑位，然后右邊的right找比key小的數(shù)據(jù)，找到就填補坑位，此時右面的right形成一個坑位，需要左面的left找比key大的數(shù)據(jù)，找到后填補右面的坑位，一直到left和right相遇，然后key填補相遇時的坑位【左邊做坑，右邊先走；右邊做坑，左邊先走】
key在右邊（最后一個數(shù)）也同理
和hoare相比，代碼幾乎一樣，但是容易理解：（1）不用理解為什么相遇位置比key?。?）不需要理解左邊做key，右邊先走
代碼2展示：
int PartSort2(int* a, int left, int right)
{
int key = a[left];
int pit = left;
while (left < right)
{
while (left < right && a[right] >= key)
{
right--;
}
a[pit] = a[right];
pit = right;
while (left < right && a[left] <= key)
{
left++;
}
a[pit] = a[left];
pit = left;
}
a[pit] = key;
return pit;
}（3）前后指針法
key在左邊（第一個數(shù)）
兩個指針，一個prev，一個cur。剛開始?prev在keyi的位置，cur在keyi的下一個位置;cur找小，如果找到prev++,并交換prev和cur的值；【如果cur和prev++在同一個位置，就沒有交換數(shù)據(jù)的必要：如果cur的第一個位置就是比key小，那么需要prev++,然后交換位置，但是在同一個位置，就沒有必要】【while(cur <= right)】
prev和cur的關(guān)系：（1）cur還沒有遇到比key大的值，prev緊跟cur，一前一后（2）cur遇到比key大的值，prev和cur之間間隔著一段比key大的值的區(qū)間。
代碼3展示：
int PartSort3(int* a, int left, int right)
{
int key = a[left];
int prev = left;
int cur = left + 1;
while (cur <= right)
{
if (a[cur] < key && a[cur] != a[++prev])//這個條件，只有前面條件符合才會走后面的條件
{
Swap(&a[cur], &a[prev]);
}
cur++;
}
Swap(&a[left], &a[prev]);//這里不能寫&key，因為并不能改變a[left]的值，不要和局部變量交換
return prev;
}key在右面（最后一個數(shù)）
兩個指針，一個prev，一個cur。剛開始?prev在left-1的位置，cur在left;cur找小，如果找到prev++,并交換prev和cur的值；【如果cur和prev++在同一個位置，就沒有交換數(shù)據(jù)的必要：如果cur的第一個位置就是比key小，那么需要prev++,然后交換位置，但是在同一個位置，就沒有必要】【while (cur <= right - 1】
int PartSort4(int* a, int left, int right)
{
int key = a[right];
int prev = left - 1;
int cur = left;
while (cur <= right - 1)
{
if (a[cur] < key && a[cur] != a[++prev])//這個條件，只有前面條件符合才會走后面的條件
{
Swap(&a[cur], &a[prev]);
}
cur++;
}
Swap(&a[right], &a[++prev]);//這里不能寫&key，因為并不能改變a[left]的值，不要和局部變量交換
return prev;
}整體排序：單趟排序之后，key已經(jīng)放在正確的位置，不需要進行移動，此時只要保證左邊有序，右面有序，就可以保證整體有序了【分治解決子問題】
代碼展示：（hoare單趟排序+分治整體排序）?
//快速排序
int PartSort(int* a, int left, int right)
{
int keyi = left;
while (left < right)
{
while (left < right && a[right] >= a[keyi])
right--;
while (left < right && a[left] <= a[keyi])
left++;
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[keyi]);
return left;
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
return;
int keyi = PartSort(a, begin, end);
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}1. 快速排序整體的綜合性能和使用場景都是比較好的，所以才敢叫快速排序
2. 時間復(fù)雜度：O(N*logN)? 每次調(diào)用快速排序，都需要把所有元素進行遍歷一遍
最好的情況：每次選key都是中位數(shù)O(N*logN)?? 最差的情況：每次選key都是最大的數(shù)字或者最小的數(shù)字O(N^2)? [有序或者接近有序]
3. 空間復(fù)雜度：O(logN)
4. 穩(wěn)定性：不穩(wěn)定
?快速排序優(yōu)化?
?因為最壞的情況，所以可以對key進行優(yōu)化，讓key不是最大或者最小的數(shù)字：（1）隨機選key（2）三個數(shù)字選不大也不小的那個數(shù)字，然后這個數(shù)字和left或者right位置的數(shù)據(jù)進行交換。
代碼展示：
int GetMinIndex(int* a, int left, int right)
{
int mid = left + (right - left) / 2;
if (a[left] < a[mid])
{
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 PartSort1(int* a, int left, int right)
{
int midi = GetMidIndex(a, left, right);
Swap(&a[left], &a[midi]);
int keyi = left;
while (left < right)
{
while (left < right && a[right] >= a[keyi])
right--;
while (left < right && a[left] <= a[keyi])
left++;
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[keyi]);
return left;
}小區(qū)間優(yōu)化：區(qū)間很小時，不再使用遞歸劃分的思路，而是直接使用插入排序?qū)π^(qū)間進行排序，減少遞歸調(diào)用
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
return;
if (end - begin + 1 <= 10)
{
InsertSort(a + begin, end - begin + 1);
}
else
{
int keyi = PartSort1(a, begin, end);
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
}快速排序非遞歸（棧）
void QucikSort(int* a, int begin, int end)
{
ST st;
StackInit(&st);
StackPush(&st, begin);
StackPush(&st, end);
while (!StackEmpty(&st))
{
int right = StackTop(&st);
StackPop(&st);
int left = StackTop(&st);
StackPop(&st);
int keyi = PartSort(a, left, right);
if (left < keyi - 1)
{
StackPush(&st, left);
StackPush(&st, keyi -1);
}
if (right > keyi + 1)
{
StackPush(&st, keyi - 1);
StackPush(&st, right);
}
}
StackDestory(&st);
}?遞歸改成非遞歸：（1）用循環(huán)（2）用?！具f歸會有爆棧的風(fēng)險】
1.2 歸并排序
先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表【先讓左右區(qū)間有序，再對兩個區(qū)間歸并】
一個數(shù)組分成左右兩個數(shù)組，假設(shè)數(shù)組有序，兩個有序數(shù)組，歸并成一個有序數(shù)組。（取兩個數(shù)組中小的數(shù)據(jù)，依此尾插到新的數(shù)組），但是這個數(shù)組是無序的，所以把數(shù)組一直分，一直分到一個數(shù)據(jù)或者沒有數(shù)據(jù)，就可以認(rèn)為是有序的，然后依次合并，然后這個數(shù)組就是有序的?！鞠确衷俸喜ⅰ?/p>
代碼展示：【遞歸】
void _MergeSort(int* a, int begin, int end, int* tmp)
{
if (begin >= end)
{
return;
}
int mid = (begin + end) / 2;//中間值
_MergeSort(a, begin, mid, tmp);//左邊有序
_MergeSort(a, mid + 1, end, tmp);//右邊有序
int begin1 = begin;
int end1 = mid;
int begin2 = mid + 1;
int end2 = end;
int index = begin;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}
memcpy(a+begin, tmp+begin, sizeof(int) * (end - begin + 1));
}
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
printf("malloc fail\n");
exit(-1);
}
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
tmp = NULL;
}（1）mid等于（第一個數(shù)據(jù)的下標(biāo)+最后一個數(shù)據(jù)的下標(biāo)）/2，分成的兩個區(qū)間應(yīng)該是【left，mid】【mid+ 1, right】,否則就會出現(xiàn)死循環(huán)。
（2）分割完再合并，分割完分別調(diào)用合并排序，? 合并排序?qū)懺谡{(diào)用后面。【分割的兩個數(shù)組都有序之后，再合并】【函數(shù)主框架，左面有序+右面有序+合并】
（3）歸并完再把內(nèi)容復(fù)制到原來的數(shù)組里?！練w并的時候需要新的數(shù)組】
（4）類似于后序遍歷
1. 歸并的缺點在于需要O(N)的空間復(fù)雜度，歸并排序的思考更多的是解決在磁盤中的外排序問題。
2. 時間復(fù)雜度：O(N*logN)? ?N個數(shù)據(jù)，logN層?
3. 空間復(fù)雜度：O(N)? ? 時間復(fù)雜度是O(N +?logN)?但是?logN可以忽略不計
4. 穩(wěn)定性：穩(wěn)定
代碼展示：【非遞歸】
//歸并排序
//非遞歸
void MergeSort2(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)
{
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
if (end1 >= n)
end1 = n - 1;
if (begin2 >= n)
{
begin2 = n;
end2 = n - 1;
}
// begin2沒有越界， end2越界，修正end2即可
if (begin2 < n && end2 >= n)
end2 = n - 1;
int index = i;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
tmp[index++] = a[begin1++];
else
tmp[index++] = a[begin2++];
}
while (begin1 <= end1)
tmp[index++] = a[begin1++];
while (begin2 <= end2)
tmp[index++] = a[begin2++];
}
memcpy(a, tmp, n * sizeof(int));
gap *= 2;
}
free(tmp);
}首先gap為1進行歸并，此時2個數(shù)據(jù)一組是有序的，然后gap = gap*2 = 2,判斷gap是否>=n,?然后gap為2進行歸并，此時4個數(shù)據(jù)一組是有序的，然后gap = gap*2 = 4判斷gap是否>=n,然后gap為4進行歸并……直到gap>=n的時候結(jié)束【gap是多少，就多少一組進行合并】
越界問題:begin1是不可能越界的（begin1是等于i的，i又是小于n的）end1、begin2、end2是可能越界的
(1)只有end2越界，進行修正，n-1
（2）begin2越界，那么end2也越界，此時歸并的第二組數(shù)據(jù)都越界，那么begin2和end2就不需要修正，那么第二組區(qū)間不存在
（3）end1越界，進行修正，那么第二組區(qū)間不存在即可
時間復(fù)雜度：O(N*logN)? ? ? ? ???空間復(fù)雜度：O(N)?
調(diào)試小技巧：
// 條件斷點 if (begin1 == 8 && end1 == 9 && begin2 == 9 && end2 == 9) { int x = 0; }當(dāng)我們想要在某一個地方停止，但是比較麻煩，可以直接寫一個條件斷點，然后打一個斷點即可
1.3 非比較排序
比較排序：直接插入排序、希爾排序、選擇排序、堆排序、冒泡排序、快速排序、歸并排序
非比較排序：（1）計數(shù)排序（2）基數(shù)排序、桶排序
計數(shù)排序又稱為鴿巢原理，是對哈希直接定址法的變形應(yīng)用。
計數(shù)排序代碼展示：
void CountSort(int* a, int n)
{
int min = a[0];
int max = a[0];
for (int i = 1; i < n; i++)
{
if (a[i] < min)
min = a[i];
if (a[i] > max)
max = a[i];
}
int range = max - min + 1;
int* countA = (int*)malloc(sizeof(int) * range);
if (countA == NULL)
{
printf("malloc fail\n");
exit(-1);
}
memset(countA, 0, sizeof(int) * range);
for (int i = 0; i < n; i++)
{
countA[a[i] - min]++;
}
int j = 0;
for (int i = 0; i < range; i++)
{
while (countA[i]--)
{
a[j++] = i + min;
}
}
}
首先找出數(shù)據(jù)的最大值的最小值，然后相減+1算出新數(shù)組的大小，然后新數(shù)組的值都賦值為0，然后遍歷以前的數(shù)組，遍歷的數(shù)字-min，就是新數(shù)組的下標(biāo)，這個下標(biāo)里面的值就+1，遍歷完以前的數(shù)組之后，再把新的數(shù)組的值再返回以前的數(shù)組即可
1. 計數(shù)排序在數(shù)據(jù)范圍集中時，效率很高，但是適用范圍及場景有限。（適用于數(shù)據(jù)范圍集中）（適用于整數(shù)，負(fù)數(shù)也可以，其他類型不可以）
2. 時間復(fù)雜度：O(MAX(N,范圍))
3. 空間復(fù)雜度：O(范圍)
4. 穩(wěn)定性：穩(wěn)定
二、排序算法復(fù)雜度及穩(wěn)定性分析
?文章來源：http://www.zghlxwxcb.cn/news/detail-600179.html
?文章來源地址http://www.zghlxwxcb.cn/news/detail-600179.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】一文帶你全面了解排序（下）——冒泡排序、快速排序、歸并排序、計數(shù)排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
