Python实现常见的排序算法

当涉及到排序算法时，一些常见的排序算法包括插入排序、选择排序、冒泡排序、快速排序、归并排序和堆排序。以下是使用Python实现这些常见排序算法的示例代码：

1. 插入排序（Insertion Sort）：

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

2. 选择排序（Selection Sort）：

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

3. 冒泡排序（Bubble Sort）：

def bubbleSort(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]

4. 快速排序（Quick Sort）：

def quickSort(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 quickSort(left) + middle + quickSort(right)

5. 归并排序（Merge Sort）：

def mergeSort(arr):if len(arr) <= 1:return arrmid = len(arr) // 2left = mergeSort(arr[:mid])right = mergeSort(arr[mid:])return merge(left, right)def merge(left, right):result = []while len(left) > 0 and len(right) > 0:if left[0] <= right[0]:result.append(left.pop(0))else:result.append(right.pop(0))result.extend(left)result.extend(right)return result

6. 堆排序（Heap Sort）：

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