插入排序
直接插入排序
直接插入排序是一種簡單的插入排序法，其基本思想:是把待排序的記錄按其關(guān)鍵碼值的大小逐個插入到一個已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列
可以理解為一遍摸撲克牌，一邊進行排序
在待排序的元素中，假設(shè)前面n-1(其中n>=2)個數(shù)已經(jīng)是排好順序的，現(xiàn)將第n個數(shù)插到前面已經(jīng)排好的序列中，然后找到合適自己的位置，使得插入第n個數(shù)的這個序列也是排好順序的。
按照此法對所有元素進行插入，直到整個序列排為有序的過程，稱為插入排序
- 當插入第n個元素時，前面的n-1個數(shù)已經(jīng)有序
- 用第n個數(shù)與前面的n-1個數(shù)比較，我們將第n個數(shù)假設(shè)為tmp ,也就是說將tmp插入到[0 ,end] 的區(qū)間中
第一種情況：如果tmp比end大就放在end后面
第二種情況：如果tmp比end小但是比數(shù)組前面的幾個數(shù)據(jù)大,插入之后，tmp之后的數(shù)據(jù)就往后挪動
第三種情況：如果tmp比數(shù)組所有元素都小,所有數(shù)據(jù)都需要挪動,end就得挪動到數(shù)組下標為-1的位置才結(jié)束
動圖演示：
void InsertSort(int* a , int n )
{
for (int i = 1; i <n ; i++)
{
//一趟插入排序
int tmp = a[i];
int end = i-1; //end是數(shù)組下標
while (end >= 0)
{
//如果tmp比end小但是比數(shù)組前面的幾個數(shù)據(jù)大,插入之后，tmp之后的數(shù)據(jù)就往后挪動
if (tmp < a[end])
{
a[end + 1] = a[end];//往后挪動
end--;
}
else
{
break;
}
}
//如果tmp比數(shù)組所有元素都小,所有數(shù)據(jù)都需要挪動,end就得挪動到數(shù)組下標為-1的位置才結(jié)束
//如果tmp比end大就放在end后面
a[end + 1] = tmp;//包含上述兩種情況
}
}
時間復雜度：O(N^2)
空間復雜度：O(1)
希爾排序
第一步先選定個小于n的數(shù)字作為gap，將所有距離為gap的數(shù)分為一組進行預排序,預排序的目的就是使數(shù)組接近有序，與直接插入排序相同，直接插入排序的間隔為1，預排序的間隔變?yōu)間ap了
再選一個小于gap的數(shù)作為新的gap，重復第一步的操作
當gap的大小減到1時，就相當于整個序列被分到一組，進行一次直接插入排序，排序完成
舉例分析一下:
我們用序列長度的一半作為第一次排序時gap的值，此時相隔距離為5的元素被分為一組（共分了5組，每組有2個元素），然后分別對每一組進行直接插入排序
gap的值折半，此時相隔距離為2的元素被分為一組（共分了2組，每組有5個元素），然后再分別對每一組進行直接插入排序
gap的值再次減半，此時gap減為1，即整個序列被分為一組，進行一次直接插入排序。
為什么是選一個小于gap的數(shù)作為新的gap，也就是要gap由大變小？
gap越大，數(shù)據(jù)跳躍的幅度越大，數(shù)據(jù)挪動得越快；gap越小，數(shù)據(jù)跳躍的幅度越小，數(shù)據(jù)挪動得越慢。前期讓gap較大，可以讓數(shù)據(jù)更快得移動到自己對應的位置附近，減少挪動次數(shù),提高算法效率
void ShellSort(int* a, int n) // 希爾排序
{
int gap = n;
while (gap > 1)
{
//一趟排序
gap /= 2;
for (int i = gap; i < n; i += gap)
{
int end = i - gap; //有序序列最后一個元素的下標
int tmp = a[end + gap];
while (end >= 0)
{
//如果tmp比end小但是比數(shù)組前面的幾個數(shù)據(jù)大,插入之后，tmp之后的數(shù)據(jù)就往后挪動
if (tmp < a[end])
{
a[end + gap] = a[end]; //往后挪動
end -= gap;
}
else
{
break;
}
}
//tmp比數(shù)組中所有數(shù)據(jù)都小 ,一直往后挪動 ，end挪到了-1
//tmp >a[end]
a[end + gap] = tmp;
}
}
}
選擇排序
選擇排序
基本思想 : 每一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素，存放在序列的起始位置；直到全部待排序的數(shù)據(jù)元素排完
在元素集合array[i]到array[n-1]中選擇關(guān)鍵碼最大(小)的數(shù)據(jù)元素；
若它不是這組元素中的最后一個(第一個)元素，則將它與這組元素中的最后一個（第一個）元素交換；
在剩余的array[i] 到 array[n-2]（array[i+1]–array[n-1]）集合中，重復上述步驟，直到集合剩余1個元素
注意特殊情況 ：如果Maxi在left位置，當a [ Mini ] 和 a [ left ] 互換時，此時Maxi的位置就變成了Mini， 我們添加一個判斷條件 ，判斷l(xiāng)eft == Maxi ， 修正Maxi ，防止Maxi更改
以升序為例做分析：
經(jīng)過第一躺交換，最小的元素排在了數(shù)組的第一個位置
經(jīng)過第二趟交換 ，第二小的元素已經(jīng)到了數(shù)組第二個元素位置
經(jīng)過第三趟排序 ，第三小的元素已經(jīng)排在了第三個位置
最后一趟排序 ，數(shù)組已經(jīng)有序了
動圖演示 ：
代碼實現(xiàn)：
void SelectSort(int* a, int n)//選擇排序
{
//升序
int left = 0, right = n - 1;
while (left < right)
{
//選出最大最小數(shù)的下標
int Mini = left;
int Maxi = left;
//一趟
for (int i = left+1 ; i <= right; i++)
{
if (a[i] < a[Mini])
{
Mini = i; // 更新Mini
}
if (a[i] > a[Maxi])
{
Maxi = i; //更新Maxi
}
}
// Mini和左邊交換
Swap(&a[left], &a[Mini]);
// Maxi 在左邊 ，Maxi 被換成Mini， 修正Maxi
if (left == Maxi)
{
Maxi = Mini;
}
//Maxi與右邊交換
Swap(&a[right], &a[Maxi]);
left++;
right--;
}
}
選擇排序效率較低,實際中很少使用
時間復雜度：O(N^2)
空間復雜度：O(1)
穩(wěn)定性：不穩(wěn)定
堆排序
排降序 建立小堆
排升序 建立大堆
升序
向上調(diào)整建堆,時間復雜度為O(N* longN)
使用向上調(diào)整算法建大堆，將數(shù)組建成大堆后,此時堆頂元素是最大的 ，將堆頂元素和最后一個元素進行交換,這樣最大的元素就到了數(shù)組最后一個元素,對剩下的元素使用向下調(diào)整 ， 當下一次向下調(diào)整時，我們不管這個處在數(shù)組最后一個位置的最大元素（有點類似堆的刪除 ），此時第二大的元素來到的堆頂 ，堆頂元素繼續(xù)與最后一個元素進行交換，（注意第一個交換過去的最大的元素已經(jīng)不在范圍內(nèi)了） ，依次類推 ，升序就完成了
void HeapSort(int* a, int n)
{
//向上調(diào)整建堆
for (int i = 0; i < n; i++)
{
AdjustUp(a, i);
}
//向下調(diào)整排序
int end = n - 1;// end 是最后一個元素的下標
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
end--;
}
}
int main()
{
int a[10] = { 2, 1, 5, 7, 6, 8, 0, 9, 4, 3 };
HeapSort(a, 10);
return 0;
}
向下調(diào)整建堆的前提是左右子樹都是堆 ，從倒數(shù)第一個非葉子節(jié)點開始倒著調(diào)整,如何找到倒數(shù)第一個非葉子節(jié)點？通過最后一個節(jié)點的父節(jié)點來找到 , 那為什么要找倒數(shù)第一個非葉子節(jié)點？ 因為倒數(shù)第一個非葉子節(jié)點的左右子樹都滿足大堆或小堆的條件
void HeapSort(int* a, int n)
{
//向下調(diào)整建堆
for (int i = (n-1-1)/ 2; i >= 0; i--) // n-1是最后一個節(jié)點的下標，（n-1-1)/2 通過下標找到最后一個節(jié)點的父節(jié)點
{
AdjustDown(a,n , i);
}
//向下調(diào)整排序
int end = n - 1; //end 是最后一個元素的下標
while (end >=0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
end--;
}
}
int main()
{
int a[10] = { 2, 1, 5, 7, 6, 8, 0, 9, 4, 3 };
HeapSort(a, 10);
return 0;
}
交換排序
冒泡排序
以升序為例
冒泡排序，該排序的命名非常形象，即一個個將氣泡冒出。冒泡排序一趟冒出一個最大（或最?。┲?br> 如果前一位的數(shù)字大于后一位的，那么這兩個數(shù)字交換位置，因此，最大的數(shù)字在第一輪循環(huán)中不斷像一個氣泡一樣向上冒
動圖演示：
代碼實現(xiàn) :
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n-1; i++)
{
//一趟
for (int j = 0; j < n-1 - i; j++)
{
assert(j < n-1);
if (a[j] > a[j + 1])
{
assert(j + 1 < n);
Swap(&a[j], &a[j + 1]);
}
}
}
}
如果一趟排序沒有交換就說明已經(jīng)有序了，不用再進行比較了
冒泡排序：
時間復雜度 ：O(N^2)
快速排序
遞歸
hoare版本
快速排序是Hoare于1962年提出的一種二叉樹結(jié)構(gòu)的交換排序方法，其基本思想為：任取待排序元素序列中的某元素作為基準值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后最左右子序列重復該過程，直到所有元素都排列在相應位置上為止。
單趟排序 ： 一趟下來的結(jié)果是讓Key左邊的數(shù)據(jù)全部都小于Key，Key右邊的數(shù)據(jù)全部都大于Key， 就相當于Key這個基準值被排好序了，快速排序的單趟排序本質(zhì)上就是在排一個數(shù)的順序
步驟：
1 選最左邊的或者最右邊的當作基準值Key
2 定義一個Left和一個Right，Right從右向左走, 若Right遇到小于Keyi的數(shù)，則停下,Left從左向右開始走，直到Left遇到一個大于Keyi的數(shù)時，將Left和Right的內(nèi)容交換 ，Right再次開始走，如此進行下去，直到Left和Right最終相遇，此時將相遇點的內(nèi)容與key交換即可
（需要注意的是：若選擇最左邊的數(shù)據(jù)作為基準值Key，則需要Right先走；若選擇最右邊的基準值數(shù)據(jù)作為基準值Key，則需要Left先走）
注意：Left 和Right相遇位置一定比Key小
3 然后我們再將Key的左序列和右序列再次進行這種單趟排序，如此反復操作下去 ，其實就是一個遞歸
如果選擇最左邊的數(shù)據(jù)作為基準值Key ,為什么不能Left先走呢？
快排hoare版本 單趟動圖演示：
代碼實現(xiàn)：
void QuickSort(int* a, int left , int right ) // Hoare 版本
{
int begin = left;
int end = right;
//升序
// 從左向右走 , 從右向左走
int Keyi = left; // 最左邊為基準值
if (left >= right)
return;
while (left <right )
{
//單趟排序
//右邊找小
while (right > left && a[right] >= a[Keyi])
{
right--;
assert(right > 0);
}
//左邊找大
while (left < right && a[left] <= a[Keyi])
{
left++;
assert(left <= right);
}
Swap(&a[left], &a[right]);
}
Swap(&a[Keyi], &a[left]); //Left和Right最終相遇，此時將相遇點的內(nèi)容與key交換即可
//遞歸 類似二叉樹的前序遍歷
// [begin , Keyi-1 ] Keyi [Keyi+1 , end]
Keyi = left;
assert(Keyi - 1 >= 0);
QuickSort( a, begin, Keyi -1);
QuickSort(a, Keyi+1, end );
}
快排時間復雜度 ：
如果每趟排序所選的Key都正好是該序列的中間值，即單趟排序結(jié)束后Key位于序列正中間，那么快速排序的時間復雜度就是O(NlogN)
挖坑法
以升序為例
單趟排序：一趟下來的結(jié)果是讓Key左邊的數(shù)據(jù)全部都小于Key，Key右邊的數(shù)據(jù)全部都大于Key
步驟(在最左邊挖坑為例） ：
1 選出最左邊或者最右邊的一個數(shù) ,存放在Key變量中，并且在該數(shù)據(jù)位置形成一個坑
2 定義一個Left和一個Right，Left從左向右走，找比Key大的數(shù) ，Right從右向左走，找比Key小的數(shù)。（注意： 如果是在最左邊挖坑，則需要Right先走；如果是在最右邊挖坑，則需要Left先走）
3 因為是以最左邊挖坑為例 ,所以是Right 先走 , 在Left和Right 遍歷的過程中,如果Right遇到小于Key的數(shù)，則將該數(shù)放到最左邊的坑位，并在Right當前位置形成新的坑位，這時Left再向右邊走，若遇到大于Key的數(shù)，則將其拋入到剛才在Right位置形成的一個坑位，然后在Left 當前位置形成一個坑位，如此循環(huán)下去，直到最終Left和Right相遇，而且Left和Right相遇一定相遇在坑位處 ,這時將Key填在坑位即可。
Key的左序列和右序列再次進行這種單趟排序，如此反復操作下去，直到左右序列只有一個數(shù)據(jù)，或是左右序列不存在時，便停止操作
單趟動圖演示：
代碼實現(xiàn)：
//快排挖坑法
void QuickSort(int* a, int left, int right)
{
int begin = left;
int end = right;
if (left >= right)
return;
// 升序 ，最左邊挖坑 ，右邊先走
//選最左邊為 Key,并形成hole
int hole=left;
int Key = a[left];
while (left < right)
{
//單趟排序
//right 找小
while (left < right && a[right] > Key)
{
right--;
}
//找到比Key小的數(shù) ，放進最左邊的坑位 ，并在right當前位置形成新的坑位
a[hole] = a[right];
hole = right;
assert(hole >= 0);
//left 找 大
while (right > left && a[left] < Key)
{
left++;
}
// 找到比Key大的數(shù) ，放進right當時形成的坑位 ，并在Left當前位置形成新的坑位
a[hole] = a[left];
hole = left;
assert(hole >= 0);
}
//直到最終Left和Right相遇，這時將Key填在坑位即可。
assert(hole >= 0);
a[hole] = Key;
//遞歸
//遞歸 類似二叉樹的前序遍歷
// [begin , Key-1 ] Key [Key+1 , end]
Key = left;
assert(Key - 1 >= 0);
QuickSort( a, begin, Key -1);
QuickSort(a, Key+1, end );
}
前后指針版本
以升序為例
單趟排序：一趟下來的結(jié)果是讓Key左邊的數(shù)據(jù)全部都小于Key，Key右邊的數(shù)據(jù)全部都大于Key
步驟(以最左邊為Key 為例） ：
1 選最左邊的或者最右邊的當作基準值Key
2 定義一個prev 和 cur ，prev指針指向序列開頭 ，prev 從左往右遍歷 ,cur指針指向prev+1, cur從左往右遍歷 。
3、若cur指向的內(nèi)容小于Key，則prev先++，然后交換prev和cur的值，然后cur++；若cur的值大于key，則cur指針直接++。如此進行下去，直到cur指針越界，此時將Key和prev指針指向的內(nèi)容交換即可。
然后我們再將Key的左序列和右序列再次進行這種單趟排序，如此反復操作下去 ，其實就是一個遞歸
單趟動圖演示：
代碼實現(xiàn)：
int PartSort2(int* a, int left, int right) //前后指針法
{
int begin = left;
int end = right;
//升序
// 單趟排序
int prev = left;
int cur = prev + 1;
int Keyi = left; //選最左邊為Key
//cur 找比Key小的
while (cur <= right) //cur未越界就繼續(xù)
{
//如果cur找到比Key小 ，往后++
if (a[cur] < a[Keyi] && ++prev != cur) //++prev !=cur , 有可能數(shù)組前幾個元素比Key小，但是沒必要交換
{
Swap(&a[cur], &a[prev]); //交換
}
cur++;
}
assert(cur <= right+1);
Swap(&a[prev], &a[Keyi]);
/*遞歸 類似二叉樹的前序遍歷
[begin , Keyi-1 ] Keyi [Keyi+1 , end] */
Keyi = prev;
assert(Keyi - 1 >= 0);
return prev;
}
void QuickSort(int* a, int left, int right)
{
//遞歸
if (left >= right)
return;
int keyi = PartSort2(a, left, right);
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
非遞歸
將一個用遞歸實現(xiàn)的算法改為非遞歸時，一般需要借用一個數(shù)據(jù)結(jié)構(gòu)，那就是棧。將Hoare版本、挖坑法以及前后指針法的快速排序改為非遞歸版本
Hoare版本、挖坑法和前后指針法 ，這三種排序都只寫單趟 ，后面再寫一個非遞歸的快速排序，在函數(shù)內(nèi)部調(diào)用單趟排序的函數(shù)
Hoare
單趟排序代碼實現(xiàn)：
//Hoare版本（單趟排序）
int PartSort1(int* a, int left, int right)
{
int keyi = left;//key的下標
while (left < right)
{
//right走，找小
while (left < right&&a[right] >= a[keyi])
{
right--;
}
//left先走，找大
while (left < right&&a[left] <= a[keyi])
{
left++;
}
if (left < right)
{
Swap(&a[left], &a[right]);//交換left和right的值
}
}
int meeti = left;//L和R的相遇點
Swap(&a[keyi], &a[meeti]);//交換key和相遇點的值
return meeti;//返回相遇點，即key的當前位置
}
挖坑法
單趟排序代碼實現(xiàn)：
//挖坑法（單趟排序）
int PartSort2(int* a, int left, int right)
{
int key = a[left];//在最左邊形成一個坑位
while (left < right)
{
//right向左，找小
while (left < right&&a[right] >= key)
{
right--;
}
//填坑
a[left] = a[right];
//left向右，找大
while (left < right&&a[left] <= key)
{
left++;
}
//填坑
a[right] = a[left];
}
int meeti = left;//L和R的相遇點
a[meeti] = key;//將key拋入坑位
return meeti;//返回key的當前位置
}
前后指針
單趟排序代碼實現(xiàn)：
//前后指針法（單趟排序）
int PartSort3(int* a, int left, int right)
{
int prev = left;
int cur = left + 1;
int keyi = left;
while (cur <= right)//當cur未越界時繼續(xù)
{
if (a[cur] < a[keyi] && ++prev != cur)//cur指向的內(nèi)容小于key
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
int meeti = prev;//cur越界時，prev的位置
Swap(&a[keyi], &a[meeti]);//交換key和prev指針指向的內(nèi)容
return meeti;//返回key的當前位置
}
快排的優(yōu)化
三數(shù)取中法選key
如果這個序列是非常無序，快速排序的效率是非常高的 ,一旦序列有序 ，每次選取最左邊或是最右邊的數(shù)作為基準值Key，時間復雜度就會從O(N*logN)變?yōu)镺(N^2),這樣快排的效率極低
也就是說影響快排時間復雜度就是基準值Key的選取，如果選取的Key離中間位置越近，則效率越高
為了解決這個問題 ,也就出現(xiàn)了三數(shù)取中 :
三數(shù)取中，當中的三個數(shù)指的是：最左邊的數(shù)、最右邊的數(shù)以及中間位置的數(shù)。
三數(shù)取中就是取這三個數(shù)當中，值的大小居中的那個數(shù)作為該趟排序的Key ，因為它離中間位置最近。這就確保了我們所選取的數(shù)不會是序列中的最左邊的數(shù)、最右邊的數(shù)
代碼實現(xiàn)：
//三數(shù)取中 ,得到中間元素的下標
int GetMiddleIndexi(int* a, int left, int right)
{
int mid = (left + right) / 2;
if (a[left] < a[mid])
{
if (a[right] > a[mid])
{
return mid;// a[right] > a[mid] > a[left]
}
// a[mid]>=a[right] ，此時a[mid]是最大的 ，只需要比較a[left] ,a[right]
else if (a[left] > a[right])// a[mid] > a[left] > a[right]
{
return left;
}
else //a[left] < a[right]
{
return right; // a[mid] > a[right] > a[left]
}
}
else //a[left] >= a[mid]
{
if (a[mid] > a[right])
{
return mid;
}
//a[mid] <= a[right] ,此時a[mid]已經(jīng)是最小的 只需要比較a[left] 和a[right]
else if (a[left] > a[right]) // a[left] > a[right] > a[mid]
{
return right;
}
else // a[left] <= a[right]
{
return left; //a[right] > a[left] > a[mid ]
}
}
}
遞歸到小的子區(qū)間時，可以考慮使用插入排序
歸并排序
歸并排序是采用分治法的一個非常典型的應用。其基本思想是：將已有序的子序合并，從而得到完全有序的序列，即先使每個子序有序，再使子序列段間有序
動圖演示：
遞歸實現(xiàn)
核心步驟：
分解得到子序列
如何得到有序的子序列 ? 序列分解到只有一個元素或是沒有元素時，就可以認為是有序了
然后合并兩個有序的子序列 ,思路與Leetcode. 88合并兩個有序數(shù)組 相似 ,依次比較 ，較小值尾插到tmp數(shù)組中
創(chuàng)建一個與待排序列大小相同的tmp數(shù)組 ,合并完畢后再將tmp數(shù)組里的數(shù)據(jù)拷貝回原數(shù)組 ，最后將tmp 數(shù)組釋放 。
代碼實現(xiàn) ：
void _MergeSort(int* a, int left, int right, int * tmp)
{
int mid = (left + right) / 2;
//分割
// [begin , mid] [mid+1 , end ]
int begin = left;
int end = right;
if (begin >= end)//序列分解到只有一個元素或是沒有元素時，就可以認為是有序了
return;
_MergeSort(a, begin, mid, tmp); //end-begin+1 是元素個數(shù)
_MergeSort(a, mid + 1, end, tmp);
//歸并 ——類似合并兩個有序數(shù)組 ,[begin , mid] [mid+1 , end ]
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
int i = begin; //不能取0 , 兩段有序區(qū)間不一定是從頭開始的區(qū)間
while (begin1 <= end1 && begin2 <=end2 )
{
if (a[begin1] < a[begin2])
{
tmp[i++] = a[begin1++];
}
else
{
tmp[i++] = a[begin2++];
}
}
//begin1 先走完 ，begin2還沒有走完,begin2尾插到tmp數(shù)組后面
while (begin2 <= end2 )
{
tmp[i++] = a[begin2++];
}
//begin2 先走完 ，begin1還沒有走完, begin1尾插到tmp數(shù)組后面
while (begin1 <= end1)
{
tmp[i++] = a[begin1++];
}
//將tmp數(shù)組拷貝到原數(shù)組中
memcpy(a+begin, tmp+begin, sizeof(int*) * ( right- left +1));
}
void MergeSort(int* a , int left , int right , int *tmp )
{
//申請一個與原數(shù)組大小的tmp數(shù)組
tmp = (int*)malloc(sizeof(int) * (right -left +1 ) );
//歸并
_MergeSort( a, left, right , tmp);
//釋放tmp 數(shù)組
free(tmp);
}
tmp 和 a的后面為什么都要加begin ?
如圖所示：
非遞歸實現(xiàn)
遞歸實現(xiàn)的缺點就是會一直調(diào)用棧幀，而棧幀內(nèi)存往往是很小的。所以，我們嘗試著用循環(huán)的辦法去實現(xiàn)，也就是用非遞歸的方式去實現(xiàn) ，但是非遞歸需要處理幾個邊界條件
和遞歸的區(qū)別就是遞歸要將區(qū)間一直細分，要將左區(qū)間一直遞歸劃分完了，再遞歸劃分右區(qū)間，而借助數(shù)組的非遞歸是一次性就將數(shù)據(jù)處理完畢，并且每次都將下標拷貝回原數(shù)組
歸并排序的非遞歸基本思路是將待排序序列a[0…n-1]看成是n個長度為1的有序序列，將相鄰的有序表成對歸并
非遞歸的核心就是需要控制每次參與合并的元素個數(shù)，使序列變?yōu)橛行?/mark>：
如果排序的數(shù)是奇數(shù)，就會出現(xiàn)一些越界的情況需要特殊處理
end1越界，begin2 和end2絕對也越界了 ，那就不對end1后面的進行歸并
舉例
begin2 和end2越界,那不需要對begin2和end2之間的數(shù)進行歸并
舉例
end2 越界，還是需要歸并，修正end2就可以了
舉例：
void MergeSort(int* a,int n )
{
int* tmp = (int*)malloc(sizeof(int) * (n ) );
if (tmp == NULL)
{
printf("malloc fail");
exit(-1);
}
int gap = 1;
while (gap<n)
{
//歸并
for (int i = 0; i < n; i += 2 * gap)
{
//歸并 ——類似合并兩個有序數(shù)組 ,[begin , end1] [begin2 , end2 ]
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap - 1 + 1, end2 =i+ 2 * gap - 1; //從圖中分析可得
int index= i;
printf("[%d %d] [%d %d] ", begin1, end1, begin2, end2);
/*end1 和begin2越界*/
if (end1 >=n || begin2 >=n)
{
break;
}
//end2越界,修正
if (end2 >=n)
{
end2 = n - 1;
}
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
}
//begin1 先走完 ，begin2還沒有走完,begin2尾插到tmp數(shù)組后面
while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}
//begin2 先走完 ，begin1還沒有走完, begin1尾插到tmp數(shù)組后面
while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}
//將tmp數(shù)組拷貝到原數(shù)組中
memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
}
gap *= 2;
}
free(tmp);
}
歸并排序時間復雜度：
每一層歸并排序的消耗是O(N) ,有 log層 ， 所以歸并排序的時間復雜度 O(N * logN)
排序算法復雜度以及穩(wěn)定性
穩(wěn)定的排序有：直接插入排序、冒泡排序、歸并排序
不穩(wěn)定的排序有：希爾排序、選擇排序、堆排序、快速排序、計數(shù)排序
文章來源：http://www.zghlxwxcb.cn/news/detail-431021.html
如果你覺得這篇文章對你有幫助，不妨動動手指給點贊收藏加轉(zhuǎn)發(fā)，給鄃鱈一個大大的關(guān)注
你們的每一次支持都將轉(zhuǎn)化為我前進的動力?。?！文章來源地址http://www.zghlxwxcb.cn/news/detail-431021.html
到了這里，關(guān)于手把手教你 ，帶你徹底掌握八大排序算法【數(shù)據(jù)結(jié)構(gòu)】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
