什么是歸并排序？
- 概念
- 演算法實作
- 后續
概念
“歸并”的含義是將兩個或兩個以上的有序表組合成一個新的有序表，假設待排序表含有n個記錄，則可將其視為n個有序的子表，每個子表的長度為一，然后兩兩歸并，得到【n/2】個長度為2或1的有序表；繼續兩兩歸并，，，如此重復，直到合并成一個長度為n的有序表為止，這種排序方法稱為2路歸并排序，
歸并排序是使用到了分治方法（Divide and Conquer），
- Divide：將原問題分解為若干子問題，其中這些子問題的規模小于原問題的規模，
- Conquer：遞回地求解子問題，當子問題規模足夠小時直接求解，
- Merge：將子問題的解合并得到原問題的解，
演算法實作
/*****************歸并排序*****************/
int guibing = 10;//和總體表的大小一致
ElemType* B = (ElemType*)malloc((guibing + 1) * sizeof(ElemType));//輔助陣列B
void Merge(ElemType A[],int low,int mid,int high)
{
int i, j,k;
//表A[low...mid]和A[mid+1...high]各自有序，將他們合并成一個有序表
for (int k = low; k <= mid; k++)
B[k] = A[k];
for (int i = low, j = mid + 1, k = i; i <= mid && j <= high; k++)
{
if (B[i] <= B[j])
A[k] = B[i++];//將較小值復制到A中
else
A[k] = B[j++];
}
while (i <= mid)
A[k++] = B[i++];//若第一個表未檢測完，復制
while (j <= high)
A[k++] = B[j++];
}
void Merge_Sort(ElemType A[],int low,int high)
{
if (low < high)
{
int mid = (low+high)/2; //劃分成兩個子序列
Merge_Sort(A,low,mid);
Merge_Sort(A,mid+1,high);
Merge(A,low,mid,high); //歸并
}
}
后續
如果想了解更多物聯網、智能家居專案知識，可以關注我的程式設計專欄，
訂閱專欄后，可以在微信公眾號上私聊我，直接發給你原始碼，
或者關注公眾號，
撰寫不易，感謝支持，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/294294.html
標籤：其他