数据结构与算法——排序算法—（5）归并排序

缺乏、安全感 2022-02-26 20:59 351阅读 0赞

**思想：**  
将两个有序数列合并成一个有序数列我们称之为归并。归并排序就是利用归并思想对数列进行排序。归并排序包括“从上到下”和“从下到上”，这里主要讲从上到下的思想：  
(1）分解:将当前区间一分为二，即求分裂点mid=(start+end)/2;  
(2)求解：递归的对两个子区间a\[start,mid\]和a\[mid+1,end\]进行归并排序。递归的终结条件是子区间长度为1.  
（3）合并：将已排序的两个子区间a\[start,mid\]和a\[mid+1,end\]归并为一个有序的区间a\[low,high\]

**程序**

//(5)归并排序
    void merge(int *a, int start, int mid, int end)
    {
    	int *temp = new int[end - start + 1];
    	int i = start;
    	int j = mid + 1;
    	int k = 0;
    
    	while (i <= mid && j <= end)//(i < mid && j < end)
    	{
    		if (a[i] <= a[j])//(a[i] >= a[j])
    			temp[k++] = a[i++];
    		else
    			temp[k++] = a[j++];
    	}
    
    	while (i <= mid)
    		temp[k++] = a[i++];
    
    	while(j <= end)
    		temp[k++] = a[j++];
    
    	for (i = 0; i< k; ++i)
    	{
    		a[start + i] = temp[i];
    	}
    	delete[] temp;
    }
    
    void mergeSortUp2Down(int* a, int start, int end)
    {
    	if (a == NULL || start >= end)
    		return;
    
    	int mid = (end + start) / 2;
    	mergeSortUp2Down(a, start, mid); // 递归排序a[start...mid]
    	mergeSortUp2Down(a, mid + 1, end); // 递归排序a[mid+1...end]
    
    // a[start...mid] 和 a[mid...end]是两个有序空间，
    // 将它们排序成一个有序空间a[start...end]
    	merge(a, start, mid, end);
    }
    
    //调用：
    mergeSortUp2Down(arr, 0, length-1);

**时间复杂度和稳定性：**  
归并排序的时间复杂度为O(N*lgN)，假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N),需要遍历多少次？  
归并排序的形式就是一颗二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的可以得出它的时间复杂度是O(N*lgN)

归并排序是稳定的  
算法稳定性——假设在数列中存在a\[i\] = a\[j\],若在排序之前，a\[i\]在a\[j\]前面；并且排序之后，a\[i\]仍然在a\[j\]前面。