C語(yǔ)言數(shù)據(jù)結(jié)構(gòu) 鏈表與歸并排序?qū)嵗斀?/h1>

來源：本站原創(chuàng)|時(shí)間：2020-01-10|欄目：C語(yǔ)言|點(diǎn)擊： 次

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu) 鏈表與歸并排序?qū)嵗斀?/strong>

歸并排序適合于對(duì)鏈表進(jìn)行原址排序，即只改變指針的連接方式，不交換鏈表結(jié)點(diǎn)的內(nèi)容。

歸并排序的基本思想是分治法：先把一個(gè)鏈表分割成只有一個(gè)節(jié)點(diǎn)的鏈表，然后按照一定順序、自底向上合并相鄰的兩個(gè)鏈表。

只要保證各種大小的子鏈表是有序的，那么最后返回的鏈表就一定是有序的.

歸并排序分為分割和合并兩個(gè)子過程。分割是用遞歸的方法，把鏈表對(duì)半分割成兩個(gè)子鏈表；合并是在遞歸返回（回朔）的時(shí)候，把兩個(gè)有序鏈表合并成一個(gè)有序鏈表。

(注意：只有一個(gè)節(jié)點(diǎn)的鏈表一定是有序的)

這里sort過程就是分割過程；merge過程就是合并且排序的過程

說到分割鏈表，那么問題來了：鏈表不是隨機(jī)訪問的，我怎么知道分割點(diǎn)在哪里？一個(gè)寶貴的經(jīng)驗(yàn)就是：維護(hù)兩個(gè)指針，一快一慢?？熘羔樏看魏笠苾蓚€(gè)單位，慢指針每次只移動(dòng)一個(gè)單位。當(dāng)快指針移動(dòng)到tail或者最后一個(gè)有效節(jié)點(diǎn)時(shí)，慢指針就指向了中間的節(jié)點(diǎn)。

sort過程:

Node* sort (Node* beg)
{
  if(beg==tail || beg->next==tail) return beg;
  Node* a = beg; Node* b = beg->next;
  while(b!=tail && b->next != tail)
  {
    a = a->next; b = b->next->next;
  }
  b = a->next;  //the beginning of right part
  a->next = tail; //the end of left part
  return merge(sort(beg), sort(b));
}

把鏈表分割之后就要合并。merge操作傳入的參數(shù)是兩個(gè)有序鏈表，返回的是合并后的有序的鏈表。兩個(gè)有序鏈表簡(jiǎn)單拼接之后不一定是有序的，需要對(duì)每一個(gè)元素重排。這個(gè)重排的過程是從兩個(gè)鏈表各自最小（最大）元素開始，誰(shuí)?。ù螅┚桶颜l(shuí)放到新的鏈表里。

Node* LinkedList<T>::merge(Node* a, Node* b)
{
	Node dummy = Node();
	Node* head = &dummy;
	// temp是正在合并的表的節(jié)點(diǎn)
	Node* temp = head;
	while(a!=tail && b!=tail) //逐個(gè)比較鏈表a和鏈表b的每個(gè)元素
	{
		if(a->data <= b->data)
		{
			// 如果a比b小, 那么當(dāng)前結(jié)點(diǎn)的后繼就是a
			temp->next = a;
			// 把當(dāng)前節(jié)點(diǎn)移向后繼
			temp = a;
			// a后移
			a = a->next;
		}
		else 
		{
			temp->next = b;
			temp = b; 
			b = b->next;
		}
		// 如果原表a已經(jīng)排完,那么新表后面就放b的剩余元素
		// 否則仍然以a為標(biāo)準(zhǔn)和b進(jìn)行比較
		temp->next = (a==tail) ? b : a;
	}
	return head->next;
}

感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！