Python排序算法
时间: 2024-01-29 08:10:13 浏览: 27
以下是两种常见的Python排序算法的介绍和示例:
1. 计数排序:
计数排序是一种不基于比较的排序算法,它的速度更快。但是它需要额外的空间来存放排序后的数列。
算法描述:
- 首先,找出待排序数组中的最大值和最小值。
- 创建一个计数数组,长度为最大值和最小值之间的差值加一。
- 遍历待排序数组,将每个元素的计数值加一。
- 遍历计数数组,将每个元素与前一个元素相加,得到每个元素在排序后数组中的位置。
- 创建一个与待排序数组相同长度的结果数组。
- 遍历待排序数组,将每个元素放入结果数组的对应位置,并将计数数组中对应元素的值减一。
- 返回结果数组作为排序后的数组。
示例代码:
```python
def counting_sort(arr):
min_val = min(arr)
max_val = max(arr)
count = [0] * (max_val - min_val + 1)
for num in arr:
count[num - min_val] += 1
for i in range(1, len(count)):
count[i] += count[i - 1]
result = [0] * len(arr)
for num in arr:
result[count[num - min_val] - 1] = num
count[num - min_val] -= 1
return result
```
2. 选择排序:
选择排序是一种简单但不稳定的排序算法,时间复杂度为O(n^2),适用于小数据。
算法描述:
- 首先,将数组分成已排序和未排序两组。
- 遍历未排序数组,从中找出最小值的索引。
- 将最小值与未排序数组的首位元素交换位置。
- 重复上述步骤,直到未排序数组为空。
示例代码:
```python
def selection_sort(arr):
n = len(arr)
for i in range(n - 1):
min_index = i
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[min_index], arr[i] = arr[i], arr[min_index]
return arr
```