排序算法python（排序算法稳定性是什么意思）

排序算法

## 简介排序算法是计算机科学中用于将数据元素按特定顺序排列的技术。在 Python 中，有许多不同的排序算法可用，每种算法都有自己的优点和缺点。## 常见排序算法

1. 冒泡排序

冒泡排序是一种简单易懂的算法，它通过反复比较相邻元素并将较大的元素向后移动来对列表进行排序。它以持续“冒泡”较大的元素到正确位置的方式工作。```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] ```

2. 选择排序

选择排序通过选择列表中的最小元素并将其交换到列表的开头来对列表进行排序。此过程重复执行，每次选择列表中剩余元素的最小元素。```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] ```

3. 插入排序

插入排序通过将每个元素插入到前面已经排序的子列表中来对列表进行排序。它将当前元素与已排序子列表中的元素进行比较，并将其插入到正确的位置。```python def insertion_sort(arr):n = len(arr)for i in range(1, n):key = arr[i]j = i-1while j >= 0 and key < arr[j]:arr[j+1] = arr[j]j -= 1arr[j+1] = key ```

4. 快速排序

快速排序是一种高效的排序算法，它使用称为枢纽元素的元素将列表分成较小和较大的子列表。然后算法递归地对这些子列表进行排序。```python def quick_sort(arr, low, high):if low < high:pi = partition(arr, low, high)quick_sort(arr, low, pi-1)quick_sort(arr, pi+1, high)def partition(arr, low, high):pivot = arr[high]i = (low-1) for j in range(low, high):if arr[j] <= pivot:i = i+1arr[i], arr[j] = arr[j], arr[i]arr[i+1], arr[high] = arr[high], arr[i+1]return (i+1) ```

5. 归并排序

归并排序是一种稳定且高效的排序算法，它通过递归将列表拆分成较小的子列表，对子列表进行排序，然后合并它们来对列表进行排序。```python def merge_sort(arr):n = len(arr)if n > 1:mid = n//2 L = arr[:mid] R = arr[mid:] merge_sort(L) merge_sort(R) i = j = k = 0while i < len(L) and j < len(R):if L[i] < R[j]:arr[k] = L[i]i+= 1else:arr[k] = R[j]j+= 1k+= 1while i < len(L):arr[k] = L[i]i+= 1k+= 1while j < len(R):arr[k] = R[j]j+= 1k+= 1 ```

**排序算法**

简介排序算法是计算机科学中用于将数据元素按特定顺序排列的技术。在 Python 中，有许多不同的排序算法可用，每种算法都有自己的优点和缺点。

常见排序算法**1. 冒泡排序**冒泡排序是一种简单易懂的算法，它通过反复比较相邻元素并将较大的元素向后移动来对列表进行排序。它以持续“冒泡”较大的元素到正确位置的方式工作。```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] ```**2. 选择排序**选择排序通过选择列表中的最小元素并将其交换到列表的开头来对列表进行排序。此过程重复执行，每次选择列表中剩余元素的最小元素。```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] ```**3. 插入排序**插入排序通过将每个元素插入到前面已经排序的子列表中来对列表进行排序。它将当前元素与已排序子列表中的元素进行比较，并将其插入到正确的位置。```python def insertion_sort(arr):n = len(arr)for i in range(1, n):key = arr[i]j = i-1while j >= 0 and key < arr[j]:arr[j+1] = arr[j]j -= 1arr[j+1] = key ```**4. 快速排序**快速排序是一种高效的排序算法，它使用称为枢纽元素的元素将列表分成较小和较大的子列表。然后算法递归地对这些子列表进行排序。```python def quick_sort(arr, low, high):if low < high:pi = partition(arr, low, high)quick_sort(arr, low, pi-1)quick_sort(arr, pi+1, high)def partition(arr, low, high):pivot = arr[high]i = (low-1) for j in range(low, high):if arr[j] <= pivot:i = i+1arr[i], arr[j] = arr[j], arr[i]arr[i+1], arr[high] = arr[high], arr[i+1]return (i+1) ```**5. 归并排序**归并排序是一种稳定且高效的排序算法，它通过递归将列表拆分成较小的子列表，对子列表进行排序，然后合并它们来对列表进行排序。```python def merge_sort(arr):n = len(arr)if n > 1:mid = n//2 L = arr[:mid] R = arr[mid:] merge_sort(L) merge_sort(R) i = j = k = 0while i < len(L) and j < len(R):if L[i] < R[j]:arr[k] = L[i]i+= 1else:arr[k] = R[j]j+= 1k+= 1while i < len(L):arr[k] = L[i]i+= 1k+= 1while j < len(R):arr[k] = R[j]j+= 1k+= 1 ```