單鏈表的冒泡，快排，選擇，插入，歸并等多圖詳解-有解無憂

上節介紹了鏈表的基本操作

0.穩定排序和原地排序的定義
1.冒泡排序
2.快速排序
3.插入排序
4.選擇排序
5.歸并排序

這節介紹鏈表的5種排序演算法，
@目錄

0.穩定排序和原地排序的定義
1.冒泡排序
2.快速排序
3.插入排序
4.選擇排序
5.歸并排序

0.穩定排序和原地排序的定義

穩定排序：
??假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，則稱這種排序演算法是穩定的；否則稱為不穩定的，像冒泡排序，插入排序，基數排序，歸并排序等都是穩定排序
原地排序：
??基本上不需要額外輔助的的空間，允許少量額外的輔助變數進行的排序，就是在原來的排序陣列中比較和交換的排序，像選擇排序，插入排序，希爾排序，快速排序，堆排序等都會有一項比較且交換操作(swap(i,j))的邏輯在其中，因此他們都是屬于原地(原址、就地)排序，而合并排序，計數排序，基數排序等不是原地排序

1.冒泡排序

基本思想:
??把第一個元素與第二個元素比較，如果第一個比第二個大，則交換他們的位置，接著繼續比較第二個與第三個元素，如果第二個比第三個大，則交換他們的位置....
??我們對每一對相鄰元素作同樣的作業，從開始第一對到結尾的最后一對，這樣一趟比較交換下來之后，排在最右的元素就會
是最大的數，除去最右的元素，我們對剩余的元素做同樣的作業，如此重復下去，直到排序完成，
具體步驟：
??1.比較相鄰的元素，如果第一個比第二個大，就交換他們兩個，
??2.對每一對相鄰元素作同樣的作業，從開始第一對到結尾的最后一對，這步做完后，最后的元素會是最大的數，
??3.針對所有的元素重復以上的步驟，除了最后一個，
??4.持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較，
時間復雜度：O(N2)
空間復雜度：O(1)
穩定排序:是
原地排序:是
在這里插入圖片描述


Node *BubbleSort(Node *phead)
{

	Node * p = phead;
	Node * q = phead->next;
	/*有幾個資料就-1；比如x 個i<x-1*/
	for(int i=0;i<5;i++)
	{ 
		while((q!=NULL)&&(p!=NULL))
		{ 
			if(p->data>q->data)
			{
				/*頭結點和下一節點的交換，要特殊處理，更新新的頭head*/
				if (p == phead)
				{
					p->next = q->next;
					q->next = p;
					head = q;
					phead = q;
					/*這里切記要把p,q換回來，正常的話q應該在p的前面，進行的是p,q的比較
					*但是經過指標域交換之后就變成q,p.再次進行下一次比較時，
					*就會變成q,p的資料域比較，假如原本p->data > q->data,則進行交換，變成q->data和p->data比較，
					*不會進行交換，所以排序就會錯誤，有興趣的可以除錯下，
					*/	
					Node*temp=p; 
					p=q;
					q=temp;		
				}
				/*處理中間程序，其他資料的交換情況，要尋找前驅節點if (p != phead)*/
				else 
				{
					/*p，q的那個在前，那個在后，指標域的連接畫圖好理解一點*/
					if (p->next == q)
					{
						/*尋找p的前驅節點*/
						Node *ppre = FindPreNode(p);
						/*將p的下一個指向q的下一個*/
						p->next = q->next;
						/*此時q為頭結點，讓q的下一個指向p，連接起來*/
						q->next = p;
						/*將原來p的前驅節點指向現在的q，現在的q為頭結點*/
						ppre->next = q;
						Node*temp=p; 
						p=q; 
						q=temp;
					}
					else if (q->next == p)
					{
						Node *qpre = FindPreNode(q);
						q->next = p->next;
						p->next = q;
						qpre->next = p;
						Node*temp=p;
						p=q; 
						q=temp;
						}									
				}		
			}
			/*地址移動*/
			p = p->next;
			q = q->next;
		}
		/*進行完一輪比較后，從頭開始進行第二輪*/
		p = phead;
		q = phead->next;	
	}
	
	head = phead;
	return head;
}

