歸并排序

hlcc 發布于2021-10-08 10:05 / 1259人閱讀

摘要：代碼解析自見文中慢慢理解細細入深開辟分配一個輔助臨時數組開辟成功之后實現歸并之前的劃分數組步驟利用之后立刻釋放空間開辟失敗每一次找中間值依次劃分遞歸劃分后左邊的新一塊遞歸劃分后右邊的一塊合并已劃分排序好的數組一直為標記左半區第一個未排序

代碼解析自見文中

慢慢理解細細入深

#include#includevoid Print(int arr[], int sz){	int i = 0;	for (i = 0; i < sz; i++)	{		printf("%d", arr[i]);	}}void merge_sort(int arr[],int sz){	//開辟分配一個輔助臨時數組	int* temparr = (int*)mallco(sz * sizeof(int));	if (temparr)	{		//開辟成功之后 實現歸并之前的劃分數組步驟		msort(arr,temparr, 0, sz - 1);		//利用之后 立刻釋放空間		free(temparr);	}	else//開辟失敗	{		printf("error:failed to allocate memory");	}}void msort(int arr[],int temparr[] ,int left, int right){	int mid = (left + right) / 2;//每一次找中間值 依次劃分	if(left <= right)	{		msort(arr,temparr, left,mid);//遞歸劃分后左邊的新一塊		msort(arr,temparr, mid + 1, right);//遞歸劃分后右邊的一塊		merge(arr, temparr, left, right, mid);//合并已劃分排序好的數組	}}void merge(int arr[], int temparr[], int left, int right, int mid){	//left一直為0	int L_pos = left;//標記左半區第一個未排序的數字	int R_pos = right;//標記右半區第一個未排序的數字	int pos = left;//臨時數組的下標	while (L_pos <= mid && R_pos <= right)	{		//每次分別把左右半區的第一個元素拿出來進行比較大小		if (arr[L_pos] > arr[R_pos])		{			temparr[pos] = arr[R_pos];			pos++;			R_pos++;		}		else		{			temparr[pos] = arr[L_pos];			pos++;			L_pos++;		}	}	//當左半區排完之后 右半區剩余依次放進去	while (L_pos <= mid)	{		temparr[pos] = arr[L_pos];		pos++;		L_pos++;	}	//同理可得	while (R_pos <= right)	{		temparr[pos] = arr[R_pos];		pos++;		R_pos++;	}	//把臨時數組合并后的元素放到原來的數組	while (left <= right)	{		//left在這同樣初始為0開始		arr[left] = temparr[left];		left++;	}}int main(){	int arr[] = { 9,5,2,7,12,4,3,1,11 };	int sz = sizeof(arr) / sizeof(arr[0]);	Print(arr, sz);	printf("/n");	merge_sort(arr,sz);	Print(arr, sz);	return 0;}

祝你好運

GPU云服務器云服務器歸并排序二路歸并排序歸并排序算法 java歸并排序

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/121847.html

歸并排序 - Algorithms, Part I, week 3 MERGESORTS

摘要：兩個單元素數組的合并實際就是對這兩個數進行了排序，即變為，同樣再對后一組的兩個數歸并排序，即變為，再將兩單元數組歸并成四單元數組即和歸并為。前言本周講解兩個50多年前發明，但今天仍然很重要的經典算法 (歸并排序和快速排序) 之一 -- 歸并排序，幾乎每個軟件系統中都可以找到其中一個或兩個的實現，并研究這些經典方法的新變革。我們的涉及范圍從數學模型中解釋為什么這些方法有效到使這些算法...

Jokcy 2019-08-19 11:35 評論0 收藏0
歸并排序就這么簡單

摘要：歸并排序就這么簡單從前面已經講解了冒泡排序選擇排序插入排序快速排序了，本章主要講解的是歸并排序，希望大家看完能夠理解并手寫出歸并排序快速排序的代碼，然后就通過面試了如果我寫得有錯誤的地方也請大家在評論下指出。歸并排序就這么簡單從前面已經講解了冒泡排序、選擇排序、插入排序,快速排序了，本章主要講解的是歸并排序，希望大家看完能夠理解并手寫出歸并排序快速排序的代碼，然后就通過面試了！如果...

ingood 2019-08-19 10:42 評論0 收藏0
歸并排序

摘要：概述歸并排序法是將兩個或兩個以上有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。概述歸并（Merge）排序法是將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。歸并排序采用的是遞歸來實現，屬于分而治之，將目標數組從中間一分為二，之后分別對這兩個數組進行排序，排序...

CoyPan 2019-08-14 15:12 評論0 收藏0
Java排序之歸并排序

摘要：排序之歸并排序簡介歸并排序的算法是將多個有序數據表合并成一個有序數據表。如果參與合并的只有兩個有序表，則成為二路合并。對于一個原始的待排序數列，往往可以通過分割的方法來歸結為多路合并排序。 Java排序之歸并排序 1. 簡介歸并排序的算法是將多個有序數據表合并成一個有序數據表。如果參與合并的只有兩個有序表，則成為二路合并。對于一個原始的待排序數列，往往可以通過分割的方法來歸結為多路合...

gityuan 2019-08-15 18:10 評論0 收藏0