排序算法分析

类别	排序方法	时间复杂度（平均情况）	时间复杂度（最坏情况）	空间复杂度（储存空间）	稳定性
插入排序	直接插入排序	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实现：

   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 示例）：

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实现：

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)。直接选择排序是一种原地排序算法，它只需要固定的额外空间来存储临时变量。
直接选择排序虽然实现简单，但由于其效率不高，特别是对于大数据集，

堆排序（Heap Sort）

堆排序（Heap Sort）是一种基于堆数据结构的比较排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或大于）它的父节点。

堆排序主要分为两个步骤：

1. 建立最大堆（或最小堆）：将无序数组重新组织成一个堆。
2. 排序过程：反复将堆顶元素（最大值或最小值）与末尾元素交换，然后减少堆的有效长度，并重新调整堆结构，直到整个堆有序。

以下是堆排序的详细步骤，以最大堆为例：

步骤一：建立最大堆

1. 从最后一个非叶子节点开始，逐步向上调整堆结构。
2. 调整堆的过程称为“堆化”（heapify）。

步骤二：排序过程

1. 将堆顶元素（最大值）与当前堆的最后一个元素交换。
2. 排除已排序的最后一个元素，将堆的有效长度减1。
3. 对新的堆顶元素进行堆化，使其满足最大堆的性质。
4. 重复上述步骤，直到堆的有效长度为1，排序完成。

示例代码（Python）

def heapify(arr, n, i):
    largest = i  # 初始化最大值为根节点
    left = 2 * i + 1  # 左子节点
    right = 2 * i + 2  # 右子节点

    # 如果左子节点存在且大于根节点
    if left < n and arr[largest] < arr[left]:
        largest = left

    # 如果右子节点存在且大于当前最大值
    if right < n and arr[largest] < arr[right]:
        largest = right

    # 如果最大值不是根节点
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # 交换

        # 递归堆化受影响的子树
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    # 建立最大堆
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 一个一个元素从堆顶取出并调整堆
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 交换
        heapify(arr, i, 0)

# 示例
arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print("排序后的数组:", arr)

注意：在上面的代码中，heapify 函数用于维护堆的性质，heap_sort 函数则用于进行堆排序。代码中的 heapify 函数在调整子树时，实际上传入的是堆的有效长度和需要调整的根节点索引。

复杂度分析

• 时间复杂度：

  • 建立最大堆：O(n)
  • 排序过程：O(n log n)（每次堆化操作的时间复杂度为 O(log n)，需要进行 n-1 次堆化）
  • 总体时间复杂度：O(n log n)

• 空间复杂度：O(1)（原地排序，不需要额外的存储空间）

堆排序是一种高效的基于比较的排序算法，特别适用于大数据量的排序任务。

冒泡排序（Bubble Sort）

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行的，直到没有再需要交换的元素为止，这表示该数列已经排序完成。

冒泡排序的名字由来是因为越小（或越大）的元素会经过交换慢慢“浮”到数列的顶端（或底部），就像水中的气泡一样上浮到水面。

冒泡排序的基本步骤：

1. 比较相邻的元素。如果第一个比第二个大（或小，根据排序顺序决定），就交换它们两个。
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

冒泡排序的Python代码示例（升序）：

def bubbleSort(arr):
    n = len(arr)
    # 遍历所有数组元素
    for i in range(n):
        # Last i elements are already in place
        for j in range(0, n-i-1):
            # 遍历数组从0到n-i-1
            # 交换如果元素找到比它大的元素
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

# 测试代码
arr = [64, 34, 25, 12, 22, 11, 90]
bubbleSort(arr)

print("排序后的数组是:")
for i in range(len(arr)):
    print("%d" % arr[i], end=" ")

冒泡排序的性能：

• 时间复杂度：平均和最坏的情况都是O(n^2)，其中n是数组的长度。最好的情况是O(n)，这发生在数组已经是排序好的情况下。
• 空间复杂度：O(1)，因为它是原地排序，只需要用到常量的额外空间。

尽管冒泡排序在实际应用中由于其低效率而很少使用，但它对于教学和理解排序算法的基本原理很有帮助。

快速排序（Quick Sort）

在Python中实现快速排序算法，我们可以定义一个递归函数，该函数首先选择一个基准元素（pivot），然后将数组分成两部分，一部分包含小于基准的元素，另一部分包含大于基准的元素。之后，递归地对这两部分进行排序。

下面是一个使用Python实现的快速排序示例：

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    else:
        # 选择基准元素，这里选择第一个元素
        pivot = arr[0]
        # 将小于基准的元素放到左边，大于基准的元素放到右边
        less = [x for x in arr[1:] if x <= pivot]
        greater = [x for x in arr[1:] if x > pivot]
        # 递归排序左右两边的列表
        return quicksort(less) + [pivot] + quicksort(greater)

# 测试代码
arr = [10, 7, 8, 9, 1, 5]
sorted_arr = quicksort(arr)
print("Sorted array is:", sorted_arr)

然而，上述实现方式在处理大数据集时可能效率不高，因为它使用了列表推导式来创建新的列表less和greater，这增加了额外的空间复杂度。一个更高效的实现方式是使用原地分区（in-place partitioning），这样可以避免创建新的列表。

