文章/答案/技术大牛

发布

社区首页 >专栏 >python 排序

python 排序

原创

织幻妖

修改于 2021-03-01 10:13:55

68200

代码可运行

文章被收录于专栏：用户7552167的专栏用户7552167的专栏

运行总次数：0

代码可运行

1.插入排序

插入排序是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

代码演示：

def insertionSort(arr):
    for i in range(1, len(arr)):
        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 = [9, 1, 8, 2, 7, 3, 6, 4, 0, 5]
print("排序前的数组:", arr)
insertionSort(arr)
print("使用插入排序")
print("排序后的数组:", arr)

执行效果：

排序前的数组: [9, 1, 8, 2, 7, 3, 6, 4, 0, 5]
使用插入排序
排序后的数组: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

2.冒泡排序

冒泡排序是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

代码演示：

def bubbleSort(arr):
    n = len(arr)

    # 遍历所有数组元素
    for i in range(n):

        # Last i elements are already in place
        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 = [9, 1, 8, 2, 7, 3, 6, 4, 0, 5]
print("排序前的数组:", arr)
bubbleSort(arr)

print("使用冒泡排序")
print("排序后的数组:", arr)

执行效果：

排序前的数组: [9, 1, 8, 2, 7, 3, 6, 4, 0, 5]
使用冒泡排序
排序后的数组: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

3.归并排序

归并排序是创建在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

分治法:

分割：递归地把当前序列平均分割成两半。
集成：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）。

代码演示：

def merge(arr, l, m, r):
    n1 = m - l + 1
    n2 = r - m

    # 创建临时数组
    L = [0] * (n1)
    R = [0] * (n2)

    # 拷贝数据到临时数组 arrays L[] 和 R[]
    for i in range(0, n1):
        L[i] = arr[l + i]

    for j in range(0, n2):
        R[j] = arr[m + 1 + j]

        # 归并临时数组到 arr[l..r]
    i = 0  # 初始化第一个子数组的索引
    j = 0  # 初始化第二个子数组的索引
    k = l  # 初始归并子数组的索引

    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1

    # 拷贝 L[] 的保留元素
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1

    # 拷贝 R[] 的保留元素
    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1


def mergeSort(arr, l, r):
    if l < r:
        m = int((l + (r - 1)) / 2)

        mergeSort(arr, l, m)
        mergeSort(arr, m + 1, r)
        merge(arr, l, m, r)


arr = [9, 1, 8, 2, 7, 3, 6, 4, 0, 5]

n = len(arr)
print("排序前的数组:", arr)

mergeSort(arr, 0, n - 1)
print("使用归并排序")
print("排序后的数组:", arr)

执行效果：

排序前的数组: [9, 1, 8, 2, 7, 3, 6, 4, 0, 5]
使用归并排序
排序后的数组: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

4.快速排序

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。

步骤为：

挑选基准值：从数列中挑出一个元素，称为"基准"（pivot）;
分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成;
递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

递归到最底部的判断条件是数列的大小是零或一，此时该数列显然已经有序。

选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。

代码演示：

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

    for j in range(low, high):

        # 当前元素小于或等于 pivot
        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)


# arr[] --> 排序数组
# low  --> 起始索引
# high  --> 结束索引

# 快速排序函数
def quickSort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)

        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)


arr = [9, 1, 8, 2, 7, 3, 6, 4, 0, 5]
n = len(arr)
print("排序前的数组:", arr)
quickSort(arr, 0, n - 1)
print("使用快速排序")
print("排序后的数组:", arr)

执行效果：

排序前的数组: [9, 1, 8, 2, 7, 3, 6, 4, 0, 5]
使用快速排序
排序后的数组: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

5.选择排序

选择排序是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

代码演示：

arr = [9,1,8,2,7,3,6,4,0,5]
print("排序前的数组:",arr)
for i in range(len(arr)):

    min_idx = i
    for j in range(i + 1, len(arr)):
        if arr[min_idx] > arr[j]:
            min_idx = j

    arr[i], arr[min_idx] = arr[min_idx], arr[i]
print("使用选择排序")
print("排序后的数组：",arr)

执行效果：

排序前的数组: [9, 1, 8, 2, 7, 3, 6, 4, 0, 5]
使用选择排序
排序后的数组： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

6.堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。

代码演示：

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1  # left = 2*i + 1
    r = 2 * i + 2  # right = 2*i + 2

    if l < n and arr[i] < arr[l]:
        largest = l

    if r < n and arr[largest] < arr[r]:
        largest = r

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # 交换

        heapify(arr, n, largest)


def heapSort(arr):
    n = len(arr)

    # Build a maxheap.
    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)


arr = [9,1,8,2,7,3,6,4,0,5]
print("排序前的数组:",arr)
heapSort(arr)
n = len(arr)
print("使用堆排序")
print("排序后的数组：",arr)

执行效果：

排序前的数组: [9, 1, 8, 2, 7, 3, 6, 4, 0, 5]
使用堆排序
排序后的数组： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

7.希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

代码演示：

def shellSort(arr):
    n = len(arr)
    gap = int(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 = int(gap / 2)


arr = [9,1,8,2,7,3,6,4,0,5]

n = len(arr)
print("排序前的数组:",arr)

shellSort(arr)

print("使用希尔排序")
print("排序后的数组：",arr)

执行效果：

排序前的数组: [9, 1, 8, 2, 7, 3, 6, 4, 0, 5]
使用希尔排序
排序后的数组： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

8.计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

代码演示：

def countSort(arr):
    output = [0 for i in range(256)]

    count = [0 for i in range(256)]

    ans = ["" for _ in arr]

    for i in arr:
        count[ord(i)] += 1

    for i in range(256):
        count[i] += count[i - 1]

    for i in range(len(arr)):
        output[count[ord(arr[i])] - 1] = arr[i]
        count[ord(arr[i])] -= 1

    for i in range(len(arr)):
        ans[i] = output[i]
    return ans


arr = "qwerasdfzxcv"
print("字符数组排序前",arr)
ans = countSort(arr)
print("使用计数排序")
print ( "字符数组排序前",ans)

执行效果：

字符数组排序前 qwerasdfzxcv
使用计数排序
字符数组排序前 ['a', 'c', 'd', 'e', 'f', 'q', 'r', 's', 'v', 'w', 'x', 'z']

补充个小知识

有时候代码里面如果有中文，执行代码会报一下错

SyntaxError: Non-UTF-8 code starting with '\xd7' in file D:/PycharmProjects/python/kuaisupaixu.py on line 3, but no encoding declared; see http://python.org/dev/peps/pep-0263/ for details