2.快速排序

基本思想
??我們從陣列中選擇一個元素，我們把這個元素稱之為中軸元素吧，然后把陣列中所有小于中軸元素的元素放在其左邊，
所有大于或等于中軸元素的元素放在其右邊，顯然，此時中軸元素所處的位置的是有序的，也就是說，我們無需再移動中軸
元素的位置，
??從中軸元素那里開始把大的陣列切割成兩個小的陣列(兩個陣列都不包含中軸元素)，接著我們通過遞回的方式，讓中軸元素
左邊的陣列和右邊的陣列也重復同樣的操作，直到陣列的大小為1，此時每個元素都處于有序的位置，
具體步驟：
??1.從數列中挑出一個元素，稱為 "基準"（pivot）;
??2.重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊），在這個磁區退出之后，該基準就處于數列的中間位置，這個稱為磁區（partition）操作；
??3.遞回地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序；
時間復雜度：O(NlogN)
空間復雜度：O(logN)
穩定排序：否
原地排序：是

在這里插入圖片描述


int *QuickSort(Node* pBegin, Node* pEnd)
{
    if(pBegin == NULL || pEnd == NULL || pBegin == pEnd)
        return 0;
 
    //定義兩個指標
    Node* p1 = pBegin;
    Node* p2 = pBegin->next;
    int pivot = pBegin->data;

	//每次只比較小的，把小的放在前面，經過一輪比較后，被分成左右兩部分，其中p1指向中值處，pbegin為pivot，
    while(p2 != NULL)/* && p2 != pEnd->next */
	{
        if(p2->data < pivot)
		{
            p1 = p1->next;
            if(p1 != p2)
			{
                SwapData(&p1->data, &p2->data);
        	}
      	}
        p2 = p2->next;
   }
   /*此時pivot并不在中間，我們要把他放到中間，以他為基準，把資料分為左右兩邊*/
    SwapData(&p1->data, &pBegin->data);
    //此時p1是中值節點
	//if(p1->data >pBegin->data)
    QuickSort(pBegin, p1);
	//if(p1->data < pEnd->data)
    QuickSort(p1->next, pEnd);

}

3.插入排序

基本思想:每一步將一個待排序的記錄，插入到前面已經排好序的有序序列中去，直到插完所有元素為止，
具體步驟：
??1.將待排序序列第一個元素看做一個有序序列，把第二個元素到最后一個元素當成是未排序序列；
??2.取出下一個元素，在已經排序的元素序列中從后向前掃描；
??3.如果該元素（已排序）大于新元素，將該元素移到下一位置；
??4.重復步驟3，直到找到已排序的元素小于或者等于新元素的位置；
??5.將新元素插入到該位置后；
??6.重復步驟2~5，
時間復雜度：O(N2)
空間復雜度：O(1)
穩定排序：是
原地排序：是

在這里插入圖片描述

