类别 排序方法 时间复杂度（平均情况） 时间复杂度（最坏情况） 空间复杂度（储存空间） 稳定性
插入排序 直接插入排序 O(n^2) O(n^2) O(1) 是
Shell排序 O(nlogn)至O(n^2) O(n^s) 其中s是常数 O(1) 否
选择排序 直接选择排序 O(n^2) O(n^2) O(1) 否
堆排序 O(nlogn) O(nlogn) O(1) （不包括堆的存储） 否
交换排序 冒泡排序 O(n^2) O(n^2) O(1) 是
快速排序 O(nlogn) O(n^2) （未优化时） O(logn)至O(n) （递归栈） 否
归并排序 归并排序 O(nlogn) O(nlogn) O(n) 是
基数排序 基数排序（LSD） O(nk) 其中k是数字位数 O(nk) 其中k是数字位数 O(n+k) 是

直接插入排序（Straight Insertion Sort）

直接插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，找到排序位置后，需要将已排序元素逐步向后挪位，为最新元素提供插入空间。

直接插入排序的步骤：

  1. 从第一个元素开始，该元素可以认为已经被排序。
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描。
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置。
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
  5. 将新元素插入到该位置后。
  6. 重复步骤2~5。
  7. 直接插入排序的Python实现：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    def insertion_sort(arr):  
        # 遍历从1到数组长度的所有元素  
        for i in range(1, len(arr)):  
            key = arr[i]  # 当前需要排序的元素  
            j = i - 1  
            # 将arr[i]插入到arr[0...i-1]中已排序的序列中的正确位置  
            while j >= 0 and key < arr[j]:  
                arr[j + 1] = arr[j]  # 元素后移  
                j -= 1  
            arr[j + 1] = key  # 插入正确位置  
      
    # 测试代码  
    arr = [12, 11, 13, 5, 6]  
    insertion_sort(arr)  
    print("排序后的数组:")  
    for i in range(len(arr)):  
        print("%d" % arr[i], end=" ")
    时间复杂度：
    最好情况（数组已经是有序的）：O(n)
    平均情况：O(n
    2
    )
    最坏情况（数组是逆序的）：O(n
    2
    )
    空间复杂度：
    O(1)，因为是原地排序。
    直接插入排序适用于数据量较小或基本有序的情况，因为其在数据已经接近 有序 时效率较高。然而，对于数据量较大或完全无序的数组，其效率较低。

希尔排序（Shell Sort）

Shell 排序（Shell Sort），又称缩小增量排序，是插入排序的一种更高效的改进版本。它的基本思想是将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
这里的“基本有序”是指小的关键字基本在前，大的关键字基本在后，但并未真正有序。为了提高排序效率，可以减少比较的次数，即待排序的记录个数越少，比较的次数就越少。因此，可以将原来的记录序列分割成若干个子序列分别进行排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

Shell 排序的算法过程如下：

选择增量序列：初始时，选取一个增量 d1=n/2，将元素分为 d1 个组，每组相邻元素之间相隔 d1。在各组内进行直接插入排序；
重新分组：然后，取第二个增量 d2=d1/2，重复上述的分组排序过程，直到 di=1，即所有元素在同一组内进行直接插入排序。
Shell 排序的性能很大程度上取决于所选择的增量序列。好的增量序列可以使得排序时间复杂度降低，达到 O(nlogn) 的平均时间复杂度，但在最坏情况下时间复杂度仍然为 O(n^2)。
Shell 排序的一个简单实现（Python 示例）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def shell_sort(arr):  
    n = len(arr)  
    gap = n // 2  # 初始增量  
    while gap > 0:  
        for i in range(gap, n):  
            temp = arr[i]  
            j = i  
            # 对每个子列表进行插入排序  
            while j >= gap and arr[j - gap] > temp:  
                arr[j] = arr[j - gap]  
                j -= gap  
            arr[j] = temp  
        gap //= 2  # 减小增量  
  
# 测试代码  
arr = [64, 34, 25, 12, 22, 11, 90]  
shell_sort(arr)  
print("Sorted array is:", arr)

这段代码展示了 Shell 排序的基本实现。它首先通过选择一个较大的增量 gap 将数组分成多个子数组，并对每个子数组进行插入排序。然后逐渐减小 gap 的值，并重复上述过程，直到 gap 为 1，此时整个数组就是一个子数组，进行一次插入排序即可完成排序。

直接选择排序（Selection Sort）

直接选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理是：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

算法步骤
在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。
示例代码（Python）
这里以升序排序为例，展示直接选择排序的Python实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def selection_sort(arr):  
    # 遍历数组的所有元素  
    for i in range(len(arr)):  
        # 将当前位置设为最小值位置  
        min_index = i  
        # 遍历未排序的数组  
        for j in range(i+1, len(arr)):  
            # 更新最小值的位置  
            if arr[j] < arr[min_index]:  
                min_index = j  
        # 将找到的最小值交换到它应该在的位置  
        arr[i], arr[min_index] = arr[min_index], arr[i]  
    return arr  
  
# 测试代码  
arr = [64, 25, 12, 22, 11]  
sorted_arr = selection_sort(arr)  
print("Sorted array is:", sorted_arr)

复杂度分析
时间复杂度：
最好情况：O(n^2)
最坏情况：O(n^2)
平均情况：O(n^2)
无论输入数据如何，都需要进行n(n-1)/2次比较来找到所有元素的位置，因此时间复杂度总是O(n^2)。

空间复杂度：O(1)。直接选择排序是一种原地排序算法，它只需要固定的额外空间来存储临时变量。
直接选择排序虽然实现简单，但由于其效率不高，特别是对于大数据集，