欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語言常見排序算法歸并排序

 更新時(shí)間:2022年07月14日 09:04:27   作者:保護(hù)小周?  
這篇文章主要介紹了C語言常見排序算法歸并排序,歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法的一個(gè)非常典型的應(yīng)用

前言

本期為大家?guī)淼氖浅R娕判蛩惴ㄖ械?strong>歸并排序,博主在這里先分享歸并排序的遞歸算法,包您一看就會(huì),快來試試吧~

 一、歸并排序

1.1 基本思想

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

1.2 算法思想

到這里,我們可以得到一條結(jié)論,兩個(gè)有序的子序列可以合成一個(gè)新的有序子序列,通過遞歸,我們兩個(gè)新的有序序列也可以組成新的有序數(shù)列,最終實(shí)現(xiàn)排序的目的。有些朋友就會(huì)問了,這個(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)開辟的(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è)元素。
  • 每兩個(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)開辟空間的函數(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)開辟與待排序數(shù)組大小相等的一片連續(xù)的空間
	_MergeSort(a,0,n-1,tmp);//子函數(shù)實(shí)現(xiàn)歸并
 
	free(tmp);//釋放動(dòng)態(tà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;
}

1.5 歸并排序的特性總結(jié)

  • 1. 歸并的缺點(diǎn)在于需要O(N)的空間復(fù)雜度,歸并排序的思考更多的是解決在磁盤中的外排序問 題。
  • 2. 時(shí)間復(fù)雜度:O(N*logN)
  • 3. 空間復(fù)雜度:O(N)
  • 4. 穩(wěn)定性:穩(wěn)定

到此這篇關(guān)于C語言常見排序算法歸并排序的文章就介紹到這了,更多相關(guān)C語言歸并排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • C++入門指南之貪吃蛇游戲的實(shí)現(xiàn)

    C++入門指南之貪吃蛇游戲的實(shí)現(xiàn)

    這篇文章主要給大家介紹了關(guān)于C++入門指南之貪吃蛇游戲?qū)崿F(xiàn)的相關(guān)資料,文章通過示例代碼介紹的非常詳細(xì),可以讓大家能短時(shí)間內(nèi)寫出一個(gè)貪吃蛇,需要的朋友可以參考下
    2021-10-10
  • C語言二維數(shù)組應(yīng)用實(shí)現(xiàn)掃雷游戲

    C語言二維數(shù)組應(yīng)用實(shí)現(xiàn)掃雷游戲

    這篇文章主要為大家詳細(xì)介紹了C語言二維數(shù)組應(yīng)用實(shí)現(xiàn)掃雷游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-06-06
  • C語言malloc與calloc區(qū)別詳解

    C語言malloc與calloc區(qū)別詳解

    本文主要介紹了C語言malloc與calloc區(qū)別詳解,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2023-01-01
  • C++制作簡(jiǎn)單的計(jì)算器功能

    C++制作簡(jiǎn)單的計(jì)算器功能

    這篇文章主要為大家詳細(xì)介紹了C++制作簡(jiǎn)單的計(jì)算器功能,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-02-02
  • C++多繼承同名隱藏實(shí)例詳細(xì)介紹

    C++多繼承同名隱藏實(shí)例詳細(xì)介紹

    多繼承可以看作是單繼承的擴(kuò)展。所謂多繼承是指派生類具有多個(gè)基類,派生類..本文將對(duì)C++多繼承同名隱藏實(shí)例進(jìn)行分析
    2012-11-11
  • C++實(shí)現(xiàn)主機(jī)字節(jié)序和網(wǎng)絡(luò)字節(jié)序轉(zhuǎn)換示例

    C++實(shí)現(xiàn)主機(jī)字節(jié)序和網(wǎng)絡(luò)字節(jié)序轉(zhuǎn)換示例

    這篇文章主要為大家介紹了C++實(shí)現(xiàn)主機(jī)字節(jié)序和網(wǎng)絡(luò)字節(jié)序轉(zhuǎn)換示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2023-11-11
  • C++11中跳轉(zhuǎn)initializer_list實(shí)現(xiàn)分析

    C++11中跳轉(zhuǎn)initializer_list實(shí)現(xiàn)分析

    這篇文章主要介紹了C++11中跳轉(zhuǎn)initializer_list實(shí)現(xiàn)分析,實(shí)例分析initializer_list<T>初體驗(yàn),結(jié)合示例代碼給大家介紹的非常詳細(xì),需要的朋友可以參考下
    2022-04-04
  • C++實(shí)現(xiàn)LeetCode(199.二叉樹的右側(cè)視圖)

    C++實(shí)現(xiàn)LeetCode(199.二叉樹的右側(cè)視圖)

    這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(199.二叉樹的右側(cè)視圖),本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
    2021-08-08
  • C語言scandir函數(shù)獲取文件夾內(nèi)容的實(shí)現(xiàn)

    C語言scandir函數(shù)獲取文件夾內(nèi)容的實(shí)現(xiàn)

    scandir?函數(shù)用于列舉指定目錄下的文件列表,本文主要介紹了C語言scandir函數(shù)獲取文件夾內(nèi)容的實(shí)現(xiàn),具有一定的參考價(jià)值,感興趣的可以了解一下
    2024-03-03
  • c語言的程序環(huán)境與預(yù)處理詳解

    c語言的程序環(huán)境與預(yù)處理詳解

    大家好,本篇文章主要講的是c語言的程序環(huán)境與預(yù)處理詳解,感興趣的同學(xué)趕快來看一看吧,對(duì)你有幫助的話記得收藏一下
    2022-02-02

最新評(píng)論