python常用的各种排序算法原理与实现方法小结
1. 冒泡排序（Bubble Sort）
基本思想：重复地遍历待排序的数列，每次比较相邻的两个元素，如果它们的顺序错误就交换位置，直到没有需要交换的元素为止。
实现代码：
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1):
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr2. 插入排序（Insertion Sort）
基本思想：将数组分为已排序区间和未排序区间，每次从未排序区间选择一个元素，插入到已排序区间中的合适位置，直到未排序区间为空为止。
实现代码：
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
j = i
while j > 0 and arr[j] < arr[j - 1]:
arr[j], arr[j - 1] = arr[j - 1], arr[j]
j -= 1
return arr3. 选择排序（Selection Sort）
基本思想：每次从未排序区间选择最小的元素，放入已排序区间末尾，直到未排序区间为空为止。
实现代码：
def selection_sort(arr):
n = len(arr)
for i in range(n - 1):
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]
return arr4. 快速排序（Quick Sort）
基本思想：选定一个pivot，将数组分成左右两个部分，使得左边部分中的元素都小于pivot，右边部分中的元素都大于pivot。然后对左右两个部分递归地进行快排。
实现代码：
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[0]
left, right = [], []
for x in arr[1:]:
if x < pivot:
left.append(x)
else:
right.append(x)
return quick_sort(left) + [pivot] + quick_sort(right)虽然这些算法都是常见的排序算法，但在实际应用中，不同算法的性能会因数据规模、数据分布等因素而有所不同，需要具体问题具体分析，选择合适的算法来解决。
相关文章