C/C++算法从小白到高手(1)：排序算法

1. 冒泡排序

(1) 基本思路

冒泡排序是一种简单的、但效率极低的排序算法，基本思路是重复地遍历待排序的序列，通过相邻元素的比较和交换，将较大（或较小）的元素逐步"冒泡"到右侧（或左侧），直到整个序列有序为止。

(2) 升序排序

BUBBLE-SORT(a, len)
    for i = 1 ~ len-2
    do
        for j = 1 ~ len-i-2
        do
            if a[j] > a[j+1]
            do
                swap(a[j], a[j+1]);
            end if
        end for
    end for

(3) 分析时间复杂度

程序	执行次数（化简后）	时间复杂度
for i = 1 ~ len-2	$$len?2$$	$$O(len)$$
for j = 1 ~ len-i-2	$$\frac{(len?1)?(len?2)}{2}$$	$$O(le{n}^2)$$
if a[j] > a[j+1]	$$\frac{(len?1)?(len?2)}{2}$$	$$O(le{n}^2)$$
swap(a[j], a[j+1])	$$\frac{(len?1)?(len?2)}{2}$$	$$O(le{n}^2)$$
BUBBLE-SORT	$$\frac{3le{n}^2?9len+10}{2}?(len?2)$$	$$O(le{n}^3)$$

所以，冒泡排序的时间复杂度一般在 $O(le{n}^3)$ 上下。即使时间复杂度很高，但是冒泡排序还是有很高的地位。它既简单，又容易实现。

2. 插入排序

(1) 基本思路

插入排序是一种简单直观的排序算法，基本思路是将一个待排序的元素插入到已经排好序的子序列中的适当位置，直到整个序列有序为止。

(2) 升序排序

INSERTION-SORT(a, len)
    for i = 1 ~ len-1
    do
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key
        do
            a[j+1] = a[j]
            j = j - 1
        end while
        a[j+1] = key
    end for

(3) 分析时间复杂度

程序	执行次数（化简后）	时间复杂度
for i = 1 ~ len-1	$$len?1$$	$$O(len)$$
while j >= 0 and a[j] > key	$$\frac{(len?1)?(len?2)}{2}$$	$$O(le{n}^2)$$
a[j+1] = a[j]	$$\frac{(len?1)?(len?2)}{2}$$	$$O(le{n}^2)$$
a[j+1] = key	$$len?1$$	$$O(len)$$
INSERTION-SORT	$$\frac{3le{n}^2?3len+4}{2}$$	$$O(le{n}^2)$$

所以，插入排序的时间复杂度一般在 $O(n^2)$ 上下。它的时间复杂度比冒泡排序低，是一种简单且常用的排序算法。

3. 选择排序

(1) 基本思路

选择排序是一种简单直观的排序算法，基本思路是找到待排序序列中的最小（或最大）元素，将它与序列的第一个位置进行交换，然后再在剩余的序列中找到最小（或最大）元素，将它与序列的第二个位置进行交换，以此类推，直到整个序列有序为止。

(2) 升序排序

SELECTION-SORT(a, len)
    for i = 1 ~ len-1
    do
        minIndex = i
        for j = i+1 ~ len
        do
            if a[j] < a[minIndex]
            do
                minIndex = j
            end if
        end for
        swap(a[i], a[minIndex])
    end for

(3) 分析时间复杂度

程序	执行次数（化简后）	时间复杂度
for i = 1 ~ len-1	$$len?1$$	$$O(len)$$
for j = i+1 ~ len	$$\frac{(len?1)?len}{2}$$	$$O(le{n}^2)$$
if a[j] < a[minIndex]	$$\frac{(len?1)?len}{2}$$	$$O(le{n}^2)$$
swap(a[i], a[minIndex])	$$len?1$$	$$O(len)$$
SELECTION-SORT	$$\frac{3le{n}^2?3len+4}{2}$$	$$O(le{n}^2)$$

