|
本篇文章是對(duì)單鏈表的快速排序進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下 單鏈表的快排序和數(shù)組的快排序基本思想相同，同樣是基于劃分，但是又有很大的不同：單鏈表不支持基于下標(biāo)的訪問(wèn)。故書(shū)中把待排序的鏈表拆分為2個(gè)子鏈表。為了簡(jiǎn)單起見(jiàn)，選擇鏈表的第一個(gè)節(jié)點(diǎn)作為基準(zhǔn)，然后進(jìn)行比較，比基準(zhǔn)小得節(jié)點(diǎn)放入左面的子鏈表，比基準(zhǔn)大的放入右邊的子鏈表。在對(duì)待排序鏈表掃描一遍之后，左邊子鏈表的節(jié)點(diǎn)值都小于基準(zhǔn)的值，右邊子鏈表的值都大于基準(zhǔn)的值，然后把基準(zhǔn)插入到鏈表中，并作為連接兩個(gè)子鏈表的橋梁。然后分別對(duì)左、右兩個(gè)子鏈表進(jìn)行遞歸快速排序，以提高性能。但是，由于單鏈表不能像數(shù)組那樣隨機(jī)存儲(chǔ)，和數(shù)組的快排序相比較，還是有一些需要注意的細(xì)節(jié)： 1、支點(diǎn)的選取，由于不能隨機(jī)訪問(wèn)第K個(gè)元素，因此每次選擇支點(diǎn)時(shí)可以取待排序那部分鏈表的頭指針。 2、遍歷量表方式，由于不能從單鏈表的末尾向前遍歷，因此使用兩個(gè)指針?lè)謩e向前向后遍歷的策略實(shí)效， 事實(shí)上，可以可以采用一趟遍歷的方式將較小的元素放到單鏈表的左邊。具體方法為： 1)定義兩個(gè)指針pslow，pfast，其中pslow指向單鏈表的頭結(jié)點(diǎn)，pfast指向單鏈表頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn); 2)使用pfast遍歷單鏈表，每遇到一個(gè)比支點(diǎn)小的元素，就令pslow=pslow->next，然后和pslow進(jìn)行數(shù)據(jù)交換。 3、交換數(shù)據(jù)方式，直接交換鏈表數(shù)據(jù)指針指向的部分，不必交換鏈表節(jié)點(diǎn)本身。 基于上述思想的單鏈表快速排序?qū)崿F(xiàn)如下： 復(fù)制代碼 代碼如下: /** ** 單鏈表的快速排序 ** author :liuzhiwei ** date :2011-08-07 **/ #include<iostream> #include<ctime> using namespace std; //單鏈表節(jié)點(diǎn) struct SList { int data; struct SList* next; }; void bulid_slist(SList** phead, int n) //指向指針的指針 { int i; SList* ptr = *phead; for(i = 0; i < n; ++i) { SList* temp = new SList; temp->data = rand() % n; //產(chǎn)生n個(gè)n以內(nèi)的隨機(jī)數(shù) temp->next = NULL; if(ptr == NULL) { *phead = temp; ptr = temp; } else { ptr->next = temp; ptr = ptr->next; } } } void print_slist(SList* phead) //輸出鏈表 { SList *ptr = phead; while(ptr) { printf("%d ", ptr->data); ptr = ptr->next; } printf("\n"); } void my_swap(int *a,int *b) { int temp; temp=*a; *a=*b; *b=temp; } void sort_slist(SList* phead, SList* pend) //將頭指針為phead，尾指針為pend的鏈表進(jìn)行排序 { if(phead == NULL) return ; if(phead == pend) return ; SList *pslow = phead; SList *pfast = phead->next; SList *ptemp = phead; while(pfast != pend) { if(pfast->data < phead->data) //每次都選擇待排序鏈表的頭結(jié)點(diǎn)作為劃分的基準(zhǔn) { ptemp = pslow; //ptemp始終為pslow的前驅(qū)結(jié)點(diǎn) pslow = pslow->next; my_swap(&pslow->data , &pfast->data); //pslow指針指向比基準(zhǔn)小的結(jié)點(diǎn)組成的鏈表 } pfast = pfast->next; } my_swap(&pslow->data , &phead->data); //此時(shí)pslow指針指向比基準(zhǔn)小的結(jié)點(diǎn)組成的鏈表的最后一個(gè)結(jié)點(diǎn)，也就是基準(zhǔn)的位置，所以要與基準(zhǔn)（head結(jié)點(diǎn)）交換 sort_slist(phead , pslow); //ptemp為左右兩部分分割點(diǎn)（基準(zhǔn)）的前一個(gè)結(jié)點(diǎn) sort_slist(pslow->next , NULL); //右部分是比基準(zhǔn)大的結(jié)點(diǎn)組成的鏈表 } void destroy_slist(SList* phead) { SList* ptr = phead; while(ptr) { SList* temp = ptr; ptr = ptr->next; delete temp; } } int main(void) { srand(time(NULL)); printf("Before sort single list\n"); SList* phead = NULL; bulid_slist(&phead, 100); print_slist(phead); printf("After sort single list\n"); sort_slist(phead, NULL); print_slist(phead); destroy_slist(phead); system("pause"); return 0; } 第二種方法： 選擇鏈表的第一個(gè)節(jié)點(diǎn)作為基準(zhǔn)，然后進(jìn)行比較，比基準(zhǔn)小得節(jié)點(diǎn)放入左面的子鏈表，比基準(zhǔn)大的放入右邊的子鏈表。在對(duì)待排序鏈表掃描一遍之后，左面子鏈表的節(jié)點(diǎn)值都小于基準(zhǔn)的值，右邊子鏈表的值都大于基準(zhǔn)的值，然后把基準(zhǔn)插入到鏈表中，并作為連接兩個(gè)子鏈表的橋梁。然后根據(jù)左、右子鏈表中節(jié)點(diǎn)數(shù)，選擇較小的進(jìn)行遞歸快速排序，而對(duì)數(shù)目較多的則進(jìn)行迭代排序。 排序函數(shù)中使用的變量如下： 復(fù)制代碼 代碼如下: struct node *right; //右邊子鏈表的第一個(gè)節(jié)點(diǎn) struct node **left_walk, **right_walk; //作為指針，把其指向的節(jié)點(diǎn)加入到相應(yīng)的子鏈表中 struct node *pivot, *old; //pivot為基準(zhǔn), old為循環(huán)整個(gè)待排序鏈表的指針 核心代碼如下： for (old = (*head)->next; old != end; old = old->next) { if (old->data < pivot->data) { //小于基準(zhǔn),加入到左面的子鏈表,繼續(xù)比較 ++left_count; *left_walk = old; //把該節(jié)點(diǎn)加入到左邊的鏈表中， left_walk = &(old->next); } else { //大于基準(zhǔn),加入到右邊的子鏈表，繼續(xù)比較 ++right_count; *right_walk = old; right_walk = &(old->next); } } head為struct node **類(lèi)型，指向鏈表頭部，end指向鏈表尾部，可為NULL，這段程序的重點(diǎn)在于指針的指針的用法，*left_walk為一個(gè)指向node節(jié)點(diǎn)的指針，說(shuō)的明白點(diǎn)*left_walk的值就是node節(jié)點(diǎn)的內(nèi)存地址，其實(shí)還有一個(gè)地方也有node的地址，那就是指向node的節(jié)點(diǎn)的next域，故我們可以簡(jiǎn)單的認(rèn)為*left_walk = old就是把指向node節(jié)點(diǎn)的節(jié)點(diǎn)的next域改為節(jié)點(diǎn)old的地址，這樣可能造成兩種情況：一種就是*left_walk本來(lái)就指向old節(jié)點(diǎn)，這樣就沒(méi)有改變?nèi)魏胃淖?，另一種則是改變了*right_walk指向節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的next域，使其指向后部的節(jié)點(diǎn)，中間跳過(guò)了若干個(gè)節(jié)點(diǎn)，不過(guò)在這里這樣做并不會(huì)造成任何問(wèn)題，因?yàn)殒湵碇械墓?jié)點(diǎn)要么加入到左面的子鏈表中，要么加入到右面的子鏈表中，不會(huì)出現(xiàn)節(jié)點(diǎn)丟失的情況。 下面用圖示說(shuō)明下上面的問(wèn)題：
復(fù)制代碼 代碼如下: #include <stdio.h> #include <stdlib.h> #include <time.h> //鏈表節(jié)點(diǎn) struct node { int data; struct node *next; }; //鏈表快排序函數(shù) void QListSort(struct node **head,struct node *h); //打印鏈表 void print_list(struct node *head) { struct node *p; for (p = head; p != NULL; p = p->next) { printf("%d ", p->data); } printf("\n"); } int main(void) { struct node *head = NULL; struct node *p; int i; /** * 初始化鏈表 */ srand((unsigned)time(NULL)); for (i = 1; i < 11; ++i) { p = (struct node*)malloc(sizeof(struct node)); p->data = rand() % 100 + 1; if(head == NULL) { head = p; head->next = NULL; } else { p->next = head->next; head->next = p; } } print_list(head); printf("---------------------------------\n"); QListSort(&head,NULL); print_list(head); system("pause"); return 0; } void QListSort(struct node **head, struct node *end) { struct node *right; struct node **left_walk, **right_walk; struct node *pivot, *old; int count, left_count, right_count; if (*head == end) return; do { pivot = *head; left_walk = head; right_walk = &right; left_count = right_count = 0; //取第一個(gè)節(jié)點(diǎn)作為比較的基準(zhǔn)，小于基準(zhǔn)的在左面的子鏈表中， //大于基準(zhǔn)的在右邊的子鏈表中 for (old = (*head)->next; old != end; old = old->next) { if (old->data < pivot->data) { //小于基準(zhǔn),加入到左面的子鏈表,繼續(xù)比較 ++left_count; *left_walk = old; //把該節(jié)點(diǎn)加入到左邊的鏈表中， left_walk = &(old->next); } else { //大于基準(zhǔn),加入到右邊的子鏈表，繼續(xù)比較 ++right_count; *right_walk = old; right_walk = &(old->next); } } //合并鏈表 *right_walk = end; //結(jié)束右鏈表 *left_walk = pivot; //把基準(zhǔn)置于正確的位置上 pivot->next = right; //把鏈表合并 //對(duì)較小的子鏈表進(jìn)行快排序，較大的子鏈表進(jìn)行迭代排序。 if(left_walk > right_walk) { QListSort(&(pivot->next), end); end = pivot; count = left_count; } else { QListSort(head, pivot); head = &(pivot->next); count = right_count; } } while (count > 1); } |
|
|
來(lái)自： 復(fù)雜網(wǎng)絡(luò)621 > 《C語(yǔ)言》
