深入單鏈表的快速排序詳解
更新時間：2013年05月24日 12:57:12 作者：
本篇文章是對單鏈表的快速排序進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下
單鏈表的快排序和數(shù)組的快排序基本思想相同，同樣是基于劃分，但是又有很大的不同：單鏈表不支持基于下標(biāo)的訪問。故書中把待排序的鏈表拆分為2個子鏈表。為了簡單起見，選擇鏈表的第一個節(jié)點作為基準(zhǔn)，然后進(jìn)行比較，比基準(zhǔn)小得節(jié)點放入左面的子鏈表，比基準(zhǔn)大的放入右邊的子鏈表。在對待排序鏈表掃描一遍之后，左邊子鏈表的節(jié)點值都小于基準(zhǔn)的值，右邊子鏈表的值都大于基準(zhǔn)的值，然后把基準(zhǔn)插入到鏈表中，并作為連接兩個子鏈表的橋梁。然后分別對左、右兩個子鏈表進(jìn)行遞歸快速排序，以提高性能。
但是，由于單鏈表不能像數(shù)組那樣隨機(jī)存儲，和數(shù)組的快排序相比較，還是有一些需要注意的細(xì)節(jié)：
1、支點的選取，由于不能隨機(jī)訪問第K個元素，因此每次選擇支點時可以取待排序那部分鏈表的頭指針。
2、遍歷量表方式，由于不能從單鏈表的末尾向前遍歷，因此使用兩個指針分別向前向后遍歷的策略實效，
事實上，可以可以采用一趟遍歷的方式將較小的元素放到單鏈表的左邊。具體方法為：
1)定義兩個指針pslow，pfast，其中pslow指向單鏈表的頭結(jié)點，pfast指向單鏈表頭結(jié)點的下一個結(jié)點;
2)使用pfast遍歷單鏈表，每遇到一個比支點小的元素，就令pslow=pslow->next，然后和pslow進(jìn)行數(shù)據(jù)交換。
3、交換數(shù)據(jù)方式，直接交換鏈表數(shù)據(jù)指針指向的部分，不必交換鏈表節(jié)點本身。
基于上述思想的單鏈表快速排序?qū)崿F(xiàn)如下：
/**
** 單鏈表的快速排序
** author :liuzhiwei
** date :2011-08-07
**/
#include<iostream>
#include<ctime>
using namespace std;
//單鏈表節(jié)點
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個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é)點作為劃分的基準(zhǔn)
{
ptemp = pslow; //ptemp始終為pslow的前驅(qū)結(jié)點
pslow = pslow->next;
my_swap(&pslow->data , &pfast->data); //pslow指針指向比基準(zhǔn)小的結(jié)點組成的鏈表
}
pfast = pfast->next;
}
my_swap(&pslow->data , &phead->data); //此時pslow指針指向比基準(zhǔn)小的結(jié)點組成的鏈表的最后一個結(jié)點，也就是基準(zhǔn)的位置，所以要與基準(zhǔn)（head結(jié)點）交換
sort_slist(phead , pslow); //ptemp為左右兩部分分割點（基準(zhǔn)）的前一個結(jié)點
sort_slist(pslow->next , NULL); //右部分是比基準(zhǔn)大的結(jié)點組成的鏈表
}
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;
}
第二種方法：
選擇鏈表的第一個節(jié)點作為基準(zhǔn)，然后進(jìn)行比較，比基準(zhǔn)小得節(jié)點放入左面的子鏈表，比基準(zhǔn)大的放入右邊的子鏈表。在對待排序鏈表掃描一遍之后，左面子鏈表的節(jié)點值都小于基準(zhǔn)的值，右邊子鏈表的值都大于基準(zhǔn)的值，然后把基準(zhǔn)插入到鏈表中，并作為連接兩個子鏈表的橋梁。然后根據(jù)左、右子鏈表中節(jié)點數(shù)，選擇較小的進(jìn)行遞歸快速排序，而對數(shù)目較多的則進(jìn)行迭代排序。
排序函數(shù)中使用的變量如下：
struct node *right; //右邊子鏈表的第一個節(jié)點
struct node **left_walk, **right_walk; //作為指針，把其指向的節(jié)點加入到相應(yīng)的子鏈表中
struct node *pivot, *old; //pivot為基準(zhǔn), old為循環(huán)整個待排序鏈表的指針
核心代碼如下：
for (old = (*head)->next; old != end; old = old->next) {
if (old->data < pivot->data) { //小于基準(zhǔn),加入到左面的子鏈表,繼續(xù)比較
++left_count;
*left_walk = old; //把該節(jié)點加入到左邊的鏈表中，
left_walk = &(old->next);
} else { //大于基準(zhǔn),加入到右邊的子鏈表，繼續(xù)比較
++right_count;
*right_walk = old;
right_walk = &(old->next);
}
}
head為struct node **類型，指向鏈表頭部，end指向鏈表尾部，可為NULL，這段程序的重點在于指針的指針的用法，*left_walk為一個指向node節(jié)點的指針，說的明白點*left_walk的值就是node節(jié)點的內(nèi)存地址，其實還有一個地方也有node的地址，那就是指向node的節(jié)點的next域，故我們可以簡單的認(rèn)為*left_walk = old就是把指向node節(jié)點的節(jié)點的next域改為節(jié)點old的地址，這樣可能造成兩種情況：一種就是*left_walk本來就指向old節(jié)點，這樣就沒有改變?nèi)魏胃淖儯硪环N則是改變了*right_walk指向節(jié)點的前一個節(jié)點的next域，使其指向后部的節(jié)點，中間跳過了若干個節(jié)點，不過在這里這樣做并不會造成任何問題，因為鏈表中的節(jié)點要么加入到左面的子鏈表中，要么加入到右面的子鏈表中，不會出現(xiàn)節(jié)點丟失的情況。
下面用圖示說明下上面的問題：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
//鏈表節(jié)點
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;
//取第一個節(jié)點作為比較的基準(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é)點加入到左邊的鏈表中，
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; //把鏈表合并
//對較小的子鏈表進(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);
}
但是，由于單鏈表不能像數(shù)組那樣隨機(jī)存儲，和數(shù)組的快排序相比較，還是有一些需要注意的細(xì)節(jié)：
1、支點的選取，由于不能隨機(jī)訪問第K個元素，因此每次選擇支點時可以取待排序那部分鏈表的頭指針。
2、遍歷量表方式，由于不能從單鏈表的末尾向前遍歷，因此使用兩個指針分別向前向后遍歷的策略實效，
事實上，可以可以采用一趟遍歷的方式將較小的元素放到單鏈表的左邊。具體方法為：
1)定義兩個指針pslow，pfast，其中pslow指向單鏈表的頭結(jié)點，pfast指向單鏈表頭結(jié)點的下一個結(jié)點;
2)使用pfast遍歷單鏈表，每遇到一個比支點小的元素，就令pslow=pslow->next，然后和pslow進(jìn)行數(shù)據(jù)交換。
3、交換數(shù)據(jù)方式，直接交換鏈表數(shù)據(jù)指針指向的部分，不必交換鏈表節(jié)點本身。
基于上述思想的單鏈表快速排序?qū)崿F(xiàn)如下：
復(fù)制代碼 代碼如下:
/**
** 單鏈表的快速排序
** author :liuzhiwei
** date :2011-08-07
**/
#include<iostream>
#include<ctime>
using namespace std;
//單鏈表節(jié)點
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個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é)點作為劃分的基準(zhǔn)
{
ptemp = pslow; //ptemp始終為pslow的前驅(qū)結(jié)點
pslow = pslow->next;
my_swap(&pslow->data , &pfast->data); //pslow指針指向比基準(zhǔn)小的結(jié)點組成的鏈表
}
pfast = pfast->next;
}
my_swap(&pslow->data , &phead->data); //此時pslow指針指向比基準(zhǔn)小的結(jié)點組成的鏈表的最后一個結(jié)點，也就是基準(zhǔn)的位置，所以要與基準(zhǔn)（head結(jié)點）交換
sort_slist(phead , pslow); //ptemp為左右兩部分分割點（基準(zhǔn)）的前一個結(jié)點
sort_slist(pslow->next , NULL); //右部分是比基準(zhǔn)大的結(jié)點組成的鏈表
}
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;
}
第二種方法：
選擇鏈表的第一個節(jié)點作為基準(zhǔn)，然后進(jìn)行比較，比基準(zhǔn)小得節(jié)點放入左面的子鏈表，比基準(zhǔn)大的放入右邊的子鏈表。在對待排序鏈表掃描一遍之后，左面子鏈表的節(jié)點值都小于基準(zhǔn)的值，右邊子鏈表的值都大于基準(zhǔn)的值，然后把基準(zhǔn)插入到鏈表中，并作為連接兩個子鏈表的橋梁。然后根據(jù)左、右子鏈表中節(jié)點數(shù)，選擇較小的進(jìn)行遞歸快速排序，而對數(shù)目較多的則進(jìn)行迭代排序。
排序函數(shù)中使用的變量如下：
復(fù)制代碼 代碼如下:
struct node *right; //右邊子鏈表的第一個節(jié)點
struct node **left_walk, **right_walk; //作為指針，把其指向的節(jié)點加入到相應(yīng)的子鏈表中
struct node *pivot, *old; //pivot為基準(zhǔn), old為循環(huán)整個待排序鏈表的指針
核心代碼如下：
for (old = (*head)->next; old != end; old = old->next) {
if (old->data < pivot->data) { //小于基準(zhǔn),加入到左面的子鏈表,繼續(xù)比較
++left_count;
*left_walk = old; //把該節(jié)點加入到左邊的鏈表中，
left_walk = &(old->next);
} else { //大于基準(zhǔn),加入到右邊的子鏈表，繼續(xù)比較
++right_count;
*right_walk = old;
right_walk = &(old->next);
}
}
head為struct node **類型，指向鏈表頭部，end指向鏈表尾部，可為NULL，這段程序的重點在于指針的指針的用法，*left_walk為一個指向node節(jié)點的指針，說的明白點*left_walk的值就是node節(jié)點的內(nèi)存地址，其實還有一個地方也有node的地址，那就是指向node的節(jié)點的next域，故我們可以簡單的認(rèn)為*left_walk = old就是把指向node節(jié)點的節(jié)點的next域改為節(jié)點old的地址，這樣可能造成兩種情況：一種就是*left_walk本來就指向old節(jié)點，這樣就沒有改變?nèi)魏胃淖儯硪环N則是改變了*right_walk指向節(jié)點的前一個節(jié)點的next域，使其指向后部的節(jié)點，中間跳過了若干個節(jié)點，不過在這里這樣做并不會造成任何問題，因為鏈表中的節(jié)點要么加入到左面的子鏈表中，要么加入到右面的子鏈表中，不會出現(xiàn)節(jié)點丟失的情況。
下面用圖示說明下上面的問題：
這里假設(shè)鏈表的值一次是5、2、4、6、1。根據(jù)程序首先head = left_walk指向值為5的節(jié)點，old指向值為2的節(jié)點，2小于5，所以加入2到左面的子鏈表中，*left_walk=old，我們知道，*left_walk指向的是第一個節(jié)點，這樣做改變了head指針值，使其指向第二個節(jié)點，然后left_walk后移，old后移，4同樣小于5，故繼續(xù)上述操作，但是這是*left_walk和old指向的是同一個節(jié)點，沒有引起任何變化，left_walk和old后移，6大于5，這時不同就出現(xiàn)了，要把其加入到右邊的子鏈表中，故是*right_walk = old，其實right_walk初試化為&right，這句話相當(dāng)于right = old，即令old當(dāng)前指向的節(jié)點作為右邊子鏈表的第一個節(jié)點，以后大于基準(zhǔn)的節(jié)點都要加入到這個節(jié)點中，且總是加入到尾部。此時right_walk,和old后移，1小于5應(yīng)該加入到左邊的子鏈表中，*left_walk = old，此時*left_walk指向6，故此語句的作用是更改節(jié)點4的next值，把其改為1的地址，這樣6就從原來的鏈表中脫鉤了，繼續(xù)left_walk和old后移到9節(jié)點，應(yīng)加入到右邊的子鏈表中，此時*right_walk指向1，故把9節(jié)點加入到6節(jié)點的后面。
這就是基本的排序過程，然而有一個問題需要搞明白，比如有節(jié)點依次為struct node *a, *b, *c，node **p , p = &b，如果此時令*p = c，即實際效果是a->next = c；我們知道這相當(dāng)于該a的next域的值。而p僅僅是一個指針的指針，它是指向b所指向的節(jié)點的地址的指針，那么當(dāng)我們更改*p的值的時候怎么會改到了a的next呢(這個可以寫程序驗證下，確實如此)？其實并非如此，我們仔細(xì)的看看程序，left_walk初始化為head，那么第一次執(zhí)行*left_walk是把head指向了左邊鏈表的起始節(jié)點，然后left_walk被賦值為&(old->next)，這句話就有意思了，我們看一看下面在執(zhí)行*left_walk=old時的情況，可以簡單的來個等價替換，*left_walk = old也就相當(dāng)于*&(old->next) = old，即old->nex = old，不過這里的old可不一定是old->next所指向的節(jié)點，應(yīng)為left_walk和right_walk都指向它們的old節(jié)點，但是卻是不同的。
算法到這里并沒有完，這只是執(zhí)行了一次劃分，把基準(zhǔn)放入了正確的位置，還要繼續(xù)，不過下面的就比較簡單了，就是遞歸排序個數(shù)比較小的子鏈表，迭代處理節(jié)點數(shù)目比較大的子鏈表。
完整的代碼如下：
復(fù)制代碼 代碼如下:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
//鏈表節(jié)點
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;
//取第一個節(jié)點作為比較的基準(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é)點加入到左邊的鏈表中，
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; //把鏈表合并
//對較小的子鏈表進(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);
}
相關(guān)文章
在Qt項目中使用Protobuf（Protocol Buffers）可以有效地處理數(shù)據(jù)序列化和反序列化,以下是如何在Qt項目中配置和編譯Protobuf的詳細(xì)步驟,感興趣的朋友一起看看吧2024-07-07
Visual Studio Community 2022(VS2022)安裝圖文方法
這篇文章主要介紹了Visual Studio Community 2022(VS2022)安裝方法,本文分步驟通過圖文并茂的形式給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-09-09
本文主要介紹了C++?高精度乘法運(yùn)算的實現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-01-01
這篇文章主要為大家詳細(xì)介紹了OpenGL通過中點法繪制直線和圓，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-02-02
C++實現(xiàn)LeetCode(169.求大多數(shù))
這篇文章主要介紹了C++實現(xiàn)LeetCode(169.求大多數(shù)),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08
這篇文章主要介紹了淺談C++中virtual的三種用法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-07-07
OpenCV利用K-means實現(xiàn)根據(jù)顏色進(jìn)行圖像分割
K-means是一種經(jīng)典的無監(jiān)督聚類算法---不需要人工干預(yù)。本文將通過K-means算法實現(xiàn)根據(jù)顏色進(jìn)行圖像分割的效果，感興趣的小伙伴可以嘗試一下2022-10-10
這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)簡單的猜數(shù)字游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-01-01
Qt 中 isHidden 和 isVisible 的區(qū)別與使用小結(jié)
Qt 中的 isHidden() 和 isVisible() 方法都用于查詢組件顯示或隱藏狀態(tài),然而,它們有很大的區(qū)別,了解它們對于正確操作組件致關(guān)重要,下面給大家介紹Qt 中 isHidden 和 isVisible 的區(qū)別與使用,感興趣的朋友一起看看吧2025-03-03
關(guān)于C++內(nèi)存中字節(jié)對齊問題的詳細(xì)介紹
本篇文章是對C++內(nèi)存中字節(jié)對齊的問題進(jìn)行了詳細(xì)的分析與總結(jié)。需要的朋友參考下2013-05-05