排序

排序算法

排序算法冒泡排序选择排序插入排序归并排序快速排序堆排序希尔排序计数排序基数排序桶排序

目录

1. 排序算法概述
2. 常见排序算法
   • 冒泡排序 (Bubble Sort)
   • 选择排序 (Selection Sort)
   • 插入排序 (Insertion Sort)
   • 归并排序 (Merge Sort)
   • 快速排序 (Quick Sort)
   • 堆排序 (Heap Sort)
   • 希尔排序 (Shell Sort)
   • 计数排序 (Counting Sort)
   • 基数排序 (Radix Sort)
   • 桶排序 (Bucket Sort)
3. 各算法的时间复杂度和空间复杂度
4. 稳定性和适用场景
5. 总结与建议

---

1. 排序算法概述

排序算法是将一组无序的元素重新排列，使其按照一定的顺序排列。排序在计算机科学中具有重要的理论和实际意义，不仅是计算机程序设计中的基础问题之一，也是数据库、搜索算法等的关键步骤。

2. 常见排序算法

冒泡排序 (Bubble Sort)冒泡排序

• 基本思想：通过重复地交换相邻未按顺序排列的元素，使每一趟扫描后，最大的元素逐渐 ” 浮 ” 到数组的最后一个位置。

• 时间复杂度：$O(n^2)$

• 空间复杂度：$O(1)$

• 稳定性：稳定

• 代码示例：

  def bubble_sort(arr):
      n = len(arr)
      for i in range(n):
          for j in range(0, n-i-1):
              if arr[j] > arr[j+1]:
                  arr[j], arr[j+1] = arr[j+1], arr[j]

选择排序 (Selection Sort)选择排序

• 基本思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的元素序列的最后，直到全部待排序的数据元素排完。

• 时间复杂度：$O(n^2)$

• 空间复杂度：$O(1)$

• 稳定性：不稳定

• 代码示例：

  def selection_sort(arr):
      n = len(arr)
      for i in range(n):
          min_idx = i
          for j in range(i+1, n):
              if arr[j] < arr[min_idx]:
                  min_idx = j
          arr[i], arr[min_idx] = arr[min_idx], arr[i]

插入排序 (Insertion Sort)插入排序

• 基本思想：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

• 时间复杂度：$O(n^2)$

• 空间复杂度：$O(1)$

• 稳定性：稳定

• 代码示例：

  def insertion_sort(arr):
      for i in range(1, len(arr)):
          key = arr[i]
          j = i - 1
          while j >= 0 and key < arr[j]:
              arr[j + 1] = arr[j]
              j -= 1
          arr[j + 1] = key

归并排序 (Merge Sort)归并排序

• 基本思想：采用分治法，将数组递归地二分，分别排序后再合并。

• 时间复杂度：$O(n\log n)$

• 空间复杂度：$O(n)$

• 稳定性：稳定

• 代码示例：

  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

快速排序 (Quick Sort)快速排序

• 基本思想：选择一个基准元素，将数组分为两部分，小于基准的元素放左边，大于基准的元素放右边，然后递归地对左右两部分继续进行排序。

• 时间复杂度：平均 $O(n\log n)$，最坏 $O(n^2)$

• 空间复杂度：$O(\log n)$

• 稳定性：不稳定

• 代码示例：

  def quick_sort(arr):
      if len(arr) <= 1:
          return arr
      pivot = arr[len(arr) // 2]
      left = [x for x in arr if x < pivot]
      middle = [x for x in arr if x == pivot]
      right = [x for x in arr if x > pivot]
      return quick_sort(left) + middle + quick_sort(right)

堆排序 (Heap Sort)堆排序

• 基本思想：利用 堆 这种数据结构来进行排序，首先将数组构造成最大堆，然后依次将堆顶元素与末尾元素交换，并减少堆的大小，调整堆以满足堆性质，反复进行直到堆大小为 1。

• 时间复杂度：$O(n\log n)$

• 空间复杂度：$O(1)$

• 稳定性：不稳定

• 代码示例：

  def heapify(arr, n, i):
      largest = i
      l = 2 * i + 1
      r = 2 * i + 2
      if l < n and arr[i] < arr[l]:
          largest = l
      if r < n and arr[largest] < arr[r]:
          largest = r
      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)

希尔排序 (Shell Sort)希尔排序