/*不好理解可以除錯下看下具體程序*/
Node *InsertSort(Node *phead)  
{  
	/*為原鏈表剩下用于直接插入排序的節點頭指標*/  
    Node *unsort; 
	/*臨時指標變數：插入節點*/
    Node *t;  
	/*臨時指標變數*/  
    Node *p; 
	/*臨時指標變數*/  
    Node *sort; 
	/*原鏈表剩下用于直接插入排序的節點鏈表：可根據圖12來理解，*/  
    unsort = phead->next; 
	/*只含有一個節點的鏈表的有序鏈表：可根據圖11來理解，*/  
    head->next = NULL; 
  	/*遍歷剩下無序的鏈表*/ 
    while (unsort != NULL)  
    {  
        /*注意：這里for陳述句就是體現直接插入排序思想的地方*/
		/*無序節點在有序鏈表中找插入的位置*/  
		/*跳出for回圈的條件：
		*1.sort為空，此時，sort->data < t->data，p存下位置，應該放在有序鏈表的后面
		*2.sort->data > t->data ，跳出回圈時，t->data放在有序鏈表sort的前面
		*3.sort為空 sort->data > t->data，也插入在sort前面的位置
		*/  
		/*q為有序鏈表*/
        for (t = unsort, sort = phead; ((sort != NULL) && (sort->data < t->data)); p = sort, sort = sort->next); 
      
   		 /*退出for回圈，就是找到了插入的位置插入位置要么在前面，要么在后面*/  
    	/*注意：按道理來說，這句話可以放到下面注釋了的那個位置也應該對的，但是就是不能，原因：你若理解了上面的第3條，就知道了，*/  
       /*無序鏈表中的第一個節點離開，以便它插入到有序鏈表中，*/
	    unsort = unsort->next;    
		/*插在第一個節點之前*/ 
		/*sort->data > t->data*/
		/*sort為空 sort->data > t->data*/
        if (sort == phead)  
        {  
			/*整個無序鏈表給phead*/
            phead = t;  
        }  
		/*p是sort的前驅，這樣說不太確切，當sort到最后時，for里面有個sort = sort->next，
		*就會把sort置空，所以要用p暫存上一次sort的值，而且執行判斷sort->data < t->data時，用的也是上一次的sort
		*/
		/*sort后面插入*/
		/*sort遍歷到了最后，此時，sort->data < t->data,sort和p都為最后一個元素，*/ 
        else  
        {  
            p->next = t;  
        }  
		/*if處理之后，t為無序鏈表，因為要在phead前插入，這里先把t賦值給phead，再把t的next指向sort，
		*就完成了在sort之前插入小的元素，很巧妙的一種方法
		*else處理完之后，sort存放的是sort的下一次，真正的sort存放在p中，不滿足條件跳出回圈時，判斷的是下一次的sort，
		但是我們要用的插入的位置為上一次的sort，所以要記錄下sort上一次的位置
		*/
		/*完成插入動作*/
		/*當sort遍歷完成為空時，t->next就是斷開后面的元素（sort為空）*/
		/*當sort不為空時，sort->data > t->data，sort存放的元素比t要大，放在后面，t->next就是再鏈接起來sort*/
        t->next = sort;   
        /*unsort = unsort->next;*/  
    }  
	head = phead;
    return phead;  
}

4.選擇排序

基本思想：首先，找到陣列中最小的那個元素，其次，將它和陣列的第一個元素交換位置(如果第一個元素就是最小元素那么它就和自己交換)，其次，在剩下的元素中找到最小的元素，將它與陣列的第二個元素交換位置，如此往復，直到將整個陣列排序，這種方法我們稱之為選擇排序，
具體步驟：
??1.首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
??2.再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾，
??3.重復第二步，直到所有元素均排序完畢，
時間復雜度：O(N2)
空間復雜度：O(1)
穩定排序：否
原地排序：是
在這里插入圖片描述

Node* SelectSort(Node* phead)                                                
{                                                                                                             
	Node *temp;
	Node *temphead = phead;
	/*將第一次的最大值設定為頭結點*/
	int max = phead->data;
	/*交換變數*/
	 for(int i = 0;i<LengthList(phead);i++)
	 {
		 /*每次遍歷開始前都要把最大值設定為頭結點*/
		  max = phead->data;
		while (temphead->next !=NULL)
		{
			/*尋找最大值*/
			if(max < temphead->next->data)
			{
				max =  temphead->next->data;
			}
			/*移動指標位置*/
			temphead = temphead->next;
		}	
		/*找到最大值的位置*/
		temp = FindList(max);
		/*判斷最大值是否和頭節點相同*/
		if(phead != temp)
		{
			SwapNode(phead,temp);		
		}
		/*更新下一次遍歷的頭結點*/
		temphead = temp->next;
		phead = temphead;
	 }

}

