以下是数组快速排序的典型递归实现。该实现使用最后一个元素作为枢轴
int partition (int arr[], int l, int h) { int x = arr[h]; int i = (l - 1); for (int j = l; j <= h- 1; j++) { if (arr[j] <= x) { i++; swap (&arr[i], &arr[j]); } } swap (&arr[i + 1], &arr[h]); return (i + 1); } void quickSort(int A[], int l, int h) { if (l < h) { int p = partition(A, l, h); /* Partitioning index */ quickSort(A, l, p - 1); quickSort(A, p + 1, h); } }
我们可以对链表使用相同的算法吗？
以下是双向链表的 C++ 实现。思路很简单，我们先找出指向最后一个节点的指针。一旦我们有了指向最后一个节点的指针，我们就可以使用指向链表的第一个和最后一个节点的指针对链表进行递归排序，类似于上面我们传递第一个和最后一个数组元素的索引的递归函数。链表的分区函数也类似于数组的分区。它不返回枢轴元素的索引，而是返回一个指向枢轴元素的指针。在下面的实现中，quickSort()只是一个包装函数，主要的递归函数是_quickSort()，类似于quickSort()的数组实现。
#include <bits/stdc++.h> using namespace std; class Node { public: int data; Node *next; Node *prev; }; void swap ( int* a, int* b ) { int t = *a; *a = *b; *b = t; } Node *lastNode(Node *root) { while (root && root->next) root = root->next; return root; } Node* partition(Node *l, Node *h) { int x = h->data; Node *i = l->prev; for (Node *j = l; j != h; j = j->next) { if (j->data <= x) { i = (i == NULL)? l : i->next; swap(&(i->data), &(j->data)); } } i = (i == NULL)? l : i->next; swap(&(i->data), &(h->data)); return i; } void _quickSort(Node* l, Node *h) { if (h != NULL && l != h && l != h->next) { Node *p = partition(l, h); _quickSort(l, p->prev); _quickSort(p->next, h); } } void quickSort(Node *head) { Node *h = lastNode(head); _quickSort(head, h); } void printList(Node *head) { while (head) { cout << head->data << " "; head = head->next; } cout << endl; } void push(Node** head_ref, int new_data) { Node* new_node = new Node; new_node->data = new_data; new_node->prev = NULL; new_node->next = (*head_ref); if ((*head_ref) != NULL) (*head_ref)->prev = new_node ; (*head_ref) = new_node; } /* Driver code */ int main() { Node *a = NULL; push(&a, 5); push(&a, 20); push(&a, 4); push(&a, 3); push(&a, 30); cout << "排序前的链表 \n"; printList(a); quickSort(a); cout << "排序后的链表 \n"; printList(a); return 0; }
输出 ：
排序前的链表 30 3 4 20 5 排序后的链表 3 4 5 20 30
时间复杂度： 上述实现的时间复杂度与数组 QuickSort() 的时间复杂度相同。在最坏情况下需要 O(n^2) 时间，在平均和最佳情况下需要 O(nLogn) 时间。最坏的情况发生在链表已经排序时。
我们可以为链表实现随机快速排序吗？
只有当我们可以选择一个固定点作为枢轴时（如上述实现中的最后一个元素），才能为链表实现快速排序。随机快速排序不能通过选择随机主元有效地为链表实现。
