轉自別人:https://www.cnblogs.com/xiaoxuanzhi/p/4445152.html
c++版：
由于c++是包括了c語言，所以上面的快排，在c++中依然能運行通過。
這里，我來介紹一下C++中更好地辦法去排序。
1、使用多載運算子，達到給結構體新的比較方法，來實作排序的目的。說白了就是創建結構體，定義兩個結構體比較的時候，是按哪個欄位比較。直接上代碼：
注意：c++中可以不帶typedef 來給結構體"披外套.
struct Node
{
int age;
itn height;
int width;
bool operator<(struct Node b) const //這里必須加上const
{
return age < b.age;
}
};
經過上面的定義后，接著寫
Node a, b; 并給欄位賦過值后，再比較a<b. 含義就是a.age < b.age了。
這樣的話，上面的快速排序的代碼，就不用特意指定按age排序了。結構體可以直接賦值，這里就不用多載=號了。
交換代碼和上面的一樣。改寫上面的快速排序代碼：
void QuickSort(ElemType *a, int left, int right)
{
if(left < right)
{
ElemType temp = a[right]; //這里不用指定是age，具有通用型。
int i = left-1;
int j = left;
while(j < right)
{
if(a[j] < a[right])
{
++i;
Swap(&a[j],&a[i]);
}
j++;
}
Swap(&a[i+1],&a[right]);
int r = i+1;
QuickSort(a, left, r-1);
QuickSort(a, r+1, right);
}
}
2、使用sort，同樣c++中也有特有的排序函式，sort,它的內部是很多高效率的排序演算法的整合，根據待排序的資料量選擇不同的排序方法，是時間最優。
該函式位于頭檔案#include <algorithm.h>中。
函式原型:使用了模板類， 就是第三個引數(自定義排序方式)是可選的。
template< class RandomIt >
void sort( RandomIt first, RandomIt last ) (1);
template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp ); (2)
sort使用的c++中的模板template， 就可以對任何定義了比較關系的集合進行排序了。模板類，相當于純面向物件語言，如c#和Java，中的泛型概念。
如何使用sort?
1、配合結構體中的多載一起使用：
我們在上面定義了多載’<‘運算子的結構體，就可以直接用sort排序了。
直接sort(node,node+n);兩個引數，相當于陣列的始末指標。
不過注意，這里是按從小到大的順序排的，因為上面多載的時候是<對<號，如果多載小于號的時候，在函式體內寫的卻是age>b.age,結果就是從大到小排序了。
2、不使用結構體運算子的多載，使用sort的第三個引數(自定義排序方法)來實作排序的效果。
bool cmp(ElemType a, ElemType b)
{
return a.age > b.age;
}
這樣的話主函式里用的時候寫sort(a,a+n,cmp);就能排序了。
二、鏈式表的排序
單鏈表不適合快速排序，雙向鏈表才適合快速排序，這里我們用選擇排序法排序單鏈表，用快速排序法，排序雙向鏈表：
單鏈表
定義單鏈表：
typedef struct LinkNode
{
DataType data;
struct LinkNode *next; //指向后繼節點
}Linknode;
有關選擇排序的知識，請看這里：wikipedia:選擇排序；
直接上代碼：
void Sort(LinkNode *L)
{
LinkNode *p = L->next;
LinkNode *min = p;
while(p)
{
min = p;
LinkNode *q = L->next;
while(q)
{
if(q->data < min->data)
{
min = q;
}
q = q->next;
}
Swap(p, min); //這里很關鍵，如何交換兩個節點的值，而不改變節點的指標指向？
p = p->next;
}
}
下面畫圖來解釋：
實際代碼：
inline void Swap(LinkNode *p, Linknode *q)
{
LinkNode temp = *p;
temp.next = q->next;
q->next = p->next;
*p = *q;
*q = temp;
}
雙向鏈表實作快速排序
1、雙向鏈表定義：
struct Node
{
int data;
struct Node *pri, *next;
};
2、新建雙鏈表
Node* CreateDulNode(int *a, int n) //將陣列元素存到鏈表中
{
Node *head = (Node*)malloc(sizeof(Node));
head->next = NULL;
head->pri = NULL;
Node *p = head;
int i = 0;
Node *q = NULL;
while (i<n)
{
q = (Node*)malloc(sizeof(Node));
q->data = a[i];
q->next = p->next;
q->pri = p;
p->next = q;
p = q;
i++;
}
q->next = head;
head->pri = q;
return head;
}
3、快速排序 //其實就是陣列的排序原理，有些小細節要注意
//呼叫QuickSort(L->next, L->pri);
void QuickSort(Node *Left, Node* right) //閉區間
{
if (Left->pri != right) //這里當right在left左邊是結束
{
Node *temp = right;
Node *p = Left->pri;
Node *q = Left;
while (q != right)
{
if (q->data < temp->data)
{
p = p->next;
Swap(p, q);
}
q = q->next;
}
p = p->next;
Swap(p, temp);
// OutPut2(Left,right); //測驗輸出函式
QuickSort(Left, p->pri);
QuickSort(p->next, right);
}
}
4、關鍵的交換函式，不過也和單鏈表的交換差不多了
void Swap(Node *p, Node *q)
{
Node temp = *p;
temp.next = q->next;
temp.pri = q->pri;
q->next = p->next;
q->pri = p->pri;
*p = *q;
*q = temp;
}
5、測驗輸出函式
void OutPut2(Node *Left, Node *right)
{
Node *p = Left;
while (p!=right)
{
cout << p->data << " ";
p = p->next;
}
cout << right->data << " "; //單獨輸出最后一個
cout << endl;
}
實驗結果：
總結: 以前排序都是在陣列上排序，現在學了鏈表，也想實作快速排序。總之，本質上沒啥區別，演算法流程都差不多，只是操作上的不同。
uj5u.com熱心網友回復：
這里是sqlserver論壇。筆記性的知識， 建議寫到個人博客 ， 謝謝
uj5u.com熱心網友回復：
好的好的 抱歉抱歉
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/109029.html
標籤：新技術前沿
上一篇：自動化本科生選擇方向
下一篇：程式小白