Python实现比较排序算法

1. 冒泡排序（Bubble Sort）

冒泡排序的思路是比较两个相邻的元素，如果它们的顺序错误就交换位置，直到没有任何一对相邻元素需要交换为止。

代码演示：

def bubbleSort(arr):
n = len(arr)
# 遍历所有数组元素
for i in range(n):
# Last i elements are already sorted
for j in range(0, n-i-1):
# 通过比较相邻元素交换位置
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]

arr = [64, 34, 25, 12, 22, 11, 90]
bubbleSort(arr)
print ("排序后的数组:", arr)

输出结果：
排序后的数组: [11, 12, 22, 25, 34, 64, 90]

2. 选择排序（Selection Sort）

选择排序的思路是每次从未排序的数组中选择最小的元素，将其放到已排序的末尾。这样每一次选择都可以将未排序的数组中的最小值放到正确位置。

代码演示：

def selectionSort(arr):
n = len(arr)
# 遍历所有数组元素
for i in range(n):
# 寻找未排序数组中最小的元素
min_idx = i
for j in range(i+1, n):
if arr[min_idx] > arr[j]:
min_idx = j

    # 将找到的最小值放到已排序的末尾
    arr[i], arr[min_idx] = arr[min_idx], arr[i]

arr = [64, 34, 25, 12, 22, 11, 90]
selectionSort(arr)
print ("排序后的数组:", arr)

输出结果：
排序后的数组: [11, 12, 22, 25, 34, 64, 90]

3. 插入排序（Insertion Sort）

插入排序的思路是将未排序数组中的元素一个一个插入到已排序的数组中。将当前元素与已排序的所有元素进行比较，找到正确位置插入即可。

代码演示：

def insertionSort(arr):
n = len(arr)
# 遍历未排序的数组元素
for i in range(1, n):
key = arr[i]
j = i-1
# 将当前元素插入到正确的位置
while j >=0 and key < arr[j] :
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key

arr = [64, 34, 25, 12, 22, 11, 90]
insertionSort(arr)
print ("排序后的数组:", arr)

输出结果：
排序后的数组: [11, 12, 22, 25, 34, 64, 90]

4. 快速排序（Quick Sort）

快速排序的思路是将数组分成两个子数组，然后对这两个子数组进行递归排序。在每轮的排序中，将一个元素找出作为“基准”（pivot），然后将数组分成两部分，比基准小的元素放在左边，比基准大的元素放在右边。

代码演示：

def partition(arr, low, high):
i = (low-1) # 最小元素索引
pivot = arr[high] # 基准元素

for j in range(low, high):
    # 如果当前元素小于基准元素
    if arr[j] <= pivot:
        # 将其放到已排序部分的末尾
        i = i+1
        arr[i], arr[j] = arr[j], arr[i]

# 将基准元素放到已排序部分的末尾
arr[i+1], arr[high] = arr[high], arr[i+1]
return (i+1)

def quickSort(arr, low, high):
if len(arr) == 1:
return arr
if low < high:
# 找到基准元素的位置
pi = partition(arr, low, high)

    # 对基准元素左边的子数组进行递归排序
    quickSort(arr, low, pi-1)
    # 对基准元素右边的子数组进行递归排序
    quickSort(arr, pi+1, high)

arr = [64, 34, 25, 12, 22, 11, 90]
n = len(arr)
quickSort(arr, 0, n-1)
print ("排序后的数组:", arr)

输出结果：
排序后的数组: [11, 12, 22, 25, 34, 64, 90]

5. 归并排序（Merge Sort）

归并排序的思路是将数组分成两个子数组，然后对这两个子数组进行递归排序。在排序子数组时，将每个子数组分成更小的数组，直到每个数组只有一个元素。然后将这些子数组合并起来，直到两个子数组合并成一个有序数组。

代码演示：

def mergeSort(arr):
if len(arr) > 1:
mid = len(arr)//2
# 将数组分成左右两个子数组
L = arr[:mid]
R = arr[mid:]

    # 左右两个子数组进行递归排序
    mergeSort(L)
    mergeSort(R)

    i = j = k = 0
    # 合并左右两个子数组
    while i < len(L) and j < len(R):
        if L[i] < R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1

    # 将剩下未合并的元素加到已排序的末尾
    while i < len(L):
        arr[k] = L[i]
        i += 1
        k += 1

    while j < len(R):
        arr[k] = R[j]
        j += 1
        k += 1

arr = [64, 34, 25, 12, 22, 11, 90]
mergeSort(arr)
print ("排序后的数组: ", arr)

输出结果：
排序后的数组: [11, 12, 22, 25, 34, 64, 90]