本文总结了六种经典排序算法，除堆排序外还给出了单链表的实现，单链表的结点结构与 LeetCode 一致：
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
本文涉及的所有题目及实现代码下载链接为 — http://xule.ren/wp-content/uploads/2018/04/sorting.zip
Insertion Sort
Array
void insertionSort(std::vector<int>& A)
{
int n = static_cast<int>(A.size());
for (int i = 1, j = 0; i < n; ++i)
{
int num = A[i];
for (j = i; j > 0 && A[j-1] > num; --j)
A[j] = A[j-1];
A[j] = num;
}
}
List
ListNode* insertionSortList(ListNode *head)
{
if (head == NULL || head->next == NULL)
return head;
ListNode preHead(0);
preHead.next = head;
ListNode *p = NULL, *q = head; // q is the tail of ordered sequence
while (q->next != NULL)
{
p = &preHead;
while (p->next != q && p->next->val < q->next->val)
p = p->next;
// insert to tail means no need to insert
if (p->next == q && q->val <= q->next->val)
q = q->next;
// 0 -> 3 -> 6 -> 8 -> 1 -> 2 or 0 -> 3 -> 6 -> 8 -> 7 -> 2
// p q r or p q r
else // insert q->next between p and p->next
{
ListNode *r = q->next;
q->next = r->next;
r->next = p->next;
p->next = r;
}
}
return preHead.next;
}
插入排序的最大优势就是当输入序列基本有序时可以达到接近线性的时间复杂度，插入排序是稳定的。
Bubble Sort
Array
void bubbleSort(std::vector<int>& A)
{
int n = static_cast<int>(A.size());
for (int i = 0; i < n-1; ++i)
{
bool finish = true;
for (int j = 0; j < n-i-1; ++j)
{
if (A[j] > A[j+1])
{
std::swap(A[j], A[j+1]);
finish = false;
}
}
if (finish)
break;
}
}
List
ListNode* bubbleSortList(ListNode *head)
{
if (head == NULL || head->next == NULL)
return head;
ListNode preHead(0);
preHead.next = head;
// tail->prev is the tail of unordered sequence
ListNode *p = &preHead, *q = p->next, *tail = NULL;
for (; q->next != tail; p = &preHead, q = p->next)
{
bool finish = true;
while (q->next != tail)
{
if (p->next->val > q->next->val)
{
ListNode *r = q->next;
q->next = r->next;
r->next = q;
p->next = r;
finish = false;
}
else
q = q->next;
p = p->next;
}
tail = q;
if (finish)
break;
}
return preHead.next;
}
布尔标志 finish 用于指示某一趟排序中是否未发生交换，若为真则表示序列已经排好序了，采用了 finish 标志，在输入有序的情况下只需要 O(n) 的时间，冒泡排序是稳定的。
Selection Sort
Array
void selectionSort(std::vector<int>& A)
{
int n = static_cast<int>(A.size());
for (int i = 0; i < n-1; ++i)
{
int minJ = i, min = A[i];
for (int j = i+1; j < n; ++j)
{
if (min > A[j])
{
min = A[j];
minJ = j;
}
}
std::swap(A[i], A[minJ]);
}
}
List
ListNode* selectionSortList(ListNode *head)
{
if (head == NULL || head->next == NULL)
return head;
ListNode preHead(0);
// p is the tail of ordered sequence, q is the head of unordered sequence
ListNode *p = &preHead, *q = head;
while (q != NULL)
{
ListNode *preMin = NULL, *min = q;
for (ListNode *r = q; r->next != NULL; r = r->next)
{
if (min->val > r->next->val)
{
preMin = r;
min = r->next;
}
}
if (min != q)
preMin->next = min->next;
else
q = q->next;
p = p->next = min;
}
return preHead.next;
}
选择排序在最好的输入情况下也需要 O(n^2) 时间，选择排序是不稳定的。
对于单链表，针对 LeetCode 147 的测试用例三类简单排序算法的性能如下，插入排序 58ms，冒泡排序 80ms，选择排序 104ms，插入排序的性能是最好的。
Quick Sort
Array
partition (two ways)
int partition(std::vector<int>& A, int lo, int hi)
{
// int r = rand() % (hi - lo + 1) + lo;
// std::swap(A[r], A[hi]);
int pivot = A[hi], i = lo;
for (int j = lo; j < hi; ++j)
if (A[j] <= pivot)
std::swap(A[i++], A[j]);
std::swap(A[i], A[hi]);
return i;
}
int partition(std::vector<int>& A, int lo, int hi)
{
int pivot = A[lo];
while (lo < hi)
{
while (lo < hi && A[hi] >= pivot)
--hi;
A[lo] = A[hi];
while (lo < hi && A[lo] <= pivot)
++lo;
A[hi] = A[lo];
}
A[lo] = pivot;
return lo;
}
两种 partition 的区别在于是从前往后扫描还是从两侧往中间扫描，注意被注释的两行的功能是使得选取的枢轴随机化，避免遭遇最坏的输入情况使得时间复杂度恶化成 O(n^2)，当然第二种 partition 也能随机化枢轴的选取。
recursive
void quickSort(std::vector<int>& A, int lo, int hi)
{
if (lo < hi)
{
int pivot = partition(A, lo, hi);
quickSort(A, lo, pivot - 1);
quickSort(A, pivot + 1, hi);
}
}
void quickSorting(std::vector<int>& A)
{
quickSort(A, 0, A.size()-1);
}
non-recursive
void quickSorting(std::vector<int>& A)
{
if (A.size() < 2)
return;
int lo = 0, hi = static_cast<int>(A.size()) - 1;
std::stack<int> S;
S.push(lo); S.push(hi);
while (!S.empty())
{
hi = S.top(); S.pop();
lo = S.top(); S.pop();
int pivot = partition(A, lo, hi);
if (lo < pivot - 1)
{
S.push(lo);
S.push(pivot - 1);
}
if (pivot + 1 < hi)
{
S.push(pivot + 1);
S.push(hi);
}
}
}
非递归的实现中注意栈的 pop 顺序，先 pop 出 hi 再 pop 出 lo，只要与压栈的顺序相反即可；快速排序是不稳定的。
List
partition (value exchange)
ListNode* partition(ListNode *head, ListNode *tail)
{
ListNode *p = head, *q = head;
for (int pivot = head->val; q != tail; q = q->next)
{
if (q->val < pivot)
{
p = p->next;
std::swap(p->val, q->val);
}
}
std::swap(head->val, p->val);
return p; // p is the pivot
}
单链表的 partition 实现采用了值交换的方式，若是仅调整指针则非常难以实现，这主要是因为快速排序的递归形式是类似二叉树的先序遍历的结构，每一趟 partition 之后枢轴 pivot 的 next 指针域需要到 partition 出来的右半部分递归完毕后才得以确定，同样，partition 出来的左半部分也要在递归完毕之后才得以知道是哪个结点的 next 指针域指向枢轴 pivot。
recursive
void quickSort(ListNode *head, ListNode *tail)
{
if (head != tail && head->next != tail)
{
ListNode *pivot = partition(head, tail);
quickSort(head, pivot);
quickSort(pivot->next, tail);
}
}
ListNode* quickSortList(ListNode *head)
{
quickSort(head, NULL);
return head;
}
non-recursive
ListNode* quickSortList(ListNode *head)
{
if (head == NULL || head->next == NULL)
return head;
ListNode *lo = head, *hi = NULL;
std::stack<ListNode*> S;
S.push(lo); S.push(hi);
while (!S.empty())
{
hi = S.top(); S.pop();
lo = S.top(); S.pop();
ListNode *pivot = partition(lo, hi);
if (lo != pivot && lo->next != pivot)
{
S.push(lo);
S.push(pivot);
}
pivot = pivot->next;
if (pivot != hi && pivot->next != hi)
{
S.push(pivot);
S.push(hi);
}
}
return head;
}
单链表在递归的时候，枢轴 pivot 会被包含进左半部分中去，这是因为通过 partition 无法得到枢轴前驱的缘故。
Merge Sort
Array
merge
void merge(std::vector<int>& A, int lo, int mid, int hi)
{
std::vector<int> T(A.begin()+lo, A.begin()+mid+1);
int i = 0, j = mid + 1, k = lo;
while (j <= hi)
A[k++] = i <= mid - lo && T[i] <= A[j] ? T[i++] : A[j++];
while (i <= mid - lo)
A[k++] = T[i++];
}
recursive
void mergeSort(std::vector<int>& A, int lo, int hi)
{
if (lo < hi)
{
int mid = lo + (hi - lo >> 1);
mergeSort(A, lo, mid);
mergeSort(A, mid+1, hi);
merge(A, lo, mid, hi);
}
}
void mergeSorting(std::vector<int>& A)
{
mergeSort(A, 0, A.size()-1);
}
non-recursive
void mergeSorting(std::vector<int>& A)
{
int n = static_cast<int>(A.size());
for (int L = 2; L < n << 1; L <<= 1)
{
for (int lo = 0, mid = lo + L/2 - 1; mid < n - 1; lo += L, mid = lo + L/2 - 1)
{
int hi = lo + L - 1;
if (hi >= n)
hi = n - 1;
merge(A, lo, mid, hi);
}
}
}
数组归并排序的递归和非递归实现中归并的过程是不同的，递归实现是自顶向下，非递归实现是自底向上，而快速排序中无论是递归实现还是非递归实现都是自顶向下；归并排序是稳定的。
List
merge
ListNode* merge(ListNode *l1, ListNode *l2)
{
ListNode preHead(0), *tail = &preHead;
while (l1 != NULL && l2 != NULL)
{
tail = tail->next = l1->val < l2->val ? l1 : l2;
if (l1->val < l2->val)
l1 = l1->next;
else
l2 = l2->next;
}
tail->next = l1 != NULL ? l1 : l2;
return preHead.next;
}
recursive
ListNode* mergeSortList(ListNode *head)
{
if (head == NULL || head->next == NULL)
return head;
ListNode *slow = head, *fast = head->next->next;
while (fast != NULL && fast->next != NULL)
{
fast = fast->next->next;
slow = slow->next;
}
fast = slow->next;
slow->next = NULL;
slow = mergeSortList(head);
fast = mergeSortList(fast);
return merge(slow, fast);
}
单链表不适合自底向上的非递归实现，因为移动指针需要线性的时间。
对于单链表，针对 LeetCode 148 的测试用例归并排序和快速排序算法的性能如下，归并排序 50ms，快速排序非递归形式 512ms，快速排序递归形式 351ms，发现归并排序的性能远胜于快速排序的性能，如果链表中数据域存放的不是 int 这种内置类型的话，值交换就更慢了，因此单链表不适合采用快速排序。
Heap Sort
void __pushHeap(std::vector<int>& heap, int cur, int top, int val)
{
int parent = (cur - 1) / 2;
while (cur > top && heap[parent] < val)
{
heap[cur] = heap[parent];
cur = parent;
parent = (cur - 1) / 2;
}
heap[cur] = val;
}
void pushHeap(std::vector<int>& heap, int val)
{
heap.push_back(val);
__pushHeap(heap, heap.end()-heap.begin()-1, 0, val);
}
void __adjustHeap(std::vector<int>& heap, int cur, int n, int val)
{
int top = cur, right = 2*cur + 2;
while (right < n)
{
if (heap[right-1] > heap[right])
--right;
heap[cur] = heap[right];
cur = right;
right = 2*right + 2;
}
if (right == n)
{
heap[cur] = heap[right-1];
cur = right - 1;
}
__pushHeap(heap, cur, top, val);
}
void __popHeap(std::vector<int>& heap, int last)
{
int lastVal = heap[last];
heap[last] = heap[0];
__adjustHeap(heap, 0, last, lastVal);
}
void popHeap(std::vector<int>& heap)
{
int last = heap.end() - heap.begin() - 1;
if (last > 0)
__popHeap(heap, last);
heap.pop_back();
}
void makeHeap(std::vector<int>& heap)
{
int n = heap.end() - heap.begin(), parent = (n - 2) / 2 + 1;
if (n < 2)
return;
while (--parent >= 0)
__adjustHeap(heap, parent, n, heap[parent]);
}
void sortHeap(std::vector<int>& heap)
{
int last = heap.end() - heap.begin();
while (--last > 0)
__popHeap(heap, last);
}
该堆排序算法与标准库中的非递归实现完全一致，而《算法导论》中给出的是堆排序的递归实现；堆排序是不稳定的。