常见排序方法的总结归类

一、基于比较的排序方法

这类排序方法是通过比较元素大小来确定顺序，主要包括以下几种：

1. 冒泡排序（Bubble Sort）

• 原理：通过相邻元素之间的比较和交换，将最小（或最大）的元素逐步“冒泡”到列表的一端。

• 实现步骤：

  1. 从列表的第一个元素开始，比较相邻的两个元素，如果前一个元素大于后一个元素，则交换它们的位置。

  2. 依次进行比较和交换，直到列表的末尾，此时最大的元素已经位于列表的最后一个位置。

  3. 重复上述过程，但每次遍历的范围减少一个元素（因为最大的元素已经排好序）。

• Python 示例：

  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]return arr

• 优缺点：

  • 优点：实现简单，代码易于理解。

  • 缺点：时间复杂度较高，为 O(n²)，不适合大规模数据排序。

2. 选择排序（Selection Sort）

• 原理：通过多次从未排序部分选择最小（或最大）的元素，放到已排序部分的末尾，逐步完成排序过程。

• 实现步骤：

  1. 从未排序部分中找到最小的元素。

  2. 将该最小元素与未排序部分的第一个元素交换位置。

  3. 缩小未排序部分的范围，重复上述过程，直到所有元素都有序。

• Python 示例：

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

• 优缺点：

  • 优点：实现简单，无需额外的内存空间。

  • 缺点：时间复杂度为 O(n²)，效率较低；不稳定排序，可能破坏相同元素的相对顺序。

3. 插入排序（Insertion Sort）

• 原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。类似于扑克牌的排序方式。

• 实现步骤：

  1. 从第二个元素开始，假设第一个元素为已排序部分。

  2. 取未排序部分的第一个元素，将其插入到已排序部分的适当位置。

  3. 重复上述过程，直到整个列表有序。

• Python 示例：

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

• 优缺点：

  • 优点：实现简单，效率较高，对于少量数据或基本有序的数据效果不错；稳定排序，保持相同元素的相对位置。

  • 缺点：最坏情况下时间复杂度为 O(n²)；对于大规模数据排序效率低下。

4. 快速排序（Quick Sort）

• 原理：通过一个“基准”元素将数组分成两部分，然后递归地对每个部分排序。

• 实现步骤：

  1. 选择一个“基准”元素，通常选择数组的第一个、最后一个或中间的元素。

  2. 将数组分成两部分：一部分所有元素小于基准元素，另一部分所有元素大于基准元素。

  3. 递归地对两部分进行排序。

• Python 示例：

  def quick_sort(arr):if len(arr) <= 1:return arrpivot = 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)

• 优缺点：

  • 优点：平均时间复杂度为 O(n log n)，在实际应用中往往表现优越。

  • 缺点：最坏情况下时间复杂度为 O(n²)（当基准元素选择不好时）；空间复杂度为 O(log n)（递归栈空间）。

5. 归并排序（Merge Sort）

• 原理：采用分治法，将数组分成两个子数组，对每个子数组排序，然后合并两个已排序的子数组。

• 实现步骤：

  1. 将数组分成两个子数组，递归地对两个子数组进行排序。

  2. 合并两个已排序的子数组。

• Python 示例：

  def merge_sort(arr):if len(arr) <= 1:return arrmid = len(arr) // 2left = merge_sort(arr[:mid])right = merge_sort(arr[mid:])return merge(left, right)def merge(left, right):merged = []i = j = 0while i < len(left) and j < len(right):if left[i] < right[j]:merged.append(left[i])i += 1else:merged.append(right[j])j += 1merged.extend(left[i:])merged.extend(right[j:])return merged

• 优缺点：

  • 优点：时间复杂度稳定为 O(n log n)；稳定排序，保持相同元素的相对位置；适用于大规模数据。

  • 缺点：需要额外的内存空间，空间复杂度为 O(n)。

二、非基于比较的排序方法

这类排序方法不通过比较元素大小来确定顺序，主要包括以下几种：

1. 计数排序（Counting Sort）

• 原理：创建一个计数数组，统计每个元素出现的次数，然后根据计数数组重建排序后的数组。

• 实现步骤：

  1. 找出待排序数组中的最大值和最小值，确定计数数组的大小。

  2. 创建一个计数数组，遍历待排序数组，统计每个元素出现的次数。

  3. 根据计数数组重建排序后的数组。

• Python 示例：

  def counting_sort(arr):max_val = max(arr)min_val = min(arr)range_of_elements = max_val - min_val + 1count = [0] * range_of_elementsfor num in arr:count[num - min_val] += 1sorted_arr = []for i in range(len(count)):sorted_arr.extend([i + min_val] * count[i])return sorted_arr

