八大排序算法-归并排序

￡神魔★判官ぃ 2022-06-07 13:46 198阅读 0赞

归并排序的定义：

是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序的基本思想：

设r\[i…n\]由两个有序子表r\[i…m\]和r\[m+1…n\]组成，两个子表长度分别为n-i +1、n-m。

1、j=m+1；k=i；i=i; 置两个子表的起始下标及辅助数组的起始下标。

2、若i>m 或j>n，转⑷ 其中一个子表已合并完，比较选取结束。

3、选取sourceArr\[i\]和sourceArr\[j\]较小的存入辅助数组rf。  
如果sourceArr\[i\]<sourceArr\[j\]，tempArr\[k\]=sourceArr\[i\]； i++； k++； 转⑵  
否则，tempArr\[k\]=sourceArr\[j\]； j++； k++； 转⑵

4、将尚未处理完的子表中元素存入rf。  
如果i<=m，将r\[i…m\]存入tempArr\[k…n\] //前一子表非空  
如果j<=n ,  将r\[j…n\] 存入tempArr\[k…n\] //后一子表非空

5、合并结束。

过程演示：

设有数列\{35，28，58，10，61，58，97，17\}  
初始状态：35，28，58，10，61，58，97，17  
第一次归并后：\{28，35\},\{10，58\},\{58，61\}，\{17，97\}；  
第二次归并后：\{10，28，35，58\}，\{17，58，61，97\}；  
第三次归并后：\{10，17，28，35，58，58，61，97\}；

时间复杂度为：O(nlogn)。

算法：

#include <stdlib.h>
    #include <iostream>
    
    int arr[] = { 35, 28, 58, 10, 61, 58, 97, 17 };
    int k = sizeof(arr) / sizeof(arr[0]);
    
    void Merge(int sourceArr[], int tempArr[], int startIndex, int midIndex, int endIndex)
    {
    	int i = startIndex, j = midIndex + 1, k = startIndex;
    	while (i != midIndex + 1 && j != endIndex + 1)
    	{
    		if (sourceArr[i] > sourceArr[j])
    			tempArr[k++] = sourceArr[j++];
    		else
    			tempArr[k++] = sourceArr[i++];
    	}
    	while (i != midIndex + 1)
    		tempArr[k++] = sourceArr[i++];
    	while (j != endIndex + 1)
    		tempArr[k++] = sourceArr[j++];
    	for (i = startIndex; i <= endIndex; i++)
    		sourceArr[i] = tempArr[i];
    }
    
    //内部使用递归
    void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex)
    {
    	int midIndex;
    	if (startIndex < endIndex)
    	{
    		midIndex = (startIndex + endIndex) / 2;
    		MergeSort(sourceArr, tempArr, startIndex, midIndex);
    		MergeSort(sourceArr, tempArr, midIndex + 1, endIndex);
    		Merge(sourceArr, tempArr, startIndex, midIndex, endIndex);
    	}
    }
    
    int main(int argc, char * argv[])
    {
    	int i, b[8];
    	MergeSort(arr, b, 0, k - 1);
    	for (int f = 0; f < k; f++)
    	{
    		std::cout << arr[f] << "  ";
    	}
    	getchar();
    	return 0;
    }