下面是一个使用原地分区的快速排序实现：

def partition(arr, low, high):
    pivot = arr[high]  # 选择最后一个元素作为基准
    i = low - 1  # 小于基准的元素的索引
    for j in range(low, high):
        # 如果当前元素小于或等于基准
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]  # 交换
    arr[i + 1], arr[high] = arr[high], arr[i + 1]  # 将基准放到中间
    return i + 1

def quicksort_inplace(arr, low, high):
    if low < high:
        # pi 是分区后基准的索引
        pi = partition(arr, low, high)

        # 递归排序基准左边的子数组
        quicksort_inplace(arr, low, pi - 1)
        # 递归排序基准右边的子数组
        quicksort_inplace(arr, pi + 1, high)

# 测试代码
arr = [10, 7, 8, 9, 1, 5]
quicksort_inplace(arr, 0, len(arr) - 1)
print("Sorted array is:", arr)

这个实现通过partition函数进行原地分区，然后递归地对分区后的子数组进行排序。这种方法避免了不必要的数组复制，从而提高了效率。

归并排序（Merge Sort）

归并排序（Merge Sort）是一种基于分治策略的排序算法。它首先将数组分成两半，对每半部分递归地应用归并排序，然后将排序好的两半合并成一个有序的整体。以下是归并排序的Python实现：

def merge_sort(arr):
    if len(arr) > 1:
        # 找到中点，将数组分为两半
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]

        # 递归地对左右两半进行归并排序
        merge_sort(L)
        merge_sort(R)

        # 合并两个已排序的半部分
        i = j = k = 0

        # 当两个子列表都还有元素时，进行比较并合并
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        # 如果左半部分还有剩余元素，将它们添加到结果数组中
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        # 如果右半部分还有剩余元素，将它们添加到结果数组中
        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

# 测试代码
arr = [12, 11, 13, 5, 6, 7]
merge_sort(arr)
print("Sorted array is:", arr)

复杂度分析：

• 时间复杂度：

  • 最好情况：O(n log n)
  • 最坏情况：O(n log n)
  • 平均情况：O(n log n)
    归并排序的时间复杂度是稳定的，因为它总是将数组分成两半，然后对每一半进行递归排序，并将它们合并。这个过程的时间复杂度是由递归的深度（log n）和每一层递归中的合并操作（O(n)）共同决定的。

• 空间复杂度：O(n)
  归并排序不是原地排序算法，因为它需要额外的空间来存储临时数组（在上面的例子中，是L和R）。在最坏的情况下，当递归达到最底层时，需要存储与原始数组大小相同的额外空间，因此空间复杂度是O(n)。不过，可以通过一些技巧（如使用迭代而非递归，或使用原地归并排序的变体）来减少空间复杂度，但这些实现通常更复杂且效率较低。
  基数排序（Radix Sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表示字符串（如日期或电话号码），基数排序也可以很自然地扩展到这些数据的排序。

基数排序（Radix Sort）

以下是一个基于计数排序（Counting Sort）作为子过程的基数排序的Python实现，这里假设我们要排序的是非负整数列表：

def counting_sort_for_radix(arr, exp):
    """
    计数排序的辅助函数，用于基数排序的每一位
    :param arr: 输入的数组
    :param exp: 当前考虑的位数（例如，exp=1时考虑个位数）
    """
    n = len(arr)
    
    # 初始化计数数组，假设数组中的数都是非负的，并且我们知道最大的数
    output = [0] * n
    count = [0] * 10

    # 存储每个元素出现的次数
    for i in range(n):
        index = (arr[i] // exp) % 10
        count[index] += 1

    # 更改count[i]，使其包含实际位置信息
    for i in range(1, 10):
        count[i] += count[i - 1]

    # 构建输出数组
    i = n - 1
    while i >= 0:
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1
        i -= 1

    # 将排序后的元素复制回原数组
    for i in range(len(arr)):
        arr[i] = output[i]

def radix_sort(arr):
    """
    基数排序
    :param arr: 输入的整数数组
    """
    # 找到最大数以确定最大位数
    max_num = max(arr)

    # 对每个位数执行计数排序
    exp = 1
    while max_num // exp > 0:
        counting_sort_for_radix(arr, exp)
        exp *= 10

# 测试代码
arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print("Sorted array is:", arr)

在这个实现中，我们首先定义了一个counting_sort_for_radix函数，它基于当前考虑的位数（exp）对数组进行计数排序。然后，在radix_sort函数中，我们找到数组中的最大数来确定我们需要考虑的最大位数，并对每一位执行计数排序。

基数排序的时间复杂度通常是O(nk)，其中n是数组的长度，k是数字的最大位数。对于固定长度的数字（如32位整数），k可以视为常数，因此基数排序在平均和最好情况下的时间复杂度可以认为是线性的，即O(n)。然而，当k很大时（例如，对于非常大的数字或字符串），k不能被忽略，因此时间复杂度会接近O(nk)。

空间复杂度方面，基数排序通常需要额外的空间来存储计数数组和输出数组，这取决于数字的位数和范围。在最坏的情况下，空间复杂度可以是O(n+k)，但在实际应用中，由于k通常很小，这通常不是一个问题。