• 基本思想：基于插入排序的改进，通过比较相距一定间隔的元素来进行排序，随着算法的进行逐步减少间隔直到间隔为 1。

• 时间复杂度：根据增量序列不同而不同，平均复杂度为 $O(n^{1.3})$

• 空间复杂度：O(1)

• 稳定性：不稳定

• 代码示例：

  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

计数排序 (Counting Sort)计数排序

• 基本思想：对于输入数据中的每一个元素 x，确定小于 x 的元素个数，然后直接把 x 放到它在输出数组中的位置上。

• 时间复杂度：O(n + k)，其中 k 是数据范围

• 空间复杂度：O(n + k)

• 稳定性：稳定

• 代码示例：

  def counting_sort(arr):
      max_val = max(arr)
      m = max_val + 1
      count = [0] * m
      for a in arr:
          count[a] += 1
      i = 0
      for a in range(m):
          for c in range(count[a]):
              arr[i] = a
              i += 1

基数排序 (Radix Sort)基数排序

• 基本思想：将整数按位数切割成不同的数字，然后按每个位数分别比较。

• 时间复杂度：O(nk)，其中 k 是位数

• 空间复杂度：O(n + k)

• 稳定性：稳定

• 代码示例：

  def counting_sort_for_radix(arr, exp):
      n = len(arr)
      output = [0] * n
      count = [0] * 10
   
      for i in range(n):
          index = arr[i] // exp
          count[index % 10] += 1
   
      for i in range(1, 10):
          count[i] += count[i - 1]
   
      i = n - 1
      while i >= 0:
          index = arr[i] // exp
          output[count[index % 10] - 1] = arr[i]
          count[index % 10] -= 1
          i -= 1
   
      for i in range(len(arr)):
          arr[i] = output[i]
   
  def radix_sort(arr):
      max_val = max(arr)
      exp = 1
      while max_val // exp > 0:
          counting_sort_for_radix(arr, exp)
          exp *= 10
   

桶排序 (Bucket Sort)桶排序

• 基本思想：将数组元素分散到有限数量的桶中，每个桶再独立进行排序，最后合并各个桶中的元素得到排序结果。

• 时间复杂度：$O(n+k)$，其中 k 是桶的数量

• 空间复杂度：$O(n+k)$

• 稳定性：稳定

• 代码示例：

  def bucket_sort(arr):
      bucket = []
      slot_num = 10
      for i in range(slot_num):
          bucket.append([])
   
      for j in arr:
          index = int(slot_num * j)
          bucket[index].append(j)
   
      for i in range(slot_num):
          bucket[i] = sorted(bucket[i])
   
      k = 0
      for i in range(slot_num):
          for j in range(len(bucket[i])):
              arr[k] = bucket[i][j]
              k += 1

3. 各算法的时间复杂度和空间复杂度

排序算法	平均时间复杂度	最坏时间复杂度	最好时间复杂度	空间复杂度	稳定性
冒泡排序	O(n^2)	O(n^2)	O(n)	O(1)	稳定
选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定
插入排序	O(n^2)	O(n^2)	O(n)	O(1)	稳定
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	稳定
快速排序	O(n log n)	O(n^2)	O(n log n)	O(log n)	不稳定
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	不稳定
希尔排序	O(n^1.3)	O(n^2)	O(n)	O(1)	不稳定
计数排序	O(n + k)	O(n + k)	O(n + k)	O(n + k)	稳定
基数排序	O(nk)	O(nk)	O(nk)	O(n + k)	稳定
桶排序	O(n + k)	O(n^2)	O(n)	O(n + k)	稳定

4. 稳定性和适用场景

• 稳定排序：稳定排序算法保证两个相等的元素在排序前后的相对位置不变。适用于需要保留相同元素顺序的场景，如多关键字排序。
• 不稳定排序：不稳定排序算法可能改变相等元素的相对顺序。适用于对顺序没有特别要求的场景。

5. 总结与建议

• 对于小规模数据，简单排序（如插入排序、选择排序）可能是最优选择。
• 对于大规模数据，高效排序（如快速排序、归并排序、堆排序）更为适用。
• 当数据几乎有序时，插入排序表现良好。
• 需要稳定排序时，可选择归并排序、计数排序、基数排序和桶排序。

通过掌握不同排序算法的原理、复杂度和适用场景，可以根据实际情况选择最合适的排序算法，提高程序运行效率和可靠性。