??SwapNode相關代碼如下，當時考慮只需要理解排序思想就好了，就沒有把這個函式的代碼放出來，這個代碼寫的太長太復雜了，有時間我會重新精簡下，（說實話，我都快忘了怎么寫的了）

/*交換相鄰節點*/
void Swanext(Node *p,Node *q)
{
	
	/*中間相鄰節點*/
	if ((p != head)&&(q != head))
	{
		// /*p為前一個節點，q的前驅為p*/
		// /*尋找p的前驅結點*/
		// Node *ppre = FindPreNode(p);
		// Node *temp;
		
		// /*暫存p節點的后繼結點，指向q*/
		// temp = p->next;
		// /*將q節點的后繼節點賦值給p的后繼結點，即將p節點放到了q位置（此時q的前驅節點的next指標還指向的是q）*/
		// p->next = q->next;
		// /*將p節點給q的next，即將完成了q與p的重新連接*/
		// q->next =p;
		// /*找到原來p的前驅節點，指向q，即完成了原來p的前驅結點和q節點的連接*/
		// ppre->next =q;
			if (p->next == q)
			{
				Node *ppre = FindPreNode(p);
				p->next = q->next;
				q->next = p;
				ppre->next = q;
				// PrintList(head);

			}
			else if (q->next == p)
			{
				Node *qpre = FindPreNode(q);
				q->next = p->next;
				p->next = q;
				qpre->next = p;

			}			

	}
	/*頭結點相鄰的交換*/	
	else
	{
		if(p == head)
		{
			p->next = q->next;
			q->next = p;
			head = q;
		}
		else 
		{
			q->next = p->next;
			p->next = q;	
			 head = p;		
		}
	}
	

	


}
/*交換頭結點和任意節點(除尾節點外)*/
void SwapHeadAnother(Node *tmphead,Node *p)
{
	/*尋找p的前驅節點*/
	Node *ppre = FindPreNode(p);
	
	Node *temp;
	if(p!=tmphead->next)
	{
		/*暫存p節點*/
		temp = p->next;
		/*將tmphead節點的后繼節點賦值給p的后繼結點，即將tmphead節點放到了p位置（此時p的前驅節點的next指標還未斷開）*/
		p->next = tmphead->next;
		/*將p的后繼結點賦值給tmphead的后繼結點，同時連接p的前驅和tmphead*/
		tmphead->next = temp;
		ppre->next =tmphead;
		/*新的頭結點回傳給全域head*/
		head = p;
	}

	else
	{
		/*頭結點和下一節點*/
		 tmphead->next = p->next;
		 p->next = tmphead;
		 head = p;
	}


	

}
/*交換尾結點和任意節點(除頭節點外)*/
void SwapEndAnother(Node *tmpend,Node *p)
{
	/*尋找p的前驅節點*/
	Node *ppre = FindPreNode(p);
	Node *endpre = FindPreNode(tmpend);
	Node *temp;
	if((tmpend==end)&&(p!=tmpend))
	{
		/*暫存p節點*/
		temp = p->next;
		/*將tmpend節點的后繼節點賦值給p的后繼結點，即將tmpend節點放到了p位置（此時p的前驅節點的next指標還未斷開）*/
		p->next = tmpend->next;
		endpre->next = p;
		/*將p的后繼結點賦值給tmpend的后繼結點，同時連接p的前驅和tmpend（斷開了之前的連接）*/
		tmpend->next = temp;
		ppre->next =tmpend;
		/*新的頭結點回傳給全域head*/
		end = p;
	}
	else
	{
		p->next = tmpend->next;
		tmpend->next = p;
		end = p;
	}

	

}
/*交換頭結點和尾節點*/
void SwapHeadEnd(Node *tmphead,Node *tmpend)
{
	/*尋找tmpend的前驅節點*/
	Node *endpre = FindPreNode(tmpend);
	Node *temp;
	/*暫存tmpend節點*/
	temp = tmpend->next;
	/*將tmphead節點的后繼節點賦值給tmpend的后繼結點，即將tmpend節點放到了tmphead位置（此時tmpend的前驅節點的next指標還未斷開）*/
	tmpend->next = tmphead->next;
	/*將p的后繼結點賦值給tmpend的后繼結點，同時連接p的前驅和tmpend（斷開了之前的連接）*/
	tmphead->next = temp;
	endpre->next =tmphead;
	/*新的頭結點回傳給全域head*/
	head = tmpend;
	end = tmphead;
	// PrintList(tmpend);
}

