1.插入排序
1.1插入排序的思想
插入排序的思想跟摸牌很相似，從我們摸到第二張牌的開始，依次將摸到到牌依次有序的插入到手中，最后手牌變成了有序。
有了大致的思路，接下來就要細(xì)分插入排序的細(xì)節(jié)。
首先考慮某一趟的插入排序。為什么先考慮某一趟呢？因?yàn)楫?dāng)需要解決的問題比較復(fù)雜時先將問題簡單化會有利于問題的解決。
某一趟的插入排序：
整個插入排序：我們回味一下過年打牌的情景，是不是只有從第二張牌開始我們才開始將摸到牌插到手中？所以end是從1開始到n-1結(jié)束。
完整代碼：
void InsertSort(int* arr, int n)
{
for (int i = 1; i < n ; i++)
{
int end = i;
int x = arr[end];
while (end > 0)
{
if (arr[end-1] > x)
{
//后移
arr[end] = arr[end - 1];
end--;
}
else
{
break;
}
}
arr[end] = x;
}
}
1.2插入排序的特點(diǎn)
特點(diǎn)：
- 1.元素集合越接近有序，直接插入排序算法的時間效率越高
- 2.時間復(fù)雜度:O(n^2)(情況最差時,即逆序轉(zhuǎn)有序,最好的情況下為O(n));
- 3.空間復(fù)雜度:O(1);
- 4.穩(wěn)定
2.希爾排序
2.1希爾排序的思想
希爾排序是1959 年由D.L.Shell 提出來的，希爾排序是繼插入排序的一次大幅度的優(yōu)化。希爾排序又叫縮小增量排序。
基本思想：
先將整個數(shù)組分成若干個子數(shù)組,通過對子數(shù)組進(jìn)行排序,達(dá)到數(shù)組"基本有序",再對整個數(shù)組進(jìn)行插入排序,即可達(dá)到有序。
實(shí)現(xiàn)方法：
1,先分組,間隔為Gap的數(shù)據(jù)為一組,然后對這組數(shù)據(jù)進(jìn)行排序,再分組,再排,直到數(shù)組被分完。
2,然后再把Gap減小,繼續(xù)分組,排序。
3,此時數(shù)組基本有序,然后將最后Gap減小為1,即進(jìn)行直接插入排序,得到有序數(shù)組。
圖示：
有了大致思想后就可以開始寫代碼了。還是用化繁瑣為簡單的思想來寫代碼。
先考慮gap=某一個值時，代碼的實(shí)現(xiàn)。
當(dāng)gap=某一個值時，第一組數(shù)據(jù)的插入排序。（下圖）
當(dāng)gap=某一個值時，多組數(shù)據(jù)的插入排序。（下圖）
完整代碼：
//希爾排序
void ShellSort(int* arr, int n)
{
//多次預(yù)排序（gap>1）+直接插入（gap=1）
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;
//對多組數(shù)進(jìn)行插入排序
for (int j = gap; j < gap*2; j++)
{
//對一組數(shù)進(jìn)行插入排序
for (int i = j; i < n ; i += gap)
{
int end = i;
int x = arr[end];
while (end >0)
{
if (arr[end-gap] > x)
{
arr[end] = arr[end-gap];
end = end - gap;
}
else
{
break;
}
}
arr[end] = x;
}
}
}
}
2.1希爾排序的特點(diǎn)
特點(diǎn)：
- 1.希爾排序是對直接插入排序的優(yōu)化。
- 2.當(dāng)gap > 1時都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時，數(shù)組已經(jīng)接近有序的了，這樣就會很快。這樣整體而言，可以達(dá)到優(yōu)化的效果。
- 3.希爾排序的時間復(fù)雜度不好計算，因?yàn)間ap的取值方法很多，導(dǎo)致很難去計算，這里不深究。
- 4.時間復(fù)雜度O(N^1.5)、空間復(fù)雜度O(1)。
- 5.穩(wěn)定性：不穩(wěn)定。
希爾排序不穩(wěn)定說明（圖示）：
3.選擇排序
3.1選擇排序
選擇排序是我感覺最簡單的排序，理解起來很簡單，寫起來也很容易。
基本思想：
-
第一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，存放在序列的起始(末尾)位置，
-
然后選出次小(或次大)的一個元素，存放在最大(最小)元素的下一個位置，
-
重復(fù)這樣的步驟直到全部待排序的數(shù)據(jù)元素排完 。
完整代碼：
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
//選擇排序
void SelectSort(int* arr, int sz)
{
for (int i = 0; i < sz-1; i++)
{
int index = i;
for (int j = i + 1; j < sz; j++)
{
if (arr[j] < arr[index])
{
index = j ;
}
}
if (index != i)
{
Swap(&arr[i], &arr[index]);
}
}
}
選擇排序的小優(yōu)化：
基本思想：上面的思路是每一趟確定一個數(shù)，那能不能一趟確定兩個數(shù)呢？
老規(guī)矩先考慮某一趟的代碼編寫：
上面的代碼對于大部分情況是可以完成排序的。但是對于一些情況是有問題的。
例如：
為了出現(xiàn)這種情況，所以必須加個判斷語句。
完整代碼：
//選擇排序
void SelectSort(int* arr, int n)
{
int beg = 0, end = n - 1;
while (beg < end)
{
//找出最大、最小的下標(biāo)
int maxi = beg;
int mini = beg;
for (int i = beg; i <= end; i++)
{
if (arr[i] < arr[mini])
{
mini = i;
}
if (arr[i] > arr[maxi])
{
maxi = i;
}
}
Swap(&arr[beg], &arr[mini]);
if (maxi == beg)
{
maxi = mini;
}
Swap(&arr[end], &arr[maxi]);
beg++;
end--;
}
}
3.2選擇排序的特點(diǎn)
選擇排序的特點(diǎn)：
-
1.選擇排序思考非常好理解，但是效率不是很好(不論數(shù)組是否有序都會執(zhí)行原步驟)。實(shí)際中很少使用
-
2.時間復(fù)雜度：O(N^2)（最好和最壞的情況下時間復(fù)雜度都是一樣）
-
3.空間復(fù)雜度：O(1)
-
4.穩(wěn)定性：不穩(wěn)定
-
4.冒泡排序
4.1冒泡排序的思想
基本思想：
一趟過程中，前后兩個數(shù)依次比較，將較大的數(shù)字往后推，下一次只需要比較剩下的n-1個數(shù)，如此往復(fù)。
動態(tài)圖展示：
怎么編寫冒泡排序的代碼呢？咱們還是先把問題簡單化，先考慮一趟冒泡排序的代碼編寫。
第一趟冒泡排序的編寫：
怎么進(jìn)行多趟的冒泡排序呢？
只需要控制i的最終大小即可。
當(dāng)一趟循環(huán)下來i=n-2時，可以保證arr[n-1]的值是最大的；
當(dāng)一趟循環(huán)下來i=n-3時，可以保證arr[n-2]的值是次大的；
當(dāng)一趟循環(huán)下來i=n-4時，可以保證arr[n-3]的值是次次大的；
…
所以只需要在嵌套一層循環(huán)即可。
完整代碼：
//冒泡排序
void BubbleSort(int* arr, int n)
{
for (int j = 0; j < n-1 ; j++)
{
for (int i = 0; i < n -1- j; i++)
{
if (arr[i] > arr[i+1])
{
Swap(&arr[i], &arr[i+1]);
}
}
}
}
小伙伴到這是不是以為冒泡排序結(jié)束了？嘿嘿，其實(shí)還沒有。不知道大家考慮過這樣的情況過嗎？
如下圖：
答案是還要進(jìn)行。這就是上面的冒泡排序缺點(diǎn)。
冒泡排序的小優(yōu)化：
基本思想：
為了讓冒泡排序知道數(shù)組數(shù)組是否有序，可以定義一個變量flag。當(dāng)flag=1時，默認(rèn)數(shù)組是無序的。當(dāng)flag=0時，認(rèn)為數(shù)組是有序的。
優(yōu)化后的完整代碼：
//冒泡排序
void BubbleSort(int* arr, int n)
{
int flag = 1;
for (int j = 0; j < n&&flag==1; j++)
{
flag = 0;
for (int i = 1; i < n-j; i++)
{
if (arr[i-1] > arr[i])
{
Swap(&arr[i - 1], &arr[i]);
flag = 1;
}
}
}
}
4.2冒泡排序的特點(diǎn)
特點(diǎn)：
- 非常容易理解的排序
- 時間復(fù)雜度:O(N^2)
- 空間復(fù)雜度:O(1)
- 穩(wěn)定性：穩(wěn)定
5.快速排序
5.1快速排序的思想
5.1快速排序（遞歸）
基本思想：
乍一看這個排序?qū)懫饋砗翢o思路，所以我們一步一步看問題，一步一步解決問題。
先考慮第一個問題：將數(shù)組中第一個數(shù)放在正確的位置。
5.1.1快速排序（遞歸-Hoare）
第一個問題的基本思想：
第一個問題的基本步驟：
1、選出一個keyi，一般是最左邊或是最右邊的。
2、定義一個L和一個R，L從左向右走，R從右向左走。（需要注意的是：若選擇最左邊的數(shù)據(jù)作為key，則需要R先走；若選擇最右邊的數(shù)據(jù)作為keyi，則需要L先走）。
3、在走的過程中，若R遇到小于arr[keyi]的數(shù)，則停下，L開始走，直到L遇到一個大于arr[keyi]的數(shù)時，將L和R的內(nèi)容交換，R再次開始走，如此進(jìn)行下去，直到L和R最終相遇，此時將相遇點(diǎn)的內(nèi)容與arr[keyi]交換即可。（選取最左邊的值作為keyi）
經(jīng)過一次單趟排序，最終使得key左邊的數(shù)據(jù)全部都小于arr[keyi]，key右邊的數(shù)據(jù)全部都大于arr[keyi]。
為什么要注意誰先走呢？以左值為keyi舉例說明：
第一個問題的動態(tài)圖演示（Hoare）：
代碼(Hoare)：
//一趟快速排序
int Partion(int* arr, int left, int right)
{
assert(arr);
int keyi = left;
while (left < right)
{
//左邊是key值，讓右邊先走
//右邊找小
while (left < right && arr[right] >= arr[keyi])
{
right--;
}
//左邊再走
//左邊找大
while (left < right && arr[left] <= arr[keyi])
{
left++;
}
Swap(&arr[left], &arr[right]);
}
Swap(&arr[left], &arr[keyi]);
return left;
}
5.1.2快速排序（遞歸-挖坑法）
第一個問題的動態(tài)圖演示（挖坑法）：
代碼(挖坑法)：
//一趟快速排序(挖坑法)
int Partion2(int* arr, int left, int right)
{
int key = arr[left];
int pivot = left;
while (left < right)
{
//右邊先走，找小
while (left < right && arr[right] >= key)
{
right--;
}
arr[pivot] = arr[right];
pivot = right;
//左邊再走，找大
while (left < right && arr[left] <= key)
{
left++;
}
arr[pivot] = arr[left];
pivot = left;
}
arr[pivot] = key;
return pivot;
}
5.1.3快速排序（遞歸-前后指針）
第一個問題的動態(tài)圖演示（前后指針）：
代碼（前后指針）：
//一趟快速排序(前后指針)
int Partion3(int* arr, int left, int right)
{
assert(arr);
int pre = left;
int cur = pre + 1;
int keyi = left;
while (cur <= right)
{
if (arr[cur] < arr[keyi])
{
Swap(&arr[cur], &arr[++pre]);
}
cur++;
}
Swap(&arr[pre], &arr[keyi]);
return pre;
}
第二個問題與第三個問題：
快速排序遞歸版代碼（Hoare）：
//一趟快速排序
int Partion(int* arr, int left, int right)
{
assert(arr);
int keyi = left;
while (left < right)
{
//左邊是key值，讓右邊先走
//右邊找小
while (left < right && arr[right] >= arr[keyi])
{
right--;
}
//左邊找大
while (left < right && arr[left] <= arr[keyi])
{
left++;
}
Swap(&arr[left], &arr[right]);
}
Swap(&arr[left], &arr[keyi]);
return left;
}
//快速排序
void QuickSort(int* arr, int left, int right)
{
assert(arr);
if (left >= right)
{
return;
}
int keyi = Partion(arr, left, right);
QuickSort(arr, left, keyi - 1);
QuickSort(arr, keyi+1, right);
}
當(dāng)待排序的數(shù)組內(nèi)的值都是同一個值且數(shù)量很多時遞歸版快速排序容易出現(xiàn)棧溢出的情況，為了優(yōu)化這一現(xiàn)象就有了非遞歸版快速排序。
快速排序的非遞歸算法基本思路：
?1、先將待排序列的第一個元素的下標(biāo)和最后一個元素的下標(biāo)入棧。
?2、當(dāng)棧不為空時，讀取棧中的信息（一次讀取兩個：一個是L，另一個是R），然后調(diào)用某一版本的單趟排序，排完后獲得了key的下標(biāo)，然后判斷key的左序列和右序列是否還需要排序，若還需要排序，就將相應(yīng)序列的L和R入棧；若不需排序了（序列只有一個元素或是不存在），就不需要將該序列的信息入棧。
?3、反復(fù)執(zhí)行步驟2，直到棧為空為止。
圖示：
5.2快速排序（非遞歸）
快速排序非遞歸代碼：
/快速排序（非遞歸）
void QuickSortNonR(int* arr, int left, int right)
{
assert(arr);
Stack ST;
Init_Stack(&ST);
Push_Stack(&ST, left);
Push_Stack(&ST, right);
while (!IsEmpty(&ST))
{
int end = Top_Stack(&ST);
Pop_Stack(&ST);
int begin = Top_Stack(&ST);
Pop_Stack(&ST);
//[begin,keyi-1] keyi [keyi+1,end]
int keyi=Partion1(arr, begin, end);
if (keyi + 1 < end)
{
Push_Stack(&ST, keyi + 1);
Push_Stack(&ST, end);
}
if (begin < keyi - 1)
{
Push_Stack(&ST, begin);
Push_Stack(&ST, keyi - 1);
}
}
Destroy_Stack(&ST);
}
5.3快速排序的特點(diǎn)
1.快速排序很怪，為什么呢？這個排序排亂序的數(shù)組賊快，但是排有序數(shù)組慢的離譜。
比如：
為了避免最壞情況的發(fā)生，做了個三數(shù)取中的小優(yōu)化
優(yōu)化代碼：
//三數(shù)取中
int GetMidIndex(int* arr, int left, int right)
{
//int mid = (left + right) / 2;
int mid = left + (right - left) / 2;
if (arr[left] < arr[mid])
{
if (arr[mid] < arr[right])
{
return mid;
}
//arr[left]<arr[mid] arr[mid]>arr[right]
else if (arr[right] < arr[left])
{
return left;
}
else
{
return right;
}
}
//arr[left] > arr[mid]
else
{
if (arr[mid] > arr[right])
{
return mid;
}
///arr[left] > arr[mid] arr[mid] < arr[right]
else if (arr[left]>arr[right])
{
return right;
}
else
{
return left;
}
}
return 1;
}
//一趟快速排序(Hoare)
int Partion1(int* arr, int left, int right)
{
assert(arr);
int keyi = left;
while (left < right)
{
//左邊是key值，讓右邊先走
//右邊找小
while (left < right && arr[right] >= arr[keyi])
{
right--;
}
//左邊找大
while (left < right && arr[left] <= arr[keyi])
{
left++;
}
Swap(&arr[left], &arr[right]);
}
Swap(&arr[left], &arr[keyi]);
return left;
}
//快速排序
void QuickSort(int* arr, int left, int right)
{
assert(arr);
int midi = GetMidIndex(arr, left, right);
Swap(&arr[midi], &arr[left]);
if (left >= right)
{
return;
}
int keyi = Partion2(arr, left, right);
QuickSort(arr, left, keyi - 1);
QuickSort(arr, keyi+1, right);
}
通過這樣的優(yōu)化如果快速排序遇到最壞情況，那么最壞情況直接變成最好情況。
- 快排的時間復(fù)雜度： O(N*logN)
- 空間復(fù)雜度： O(logN)
- 穩(wěn)定性：不穩(wěn)定
快速排序不穩(wěn)定說明（圖示）：
6.堆排序
6.1堆排序的思想
基本思想：
上面排序的思想已經(jīng)大致清楚了，那么怎么建堆呢？怎么把一個數(shù)組建成堆呢？
思路1：將數(shù)組中從第二個元素開始利用向上調(diào)整函數(shù)建堆。
向上調(diào)整代碼：
//向上調(diào)整
void AjustUp(HeapDateType* arr, int child)
{
assert(arr);
int parent = (child - 1) / 2;
while (child > 0)
{
//大于號是大堆，小于號是小堆
if (arr[child] > arr[parent])
{
Swap(&arr[parent], &arr[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//構(gòu)建大堆
//方法1
for (int i = 1; i < n; i++)
{
AjustUp(a, i);
}
思路2：將數(shù)組中從倒數(shù)第一個非葉子節(jié)點(diǎn)開始利用向下調(diào)整函數(shù)建堆。
向下調(diào)整代碼：
//向下調(diào)整
void AjustDown(HeapDateType* arr, int len, int parent)
{
assert(arr);
int child = parent * 2 + 1;
while (child < len)
{
//大于號是大堆，小于號是小堆
if (child + 1 < len && arr[child + 1] > arr[child])
{
child++;
}
//大于號是大堆，小于號是小堆
if (arr[child] > arr[parent])
{
Swap(&arr[parent], &arr[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//方法2
//n-1是最后一個葉子節(jié)點(diǎn) (n-1-1)/2是最后一個葉子節(jié)點(diǎn)的父親節(jié)點(diǎn)
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AjustDown(a, n, i);
}
堆排序代碼：
void HeapSort(int* a, int n)
{
assert(a);
//構(gòu)建大堆
//方法1
//for (int i = 1; i < n; i++)
//{
// AjustUp(a, i);
//} //方法2
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AjustDown(a, n, i);
}
for (int end = n - 1; end > 0; end--)
{
Swap(&a[end], &a[0]);
AjustDown(a, end, 0);
}
}
6.2堆排序的特點(diǎn)
- 時間復(fù)雜度：O（N*logN）
- 空間復(fù)雜度：O(1)
- 穩(wěn)定性：不穩(wěn)定
7.歸并排序
7.1歸并排序（遞歸）
歸并排序（遞歸）的思想
歸并排序是采用分治法的一個非常典型的應(yīng)用。其基本思想是：將已有序的子序合并，從而得到完全有序的序列，即先使每個子序有序，再使子序列段間有序。
將兩個有序的數(shù)組歸并成一個有序數(shù)組動態(tài)圖：
遞歸版歸并排序：
上面的圖示其實(shí)已經(jīng)可以看出有了寫遞歸的影子了。想要對一個數(shù)組進(jìn)行排序，就需要兩個有序的子數(shù)組來歸并，而這兩個子數(shù)組想要有序也需要其自身的兩個有序子數(shù)組來歸并,就這樣套娃模式就開始了，對付套娃還得是遞歸才行。
遞歸版歸并排序?qū)懘a前分析：
遞歸版歸并排序代碼：
void _MergeSort(int* arr, int left, int right, int* temp)
{
if (left >= right)
{
return;
}
int mid = (left + right) / 2;
//遞歸
_MergeSort(arr, left, mid, temp);
_MergeSort(arr, mid+1, right, temp);
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int i = left;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
{
temp[i++] = arr[begin1++];
}
else
{
temp[i++] = arr[begin2++];
}
}
while (begin1 <= end1)
{
temp[i++] = arr[begin1++];
}
while (begin2 <= end2)
{
temp[i++] = arr[begin2++];
}
for (int i = left; i <= right; i++)
{
arr[i] = temp[i];
}
}
//歸并排序
void MergeSort(int* arr, int n)
{
assert(arr);
int* temp = (int*)malloc(sizeof(int) * n);
if (temp == NULL)
{
perror("MergeSort::malloc");
return;
}
_MergeSort(arr, 0, n - 1, temp);
free(temp);
temp = NULL;
}
7.2歸并排序（非遞歸）
在上面我們知道快速排序有遞歸版與非遞歸版，那么歸并排序有非遞歸嗎？因?yàn)檫f歸的缺點(diǎn)還是很明顯的，在有非遞歸下最好還是使用非遞歸。其實(shí)是有非遞歸的歸并排序的。但是這個寫法需要注意的東西很多，直接上代碼很容易看懵，所以且讓我慢慢道來。
歸并排序（非遞歸）的基本思想（圖示）：
理想情況下的代碼：
//歸并排序（非遞歸）
void MergeSortNonR(int* arr, int n)
{
assert(arr);
int gap = 1;
int* temp = (int*)malloc(sizeof(int) * n);
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;
int j = begin1;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
{
temp[j++] = arr[begin1++];
}
else
{
temp[j++] = arr[begin2++];
}
}
while (begin1<=end1)
{
temp[j++] = arr[begin1++];
}
while (begin2<=end2)
{
temp[j++] = arr[begin2++];
}
}
for (int j = 0; j <n; j++)
{
arr[j] = temp[j];
}
gap *= 2;
}
free(temp);
}
那怎在非理想進(jìn)行非遞歸歸并排序呢？首先就要考慮非理想情況下與理想情況下的差別有哪些。
我們仔細(xì)觀察會發(fā)現(xiàn)理想情況下的begin1、end1、begin2、end2是不會出現(xiàn)越界的，而非理想情況下end1、begin2、end2是會出現(xiàn)越界的。
所以只需要對這三種情況分別處理下就好了
第一種修正方式圖示：
非遞歸歸并排序代碼（第一種）：
/歸并排序（非遞歸）
void MergeSortNonR(int* arr, int n)
{
assert(arr);
int gap = 1;
int* temp = (int*)malloc(sizeof(int) * n);
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;
int j = begin1;
//printf("[%d,%d] [%d,%d] ", begin1, end1, begin2, end2);
//end1、begin2、end2越界
if (end1 >= n)
{
end1 = n - 1;
}
//begin2、end2越界不進(jìn)行歸并
if (begin2 >= n)
{
begin2 = n;
end2 = n - 1;
}
if (end2 >= n)
{
end2 = n - 1;
}
//printf("[%d,%d] [%d,%d] ", begin1, end1, begin2, end2);
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
{
temp[j++] = arr[begin1++];
}
else
{
temp[j++] = arr[begin2++];
}
}
while (begin1<=end1)
{
temp[j++] = arr[begin1++];
}
while (begin2<=end2)
{
temp[j++] = arr[begin2++];
}
}
for (int j = 0; j <n; j++)
{
arr[j] = temp[j];
}
gap *= 2;
//printf("\n");
}
free(temp);
}
第二種修正方式：
非遞歸歸并排序代碼（第二種）：文章來源：http://www.zghlxwxcb.cn/news/detail-432448.html
//歸并排序（非遞歸）法2
void MergeSortNonR(int* arr, int n)
{
assert(arr);
int gap = 1;
int* temp = (int*)malloc(sizeof(int) * n);
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;
int j = begin1;
//end1或者begin2越界
if (end1 >= n||begin2>=n)
{
break;
}
//end2越界
if (end2 >= n)
{
end2 = n - 1;
}
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
{
temp[j++] = arr[begin1++];
}
else
{
temp[j++] = arr[begin2++];
}
}
while (begin1 <= end1)
{
temp[j++] = arr[begin1++];
}
while (begin2 <= end2)
{
temp[j++] = arr[begin2++];
}
for (int j = i; j <=end2; j++)
{
arr[j] = temp[j];
}
}
gap *= 2;
}
free(temp);
}
7.2歸并排序的特點(diǎn)
- 1.時間復(fù)雜度：O(N*logN)
- 2.空間復(fù)雜度：O(N)
- 3.穩(wěn)定性：不穩(wěn)定
8.計數(shù)排序
8.1計數(shù)排序的思想
圖示：
文章來源地址http://www.zghlxwxcb.cn/news/detail-432448.html
//計數(shù)排序
void CountSort(int* arr,int n)
{
assert(arr);
int max = arr[0], min = arr[0];
//找出最大、最小數(shù)
for (int i = 0; i < n; i++)
{
arr[i] = arr[i];
if (arr[i] < min)
{
min = arr[i];
}
if (arr[i] > max)
{
max = arr[i];
}
}
int rang = max - min + 1;
int* temp = (int*)malloc(sizeof(int) * rang);
//初始化temp數(shù)組
memset(temp, 0, sizeof(int) * rang);
//開始在temp數(shù)組里計數(shù)
for (int i = 0; i < n; i++)
{
temp[arr[i] - min]++;
}
//排序arr
int j = 0;
for (int i = 0; i < rang; i++)
{
while (temp[i])
{
arr[j++] = i + min;
temp[i]--;
}
}
free(temp);
}
8.2計數(shù)排序的特點(diǎn)
- 1.計數(shù)排序只適用于數(shù)據(jù)范圍較集中的序列的排序，若待排序列的數(shù)據(jù)較分散，則會造成空間浪費(fèi)，并且計數(shù)排序只適用于整型排序，不適用與浮點(diǎn)型排序。
- 2.時間復(fù)雜度：O(N+range)
- 3.空間復(fù)雜度：O(range)
- 4.穩(wěn)定性：不穩(wěn)定
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)--八大排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
