归并排序

1、归并排序：

        是针对已经排好序的两个或两个以上的数列，通过合并的方式，将其组合成一个大的且已排好序的数列。

2、主要步骤：

1. 将N个长度为1的数列合并成N/2个已经排序好并且长度为2的数列；
2. 将N/2个长度为2的数列合并成N/4个已经排序好并且长度为4的数列；
3. 将N/4个长度为4的数列合并成N/8个已经排序好并且长度为8的数列；
4. 将N/个长度为的数列合并成N/个已经排序好并且长度为的数列；

     上述步骤中每一步的时间复杂度都是O(n)，而总计有logn层，因此归并排序的时间复杂度为O()

3、代码实现

C++实现：

#include

using namespace std;

const int N = 1000010;





int n;
int q[N],tmp[N];

// q表示排序的数组，l数组的左边界，r表示数组的右边界 
void merge_sort(int q[],int l,int r)
{
	if (l >= r) return;
	
	//取当前中间值 
	int mid = l+r>>1;
	
	//递归排序左右两边 
	merge_sort(q,l,mid),merge_sort(q,mid+1,r);
	
	//归并的过程 
	int k = 0,i = l,j = mid+1;
	while(i <= mid && j<=r)
		//把小的那个数放到tmp中 
		if (q[i] <= q[j]) tmp[k++] = q[i++];
		else tmp[k++] = q[j++];
	while(i <= mid) tmp[k++] = q[i++];
	
	//如果左右两边有没有循环完，就直接放到tmp的后面去 
	while(j <= r) tmp[k++] = q[j++];
	
	//将临时数组数据存到q数组中 
	for(i = l,j = 0;i<=r;i++,j++) q[i] = tmp[j];
	
}


int main()
{
	scanf("%d",&n);
	
	for(int i = 0;i 
python代码：
 
# 最后的99999不列入排序，因此在range中才会-1
list1 = [20,45,51,88,99999]
list2 = [98,10,23,15,99999]
tmp = []

def My_Merge(size1,size2): 
    index1 = 0
    index2 = 0
    for index3 in range(len(list1)+ len(list2)-2):
        if list1[index1] < list2[index2]:
            tmp.append(list1[index1])
            index1 += 1
        else:
            tmp.append(list2[index2])
            index2 += 1
            print("此数字%d取自第2个数列："% tmp[index3])
        print("目前的合并排序结果为：",end='')
        for i in range(index3+1):
            print(tmp[i],' ',end='')
        print('n')

def select_sort(data,size):
    for i in range(size-1):
        small = i
        for j in range(i+1,size):
            if data[j] < data[small]:
                small = j
        data[small],data[i] = data[i],data[small]

def merge_sort():
    # 使用选择排序将两个数列排序再进行合并
    select_sort(list1,len(list1)-1)
    select_sort(list2,len(list2)-1)
    
    print('n第1个数列的排序结果为：',end='')
    for i in range(len(list1)-1):
        print(list1[i],'',end='')
    print('n第2个数列的排序结果为：',end='')
    for i in range(len(list2)-1):
        print(list2[i],'',end='')
    print()
    
    for i in range(60):
        print('=',end='')
    print()
    
    My_Merge(len(list1)-1,len(list2)-1)
    
    for i in range(60):
        print('=',end='')
    print()
    
    print('n合并排序法的最终结果为：',end='')
    for i in range(len(list1)+len(list2)-2):
        print('%d '%tmp[i],end='')

merge_sort()