【数据结构】-内部排序(归并排序)

墨蓝 2022-11-26 05:57 191阅读 0赞

### 内部排序-归并排序 ###

*  写在前面
 *  1.头文件及类型定义
 *  2.函数声明
 *  3.基本操作
 *   *  3.1 归并
     *  3.2 主过程
     *  3.3 输出
 *  4.main函数
 *  5.小结

# 写在前面 #

【说明】以下代码实现最终为**递增序列**，即从小到大排序。

# 1.头文件及类型定义 #

#include<stdio.h>
    #include<stdlib.h>
    #define ElemType int	//定义数组元素类型
    #define LEN 7			//定义数组长度

# 2.函数声明 #

/*函数声明*/
    void Merge(ElemType A[], int low, int mid, int high);		//1.归并
    void MergeSort(ElemType A[], int low, int high);			//2.归并主过程
    void Print(ElemType A[], int len);							//3.输出

# 3.基本操作 #

## 3.1 归并 ##

//1.归并
    ElemType* B = (ElemType*)malloc((LEN) * sizeof(ElemType));		//辅助数组B
    void Merge(ElemType A[], int low, int mid, int high) {
        
    	//表A的两段A[low...mid]和A[mid+1...high]各自有序，将它们合并成一个有序表
    	int i, j, k;
    	for (k = low; k <= high; k++)
    		B[k] = A[k];				//将A中所有元素复制到B中
    	for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {
        
    		if (B[i] <= B[j])			//比较B的左右两段中的元素
    			A[k] = B[i++];			//将较小值复制到A中
    		else
    			A[k] = B[j++];
    	}//for
    	while (i <= mid)
    		A[k++] = B[i++];	//若第一个表未检测完，复制
    	while (j <= high)
    		A[k++] = B[j++];	//若第二个表未检测完，复制
    }

## 3.2 主过程 ##

//2.归并主过程
    void MergeSort(ElemType A[], int low, int high) {
        
    	if (low < high) {
        	
    		int mid = (low + high) / 2;		//从中间划分两个子序列
    		MergeSort(A, low, mid);			//对左侧子序列进行递归排序
    		MergeSort(A, mid + 1, high);	//对右侧子序列进行递归排序
    		Merge(A, low, mid, high);		//归并
    	}
    }

## 3.3 输出 ##

//3.输出
    void Print(ElemType A[], int len) {
        
    	for (int i = 0; i < len; i++)
    		printf("%d\t", A[i]);
    	printf("%\n");
    }

# 4.main函数 #

int main() {
        
    
    	ElemType A[] = {
        49,38,65,97,76,13,27};
    	MergeSort(A, 0, LEN-1);	
    	Print(A, LEN);
    
    	return 0;
    }

# 5.小结 #

*一、归并的概念*

*  "**归并**"的含义是将两个或两个以上的有序表组合成一个新的有序表。在内部排序中通常为**二路归并**。

*二、关于归并排序的性能分析*

*  **空间复杂度**：O(n)  
    **时间复杂度**：O(nlog2n)  
    **稳定性**:稳定  
    **适用性**：适用于顺序存储的线性表

*三、归并排序的相关特点*

1.  **m路归并，每选出一个元素需要对比关键字m-1次**
2.  **n个元素进行m路归并，归并趟数:⌈logmn⌉**