最近发现有时候看完一本书，时间久了容易忘记，看书不总结思考效果大打折扣，故打算写这一系列文章，一是为了整理书中的要点，帮助自己消化理解；二是勉励自己多看书思考。文章中不会把书中内容讲解的非常详细，只是总结概括，适合已经阅读过该书的读者。
下表是常用排序算法的归纳总结：
序号排序方法平均时间最差时间额外空间稳定度备注1插入O(n^2)O(n^2)O(1)稳定大部分已排序时,n小时较好2冒泡O(n^2)O(n^2)O(1)稳定大部分已排序时,n小时较好3归并O(nlog(n))O(nlog(n))O(1)稳定n较大时较好4堆排序O(nlog(n))O(nlog(n))O(1)不稳定n较大时较好5快速O(nlog(n))O(n^2)O(nlog(n))不稳定n较大时较好6计数O(n)排序的值都是0-k之间的整数7桶O(n)元素均匀、独立分布在[0, 1)区间在最坏情况下，任何比较排序算法都需要做Ω(nlog(n))次比较，所以堆排序和归并排序都是渐进最优的比较排序算法。
插入排序对于少量元素的排序，是一个有效的算法，插入排序法属于原址排序，即在任何时候，最多只有其中的常熟个数字存储在数组外面。插入排序的时间效率为O(n^2)。
InsertionSort(A) for j = 2 to A.length key = A[j] i = j - 1 while i > 0 and A[i] > key A[i + 1] = A[i] i = i - 1 A[i + 1] = key冒泡排序是一种流行但低效的排序方法，它的作用是反复交换相邻的未按次序排列的元素。冒泡排序的时间效率为O(n^2)，同样也是原址排序。
BubbleSort(A) for i = 1 to A.length - 1 for j = A.length downto i + 1 if A[j] < A[j - 1] exchange A[j] with A[j - 1]许多有用的算法在结构上是递归的：为了解决一个给定的问题，算法是一次或多次递归地调用其自身以解决紧密相关的若干子问题。这些算法典型地遵循分治法的思想：将原问题分解为几个规模较小但类似于原问题的字问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。
归并排序算法完全遵循分治模式。直观上其操作如下：
分解：分解待排序的n个元素的序列成各具n/2个元素的两个子序列解决：使用归并排序递归地排序两个子序列合并：合并两个已排序的子序列以产生已排序的答案 MERGE(A, p, q, r) n1 = q - p + 1 n2 = r - q let L[1 ... n1 + 1] and R[1 ... n2 + 1] be new arrays for i = 1 to n1 L[i] = A[p + i -1] for j = 1 to n2 R[j] = A[q + j] L[n1 + 1] = infinite R[n2 + 1] = infinite i = 1 j = 1 for k = p to r if L[i] <= R[j] A[k] = L[i] i = i + 1 else A[k] = R[j] j = j + 1 // // MERGE-SORT(A, p, r) if p < r q = ⌊(p + r) / 2⌋ MERGE-SORT(A, p, q) MERGE-SORT(A, q + 1, r) MERGE(A, p, q, r)堆排序归并排序一样，但不同于插入排序的是，堆排序的时间复杂度是O(nlog(n))。而与插入排序相同，但不同于归并排序的是，堆排序同样具有空间原址性
假定根结点为LEFT(i)和RIGHT(i)的二叉树都是最大堆，但A[i]有可能小于其孩子。对于一个树高为h的结点来说，MAX-HEAPIFY的时间复杂度是O(h)。
MAX-HEAPIFY(A, i) l = LEFT(i) r = right(i) if l <= A.heap-size and A[l] > A[i] largest = l else largest = i if r <= A.heap-size and A[r] > A[largest] largest = r if largest != i exchange A[i] with A[largest] MAX-HEAPIFY(A, largest)可以利用自底向上的方法利用过程MAX-HEAPIFY把一个大小为n＝A.Length的数组A[1 … n]转换为最大堆。可以证明建堆的时间复杂度为O(n)。
BUILD-MAX-HEAP(A) A.heap-size = A.length for i = ⌊A.length / 2⌋ to 1 MAX-HEAPIFY(A, i)O(nlog(n))
HEAPSORT(A) BUILD-MAX-HEAP(A) for i = A.length downto 2 exchange A[1] with A[i] A.heap-size = A.heap-size - 1 MAX_HEAPIFY(A, 1)高效的优先队列是堆的一个常见应用。优先队列是一种用来维护由一组元素构成的集合S的数据结构，其中的每一个元素都有一个相关的值。一个最大优先队列支持以下操作：
INSERT(S, x)：把元素x插入集合S中MAXIMUM(S)：返回S中具有最大健字的元素EXTRACT-MAX(S)：去掉并返回S中的具有最大键字的元素INCREASE-KEY(S, x, k)：将元素x的关键字值增加到k，这里假设k的值不小于x的原关键字值快速排序是一种最坏情况时间复杂度为O(n^2)的排序算法。虽然最坏情况时间复杂度很差，但是快速排序通常是实际排序应用中最好的选择，因为它的平均性能非常好：它的期望时间复杂度是O(nlog(n))，而且O(nlg(n))中隐含的常数因子非常小。
QUICKSORT(A, p ,r) if q < r q = PARTITION(A, p, r) QUICKSORT(A, p ,q - 1) QUICKSORT(A, q + 1, r) // // PARTITION(A, p, r) x = A[r] i = p - 1 for j = p to r - 1 if A[j] <= x i = i + 1 exchange A[i] with A[j] exchange A[i + 1] with A[i] return i + 1O(n)，用空间大小换取时间效率
COUNT-SORT(A, B, k) let C[0 ... k] be a new array for i = 0 to k C[i] = 0 for j = 1 to A.length C[A[j]] = C[A[j]] + 1 //C[i] now contains the number of elements equal to i for i = 1 to k C[i] = C[i] + C[i - 1] //C[i] now contains the number of elements less than or equal to i for j = A.length downto 1 B[C[A[j]]] = A[j] C[A[j]] = C[A[j]] - 1桶排序将[0, 1)区间划分为n个相同大小的子区间，或称为桶。然后，将n个输入数分别放到各个桶中。因为输入数据是均匀、独立分布在[0， 1)区间上的，所以一般不会出现很多数落在同一个桶中的情况。为了得到输出结果，先对每个桶中的数进行排序，然后遍历每个桶，按照次序把各个桶中的元素列出来。
BUCKET-SORT(A) n = A.length let B[0 ... n - 1] be a new array for i = 0 to n - 1 make B[i] an empty list for i = 1 to n insert A[i] into list B[⌊nA[i]⌋] for i = 0 to n - 1 sort list B[i] with insertion sort concatenate the lists B[0], B[1] ... B[n - 1] together in order