快捷導(dǎo)航

C語(yǔ)言常見(jiàn)排序算法歸并排序

更新時(shí)間：2022年07月14日 09:04:27 作者：保護(hù)小周?

這篇文章主要介紹了C語(yǔ)言常見(jiàn)排序算法歸并排序，歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法的一個(gè)非常典型的應(yīng)用

前言

本期為大家?guī)?lái)的是常見(jiàn)排序算法中的歸并排序，博主在這里先分享歸并排序的遞歸算法，包您一看就會(huì)，快來(lái)試試吧~

一、歸并排序

1.1 基本思想

歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。

1.2 算法思想

到這里，我們可以得到一條結(jié)論，兩個(gè)有序的子序列可以合成一個(gè)新的有序子序列，通過(guò)遞歸，我們兩個(gè)新的有序序列也可以組成新的有序數(shù)列，最終實(shí)現(xiàn)排序的目的。有些朋友就會(huì)問(wèn)了，這個(gè)我懂，關(guān)鍵是咋實(shí)現(xiàn)有序數(shù)列，其實(shí)非常的簡(jiǎn)單，分割遞歸至每個(gè)子序列只有一個(gè)元素時(shí)，是不是就有序啦，然后就可以合成有兩個(gè)元素有序的列表嘛，再合成4個(gè)，8個(gè)……

1.3 程序設(shè)計(jì)思想

定義一個(gè)tmp數(shù)組，可以是動(dòng)態(tài)開(kāi)辟的(malloc)，用于臨時(shí)存放合并后的有序數(shù)據(jù)，定義_MergeSort()函數(shù)，用于分解，合并數(shù)據(jù)（遞歸實(shí)現(xiàn)），參數(shù)有，待處理數(shù)組，數(shù)據(jù)區(qū)間（數(shù)組下標(biāo)），tmp數(shù)組。

判斷區(qū)間是否存在，區(qū)間不存在以及只有一個(gè)元素的情況結(jié)束程序。
分割區(qū)間：mid=(left+right)/2;遞歸左右區(qū)間，分割遞歸至每個(gè)子序列只有一個(gè)元素。
每?jī)蓚€(gè)子序列一組，循環(huán)遍歷每一個(gè)元素，if比較兩個(gè)子序列各元素的大小，取大或取小，放入tmp數(shù)組，tmp[index++]=子序列++；直到有一個(gè)子序列遍歷完，循環(huán)結(jié)束。
循環(huán)判斷是子序列是否遍歷完畢，未遍歷完畢的子序列剩余元素直接給到tmp數(shù)組。將tmp數(shù)組的對(duì)應(yīng)的元素拷貝回原數(shù)組（已有序）。

1.4 程序?qū)崿F(xiàn)

#define _CRT_SECURE_NO_WARNINGS
 
#include<stdio.h>
#include<stdlib.h>//動(dòng)態(tài)開(kāi)辟空間的函數(shù)的頭文件
 
void _MergeSort(int *a,int left,int right,int *tmp)
{
	//區(qū)間不存在以及只有一個(gè)元素的情況結(jié)束程序
	if (left>=right)
	{
		return;
	}
 
	int mid = (left + right) / 2;
	//假設(shè)[left,mid],[mid+1,right]有序，那么我們就可以歸并了
	//遞歸使左右區(qū)間有序
	//分割遞歸至每個(gè)子序列只有一個(gè)元素
	_MergeSort(a,left,mid,tmp);
	_MergeSort(a, mid+1,right, tmp);
 
	//歸并
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = left;
 
	while (begin1<=end1&&begin2<=end2)//有一個(gè)子序列遍歷完，循環(huán)結(jié)束
	{
		if (a[begin1] < a[begin2])//升序，取小
		{
			tmp[index++] = a[begin1++];
 
		}
		else
		{
			tmp[index++] = a[begin2++];
		}
	}
 
	//判斷子序列是否遍歷完，未遍歷完畢的子序列剩余元素直接給到tmp數(shù)組
	while (begin1 <= end1)
	{
		tmp[index++] = a[begin1++];
	}
 
	while (begin2<=end2)
	{
		tmp[index++] = a[begin2++];
	}
 
	//拷貝回去
	for (int i=left;i<=right;++i)
	{
		a[i] = tmp[i];
	}
}
 
//歸并排序
void MergeSort(int *a,int n)
{
	int* tmp=(int*)malloc(sizeof(int)*n);//動(dòng)態(tài)開(kāi)辟與待排序數(shù)組大小相等的一片連續(xù)的空間
	_MergeSort(a,0,n-1,tmp);//子函數(shù)實(shí)現(xiàn)歸并
 
	free(tmp);//釋放動(dòng)態(tài)開(kāi)辟的空間
}
 
//打印
void Print(int* a, int n)
{
	for (int i=0;i<n;++i)
	{
		printf("%d ",a[i]);
	}
}
int main()
{
	int a[] = {10,6,7,1,3,9,4,2};
	MergeSort(a,sizeof(a)/sizeof(a[0]));
	Print(a,sizeof(a)/sizeof(a[0]));
	return 0;
}