一、鏈表排序

鏈表分為單鏈表和雙鏈表，雙鏈表的排序適合快速排序，這個(gè)在c語言庫(kù)函數(shù)中使用sort進(jìn)行了實(shí)現(xiàn)。但是單鏈表并不適合使用快速排序。因此我們可以使用插入排序、選擇排序、冒泡排序等方法。注意：鏈表不一定會(huì)有頭結(jié)點(diǎn)，但是一定會(huì)有一個(gè)頭指針。特別是如何在不改變?cè)湵碇羔樦赶虻那闆r下交換兩個(gè)節(jié)點(diǎn)

1、選擇排序

選擇排序的思路：選出一個(gè)數(shù)，假定它是最小/最大值，然后與無序隊(duì)列中的元素進(jìn)行比較，直到找出最小值，然后交換數(shù)據(jù)。

具體做法：重新定義兩個(gè)鏈表指針，一個(gè)指針指向當(dāng)前操作的鏈表節(jié)點(diǎn)，取名為p，另一個(gè)取名為min，指向本輪排序中數(shù)值最小的節(jié)點(diǎn)。與數(shù)組排序不同的是，數(shù)組是記錄最小值元素的下標(biāo)，這里是記錄數(shù)值最小的節(jié)點(diǎn)的指針。

這里需要注意傳入的鏈表是否有頭結(jié)點(diǎn)，一般有頭結(jié)點(diǎn)的鏈表會(huì)在創(chuàng)建鏈表時(shí)創(chuàng)建一個(gè)頭結(jié)點(diǎn)（數(shù)據(jù)域無效或者存儲(chǔ)鏈表節(jié)點(diǎn)數(shù)）。

2、插入法排序

思路：創(chuàng)建一個(gè)有序數(shù)列，從原來的無序數(shù)列中取出一個(gè)數(shù)，插入有序數(shù)列中。

具體做法：鏈表中需要?jiǎng)?chuàng)建一個(gè)新的鏈表，用來保存排序好的鏈表節(jié)點(diǎn)。同樣的，這里也需要定義一個(gè)cur指針，指向原鏈表當(dāng)前被操作的節(jié)點(diǎn)，sortCur指向有序鏈表的當(dāng)前被操作的節(jié)點(diǎn)。prev指向當(dāng)前被操作的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)。與選擇法不同的是，這里是新節(jié)點(diǎn)插入鏈表，而不是兩個(gè)節(jié)點(diǎn)的數(shù)據(jù)交換。