void SwapRandom(Node *p,Node *q)
{
	/*除了首尾節點，中間不相鄰的兩個節點*/
	
	if((p->next != q)||(q->next != p))
	{
		/*尋找前驅結點*/
		Node *ppre = FindPreNode(p);
		Node *qpre = FindPreNode(q);
		/*借助一個中間節點傳遞資料域*/
		Node *temp;
		temp = p->next;
		/*交換p和q*/
		/*2、p的新后繼結點要變成q的原后繼結點*/
		p->next = q->next;
		/*3、q的原前趨結點（qpre）的新后繼結點要變成p*/
		qpre->next = p;
		/*4、q的新后繼結點要變成p的原后繼結點（p->next）*/
		q->next = temp;
		/*1、p的原前趨結點（ppre）的新后繼結點要變成q*/
		ppre->next = q;
	}
	/*中間相鄰節點的處理*/
	else if (p->next == q)
	{
		Node *ppre = FindPreNode(p);
		p->next = q->next;
		q->next = p;
		ppre->next = q;

	}
	else if (q->next == p)
	{
		Node *qpre = FindPreNode(q);
		q->next = p->next;
		p->next = q;
		qpre->next = p;

	}
	
}

/*交換任意兩個節點*/
void SwapNode(Node*p, Node*q)
{
	// if(LengthList(head)<2)
	// printf("Can not swap!The Length of list is:%d\r\n ",LengthList(head));
	/*檢查是否是頭尾節點*/
	/*對于頭尾節點有四種情況
	*1.p頭節點和q為中間節點
	*2.p尾節點和q為中間節點
	*3.q頭節點和p為中間節點
	*4.q尾節點和p為中間節點
	*5.p頭結點和q尾節點
	*6.q頭結點和p尾節點
	*7.其他中間交換的情況
	*/
	/*2.兩個節點是否相鄰 除去頭結點和下一節點相鄰的情況，放在headanother處理*/
	if((p->next == q)&&(p !=head)&&(q !=head))
	Swanext(p,q);
	else if((q->next == p)&&(p !=head)&&(q !=head))
	Swanext(q,p);
	/*1.p頭節點和q為中間節點*/
	else if((p == head)&&(q != end))
	SwapHeadAnother(p,q);
	/*2.p尾節點和q為中間節點*/
	else if ((p == end)&&(q != head))
	SwapEndAnother(p,q);
	/*3.q頭節點和p為中間節點*/
	else if((q == head)&&(p != end))
	SwapHeadAnother(q,p);
	/*4.q尾節點和p為中間節點*/
	else if((q == end)&&(p != head))
	SwapEndAnother(q,p);
	/*5.p頭結點和q尾節點*/
	else if((p == head)&&(q == end))
	SwapHeadEnd(p,q);
	/*6.q頭結點和p尾節點*/
	else if((q == head)&&(p == end))
	SwapHeadEnd(q,p);	
	/*7.其他中間交換的情況*/
	else 
	SwapRandom(p,q);	
}

5.歸并排序

基本思想：歸并排序是建立在歸并操作上的一種有效的排序演算法，該演算法是采用分治法（Divide and Conquer）的一個非常典型的應用，
作為一種典型的分而治之思想的演算法應用，歸并排序的實作由兩種方法：
自上而下的遞回（所有遞回的方法都可以用迭代重寫，所以就有了第 2 種方法）；
自下而上的迭代；
具體步驟：
??1.申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列；
??2.設定兩個指標，最初位置分別為兩個已經排序序列的起始位置；
??3.比較兩個指標所指向的元素，選擇相對小的元素放入到合并空間，并移動指標到下一位置；
??4.重復步驟 3 直到某一指標達到序列尾；
??5.將另一序列剩下的所有元素直接復制到合并序列尾，
時間復雜度：O(NlogN)
空間復雜度：O(N)
穩定排序：是
原地排序：否
在這里插入圖片描述