• 优缺点：

  • 优点：时间复杂度为 O(n + k)，其中 k 是数据范围，适用于数据范围较小的情况。

  • 缺点：空间复杂度较高，需要额外的计数数组；不适用于数据范围较大的情况。

2. 基数排序（Radix Sort）

• 原理：按照低位先排序，然后收集；再按照高位排序，再收集，以此类推，直到最高位。

• 实现步骤：

  1. 找出待排序数组中的最大数，确定最大数的位数。

  2. 从低位到高位，依次按照每一位的数值进行计数排序。

  3. 重复上述过程，直到最高位排序完成。

• Python 示例：

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

• 优缺点：

  • 优点：时间复杂度为 O(nk)，其中 k 是数据的位数，适用于数据位数较少的情况。

  • 缺点：需要额外的空间来存储中间结果；不适用于数据位数较多的情况。

三、Python 内置排序方法

Python 提供了内置的排序方法，主要包括 sort() 方法和 sorted() 函数。

1. sort() 方法

• 原理：sort() 方法是列表对象的一个方法，可以直接对列表进行排序，不需要创建新的列表。

• 使用示例：

  lst = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
  lst.sort()  # 默认升序排序
  print(lst)  # [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]lst.sort(reverse=True)  # 降序排序
  print(lst)  # [9, 6, 5, 5, 5, 4, 3, 3, 2, 1, 1]lst = ['apple', 'banana', 'orange', 'pear']
  lst.sort(key=len)  # 按照字符串长度排序
  print(lst)  # ['pear', 'apple', 'banana', 'orange']

• 优缺点：

  • 优点：简单易用，直接修改原列表。

  • 缺点：无法保留原列表不变。

2. sorted() 函数

• 原理：sorted() 函数是 Python 内置函数，可以对任何可迭代对象进行排序，返回一个新的列表。

• 使用示例：

  lst = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
  new_lst = sorted(lst)  # 默认升序排序
  print(new_lst)  # [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]new_lst = sorted(lst, reverse=True)  # 降序排序
  print(new_lst)  # [9, 6, 5, 5, 5, 4, 3, 3, 2, 1, 1]lst = ['apple', 'banana', 'orange', 'pear']
  new_lst = sorted(lst, key=len)  # 按照字符串长度排序
  print(new_lst)  # ['pear', 'apple', 'banana', 'orange']

• 优缺点：

  • 优点：灵活，可以对任何可迭代对象进行排序，返回新的列表，保留原列表不变。

  • 缺点：需要创建新的列表，占用额外的内存空间。

四、其他排序方法

除了上述常见的排序方法，还有一些其他的排序方法，如 lambda 表达式作为 key 参数进行排序、operator 模块进行排序以及 numpy 模块进行排序等。

1. 使用 lambda 表达式作为 key 参数进行排序

• 原理：lambda 表达式是一种匿名函数，可以用于简化代码。在排序时，可以使用 lambda 表达式作为 key 参数，指定排序的关键字。

• 使用示例：

  lst = ['apple', 'banana', 'orange', 'pear']
  lst.sort(key=lambda x: x[1])  # 按照第二个字母排序
  print(lst)  # ['banana', 'pear', 'apple', 'orange']

• 优缺点：

  • 优点：灵活，可以指定复杂的排序规则。

  • 缺点：对于复杂的排序规则，代码可读性可能较低。

2. 使用 operator 模块进行排序

• 原理：operator 模块提供了一些函数，可以用于操作 Python 中的内置对象。在排序时，可以使用 operator 模块中的函数作为 key 参数，指定排序的关键字。

• 使用示例：

  import operatorlst = [('apple', 3), ('banana', 2), ('orange', 4), ('pear', 1)]
  lst.sort(key=operator.itemgetter(1))  # 按照第二个元素排序
  print(lst)  # [('pear', 1), ('banana', 2), ('apple', 3), ('orange', 4)]

• 优缺点：

  • 优点：代码简洁，可读性高。

  • 缺点：需要导入 operator 模块。

3. 使用 numpy 模块进行排序

• 原理：numpy 模块是 Python 中用于科学计算的一个重要模块，提供了很多数组操作函数。在排序时，可以使用 numpy 模块中的函数进行排序。

• 使用示例：

  import numpy as nplst = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
  new_lst = np.sort(lst)  # 默认升序排序
  print(new_lst)  # [1 1 2 3 3 4 5 5 5 6 9]new_lst = np.sort(lst)[::-1]  # 降序排序
  print(new_lst)  # [9 6 5 5 5 4 3 3 2 1 1]

• 优缺点：

  • 优点：适用于处理大数据，效率高。

  • 缺点：需要导入 numpy 模块，对于小规模数据可能过于复杂。