python 实现排序方法，常见排序方法，快速排序，归并排序，谢尔排序，堆排序，冒泡排序，选择排序，插入排序_python堆排序vs归并vs快速排序

一、冒泡排序：

nums = [1,3,2,5,4,9,6]

def bubbleSort(alist):
    n = len(alist)
    for passnum in range(n-1,-1,-1):
        for i in range(passnum):
            if alist[i] > alist[i+1]:
                alist[i],alist[i+1] = alist[i+1],alist[i]
    return alist
 
print(bubbleSort(nums))

改进：提前排好序就停止

def shortBubbleSort(alist):
    n = len(alist)
    right = n-1
    exchange = True
    while right < 0 and exchange:
        flag = False
        for i in range(right):
            if alist[i+1] < alist[i]:
                flag = True
                alist[i],alist[i+1] = alist[i+1],alist[i]
        right -= 1
    return alist
print(shortBubbleSort(nums))

 二、选择排序：

def selectionSort(alist):
    for i in range(len(alist)-1,0,-1):
        pos = 0
        for j in range(1,i+1):
            if alist[pos] < alist[j]:
                pos = j
        alist[pos],alist[i] = alist[i],alist[pos]
    return alist
print(selectionSort(nums))

三、插入排序：

def insertionSort(alist):
    for index in range(1,len(alist)):
 
        currentvalue = alist[index]
        pos = index
        while pos > 0 and alist[pos-1] > alist[pos]:
            alist[pos] = alist[pos-1]
            pos -= 1
        alist[pos] = currentvalue
    return alist
print(insertionSort(nums))

四、希尔排序

# -------------------------------------------------------------------------------
# coding:utf-8
# Description:  
# Reference:
# Author: dacongming
# Date:   2023/7/10
# -------------------------------------------------------------------------------
def shell_sort(arr):
    n = len(arr)
    gap = n // 2
 
    while gap > 0:
        for i in range(gap,n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2
    return arr
 
arr = [9, 2, 5, 1, 6, 4, 8, 3, 7]
sorted_arr = shell_sort(arr)
print(sorted_arr)  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

以上代码中，shell_sort函数接收一个列表作为参数，使用希尔排序算法对列表进行排序。首先设置一个初始的间隔大小gap，初始值为列表长度的一半。然后不断将间隔大小减半，直到间隔大小为1。在每个间隔大小下，对列表中每个间隔位置的元素进行插入排序。

插入排序的思想是将当前元素插入到已排序的序列中的正确位置。在希尔排序中，通过设置不同的间隔，可以使得列表中的元素跳跃式地移动，从而加快排序的速度。最后，希尔排序会在间隔大小为1时完成最后一次排序，得到最终的有序列表。

五、归并排序

# coding:utf-8
# Description:  
# Reference:
# Author: dacongming
# Date:   2023/7/10
# -------------------------------------------------------------------------------
 
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
 
    left = merge_sort(left)
    right = merge_sort(right)
    return merge(left,right)
 
def merge(left, right):
    result = []
    i = j = 0
 
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
 
    result.extend(left[i:])
    result.extend(right[j:])
    return result
 
arr = [9, 2, 5, 1, 6, 4, 8, 3, 7]
sorted_arr = merge_sort(arr)
print(sorted_arr)  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

以上代码中，merge_sort函数接收一个列表作为参数，使用递归的方式进行归并排序。首先将列表分成左右两部分，然后递归调用merge_sort函数对左右两部分进行排序。然后调用merge函数将排序好的左右两部分合并成一个有序的列表并返回。

merge函数接收两个有序的列表作为参数，通过比较左右两个列表的元素大小，逐个选择较小的元素放入结果列表中。最后将剩余的元素追加到结果列表中并返回。

六、快速排序

# -------------------------------------------------------------------------------
# coding:utf-8
# Description:  
# Reference:
# Author: dacongming
# Date:   2023/7/10
# -------------------------------------------------------------------------------
 
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        less = [x for x in arr[1:] if x <= pivot]
        greater = [x for x in arr[1:] if x > pivot]
        return quick_sort(less) + [pivot] + quick_sort(greater)
 
arr = [9, 2, 5, 1, 6, 4, 8, 3, 7]
sorted_arr = quick_sort(arr)
print(sorted_arr)  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

 以上代码中，quick_sort函数接收一个列表作为参数，使用快速排序算法对列表进行排序。快速排序的基本思想是通过选择一个基准元素（通常是列表的第一个元素），将列表分割成两个子列表，其中一个子列表的元素都小于等于基准元素，另一个子列表的元素都大于基准元素。然后递归地对两个子列表进行快速排序，最后将两个子列表和基准元素合并起来。

在代码中，首先判断列表的长度。如果列表长度小于等于1，则直接返回该列表。否则，选择列表的第一个元素作为基准元素pivot。然后使用列表推导式分别生成两个子列表less和greater，其中less包含小于等于基准元素的元素，greater包含大于基准元素的元素。最后，递归地对两个子列表进行快速排序，并将排序结果与基准元素合并起来。

七：堆排序

# -------------------------------------------------------------------------------
# coding:utf-8
# Description:  
# Reference:
# Author: dacongming
# Date:   2023/7/10
# -------------------------------------------------------------------------------
 
def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
 
    if left < n and arr[i] < arr[left]:
        largest = left
 
    if right < n and arr[largest] < arr[right]:
        largest = right
 
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
 
def heap_sort(arr):
    n = len(arr)
 
    for i in range(n, -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)
 
    return arr
 
arr = [9, 2, 5, 1, 6, 4, 8, 3, 7]
sorted_arr = heap_sort(arr)
print(sorted_arr)  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

以上代码中，heapify函数用于将一个数组中的元素调整为最大堆的形式。该函数接收三个参数：数组arr、数组的长度n和当前要调整的元素下标i。首先，将当前元素下标i设为最大元素下标largest，然后分别计算左子节点和右子节点的下标。如果左子节点存在并且大于当前元素，则将左子节点的下标设为最大元素下标largest；如果右子节点存在并且大于当前元素，则将右子节点的下标设为最大元素下标largest。如果最大元素下标largest不等于当前元素下标i，则交换当前元素和最大元素，然后递归地对最大元素所在的子树进行堆化。

heap_sort函数用于对数组进行堆排序。该函数接收一个数组arr作为参数。首先，对数组进行初始化堆化，即从最后一个非叶子节点开始，依次对每个非叶子节点进行堆化。然后，依次将堆顶元素（最大元素）与最后一个元素交换，并将数组长度减一，再对堆顶元素进行堆化。重复这个过程，直到数组被完全排序。最后返回排序后的数组