/*獲取鏈表中間元素*/
Node *getMiddleNode(Node *pList)
{
    if (pList == NULL)
    {
        return NULL;
    }
    Node *pfast = pList->next;
    Node *pslow = pList;
    while (pfast != NULL)
    {
         pfast = pfast->next;
         if (pfast != NULL)
         {
             pfast = pfast->next;
             pslow = pslow->next;
         }
 
    }
 
    return pslow;
}
 /*合并有序鏈表，合并之后升序排列*/
Node *MergeList(Node *p1, Node *p2) 
{
    if (NULL == p1)
    {
        return p2;
    }
    if (NULL == p2)
    {
        return p1;
    }
 
    Node *pLinkA = p1;
    Node *pLinkB = p2;
    Node *pTemp = NULL;
	/*較小的為頭結點，pTemp存下頭結點*/
    if (pLinkA->data <= pLinkB->data)
    {
        pTemp = pLinkA;
        pLinkA = pLinkA->next;
    }
    else
    {
        pTemp = pLinkB;
        pLinkB = pLinkB->next;
    }
	/*初始化頭結點，即頭結點指向不為空的結點*/
    Node *pHead = pTemp; 
    while (pLinkA && pLinkB)
    {
        /*合并先放小的元素*/
		if (pLinkA->data <= pLinkB->data)
        {
            pTemp->next = pLinkA;
			/*保存下上一次節點，如果下一次為NULL，保存的上一次的節點就是鏈表最后一個元素*/
            pTemp = pLinkA;
            pLinkA = pLinkA->next;
        }
        else
        {
            pTemp->next = pLinkB;
            pTemp = pLinkB;
            pLinkB = pLinkB->next;
        }
 
    }
	/*跳出回圈時，有一個為空，把不為空的剩下的部分插入鏈表中*/
    pTemp->next = pLinkA ? pLinkA:pLinkB; 
	head = pHead;
    return pHead;
	
}
Node *MergeSort(Node *pList)
{
    if (pList == NULL || pList->next == NULL)
    {
        return pList;
    }
	/*獲取中間結點*/
    Node *pMiddle = getMiddleNode(pList); 
	/*鏈表前半部分，包括中間結點*/
    Node *pBegin = pList; 
	/*鏈表后半部分*/
    Node *pEnd = pMiddle->next;
	/*必須賦值為空 相當于斷開操作，pBegin--pMiddle pEnd---最后 */
    pMiddle->next = NULL; 
	/*排序前半部分資料，只有一個元素的時候停止，即有序*/
    pBegin = MergeSort(pBegin); 
	/*排序后半部分資料 遞回理解可以參考PrintListRecursion;*/
    pEnd = MergeSort(pEnd); 
	/*合并有序鏈表*/
    return MergeList(pBegin, pEnd); 
}

??大家的鼓勵是我繼續創作的動力，如果覺得寫的不錯，歡迎關注，點贊，收藏，轉發，謝謝！
以上代碼均為測驗后的代碼，如有錯誤和不妥的地方，歡迎指出，
圖片來自網路，侵權請聯系我洗掉

如遇到排版錯亂的問題，可以通過以下鏈接訪問我的CSDN，

CSDN:CSDN搜索“嵌入式與Linux那些事”

歡迎歡迎關注我的公眾號：嵌入式與Linux那些事，領取秋招筆試面試大禮包（華為小米等大廠面經，嵌入式知識點總結，筆試題目，簡歷模版等）和2000G學習資料，

轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/235621.html

標籤：其他

上一篇：搭建LAMP平臺

下一篇：詳解雙向鏈表的基本操作(C語言)