所以，选择排序的时间复杂度一般在 $O(n^2)$ 上下。虽然时间复杂度较高，但选择排序在某些情况下可以比其他排序算法更高效。

4. 快速排序

(1) 基本思路

快速排序是一种高效的排序算法，基本思路是通过一趟排序将待排序序列分割成独立的两个部分，其中一部分的所有元素都比另一部分的任意元素小，然后再对这两部分继续进行排序，直到整个序列有序为止。

(2) 升序排序

QUICK-SORT(a, low, high)
    if low < high
    do
        pivotIndex = PARTITION(a, low, high)
        QUICK-SORT(a, low, pivotIndex-1)
        QUICK-SORT(a, pivotIndex+1, high)
    end if

PARTITION(a, low, high)
    pivotValue = a[high]
    i = low - 1
    for j = low ~ high-1
    do
        if a[j] <= pivotValue
        do
            i = i + 1
            swap(a[i], a[j])
        end if
    end for
    swap(a[i+1], a[high])
    return i + 1

(3) 分析时间复杂度

程序	执行次数（化简后）	时间复杂度
if low < high	$${\log }_2(len)$$	$$O(\log (len))$$
PARTITION(a, low, high)	$$len?1$$	$$O(len)$$
QUICK-SORT(a, low, pivotIndex-1)	$$\frac{le{n}^2?len}{2}$$	$$O(le{n}^2)$$
QUICK-SORT(a, pivotIndex+1, high)	$$\frac{le{n}^2?len}{2}$$	$$O(le{n}^2)$$
QUICK-SORT	$$\frac{3le{n}^2?3len+10}{2}$$	$$O(le{n}^2)$$
PARTITION	$$len?1$$	$$O(len)$$

所以，快速排序的时间复杂度一般在 $O(n^2)$ 上下，但在平均情况下，时间复杂度为 $O(n\log n)$。

5. 归并排序

(1) 基本思路

归并排序是一种高效的排序算法，基本思路是将待排序序列分成若干个子序列，分别进行排序，然后再将已排序的子序列合并成更大的有序序列，直到最终只有一个有序序列为止。

(2) 升序排序

MERGE-SORT(a, low, high)
    if low < high
    do
        mid = (low + high) / 2
        MERGE-SORT(a, low, mid)
        MERGE-SORT(a, mid+1, high)
        MERGE(a, low, mid, high)
    end if

MERGE(a, low, mid, high)
    n1 = mid - low + 1
    n2 = high - mid
    left = new Array[n1]
    right = new Array[n2]
    for i = 0 ~ n1-1
    do
        left[i] = a[low + i]
    end for
    for j = 0 ~ n2-1
    do
        right[j] = a[mid + 1 + j]
    end for
    i = 0
    j = 0
    k = low
    while i < n1 and j < n2
    do
        if left[i] <= right[j]
        do
            a[k] = left[i]
            i = i + 1
        else
            a[k] = right[j]
            j = j + 1
        end if
        k = k + 1
    end while
    while i < n1
    do
        a[k] = left[i]
        i = i + 1
        k = k + 1
    end while
    while j < n2
    do
        a[k] = right[j]
        j = j + 1
        k = k + 1
    end while

(3) 分析时间复杂度

程序	执行次数（化简后）	时间复杂度
if low < high	$${\log }_2(len)$$	$$O(\log (len))$$
MERGE-SORT(a, low, mid)	$$\frac{len?(\log (len)?1)}{2}$$	$$O(len\log (len))$$
MERGE-SORT(a, mid+1, high)	$$\frac{len?(\log (len)?1)}{2}$$	$$O(len\log (len))$$
MERGE(a, low, mid, high)	$$len?1$$	$$O(len)$$
MERGE-SORT	$$\frac{3len?(\log (len)?1)}{2}$$	$$O(len\log (len))$$
MERGE	$$len?1$$	$$O(len)$$

所以，归并排序的时间复杂度一般为 $O(n\log n)$，在任何情况下都具有稳定的性能。