排序算法

[iLovEing]

sort algo 代码地址

[iLovEing]

bubble sort

冒泡排序 以升序为例，每次将[1, i]区间的最大值放到队尾， 其中 i = n to 2，像冒泡一样。

伪代码

*   for j = 2 to A.length
*       key = A[j]
*       //insert A[j] into the sorted sequence A[1 ... j-1]
*       i = j - 1
*       while i > 0 and A[i] > key
*           A[i + 1] = A[i]
*           i = i - 1
*
*       A[i + 1] = key

冒泡排序的耗时最差，即使原序列已经排好序，时间复杂度也是n^2

[iLovEing]

insert sort

插入排序 每次将第i个值插入到 [1, i-1] 队列的正确位置，其中i = 2 to n

伪代码

*   for j = 2 to A.length
*       key = A[j]
*       //insert A[j] into the sorted sequence A[1 ... j-1]
*       i = j - 1
*       while i > 0 and A[i] > key
*           A[i + 1] = A[i]
*           i = i - 1
*
*       A[i + 1] = key

插入排序相比冒泡好一些，平均复杂度n^2，但如果原序列已经排好序，时间复杂度可以降至n

[iLovEing]

merge sort

归并排序 利用分治递归思想，需要设计将两组已经排好序的序列合并逻辑，时间复杂度nlogn

伪代码

* MERGE (A, p, q, r)    //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]
*   L[n1 + 1] = MAX_NUM
*   for i = j to n2
*       R[j] = A[q + j]
*   R[n2 + 1] = MAX_NUM
*
*   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)    //p <= q < r
*   if p < r
*       q = (p + r) / 2
*       MERGE_SORT(A, p, q)
*       MERGE_SORT(A, q + 1, r)
*       MERGE(A, p, q, r)