python-10.菜鸟教程-5

Python 插入排序

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

实例

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 = [12, 11, 13, 5, 6]
insertionSort(arr)
print("排序后的数组:")
for i in range(len(arr)):
    print("%d" % arr[i])

执行以上代码输出结果为：

排序后的数组:
5
6
11
12
13

Python 快速排序

快速排序使用分治法（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 = [10, 7, 8, 9, 1, 5]
n = len(arr)
quickSort(arr, 0, n - 1)
print("排序后的数组:")
for i in range(n):
    print("%d" % arr[i])

执行以上代码输出结果为：

排序后的数组:
1
5
7
8
9
10

参考内容：

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = 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)


print(quicksort([3, 6, 8, 19, 1, 5]))  # [1，3, 5, 6, 8, 19]

Python 选择排序

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

实例

import sys

A = [64, 25, 12, 22, 11]

for i in range(len(A)):

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

    A[i], A[min_idx] = A[min_idx], A[i]

print("排序后的数组：")
for i in range(len(A)):
    print("%d" % A[i])

执行以上代码输出结果为：

排序后的数组：
11
12
22
25
64

 简单的方法更好用，简单的问题也不容易发现。第二个函数的交换位置我想了很久。

"""
选择排序
Selectionsort.py
"""


# 以序号为依据
def Selectionsort1():
    A = [-9, -8, 640, 25, 12, 22, 33, 23, 45, 11, -2, -5, 99, 0]
    for i in range(len(A)):
        min = i
        for j in range(i + 1, len(A)):  # 上一个值右边的数组
            if A[min] > A[j]:  # 使min为最小值，遇到比min小的值就赋值于min
                min = j

        A[i], A[min] = A[min], A[i]  # 交换最小值到左边

    print('Selectionsort1排序后的数组：', A)


# 以数值为依据
def Selectionsort2():
    A = [-9, -8, 640, 25, 12, 22, 33, 23, 45, 11, -2, -5, 99, 0]
    counter = 0  # 记录循环次数和位置
    array = []

    for i in A:
        counter += 1
        for j in A[counter:]:  # 缩小范围
            if i > j:  # 使i为最小值
                i = j

            A.remove(i)
            A.insert(counter - 1, i)
            # 把最小值置于列表左边，避免重复比较

        array.append(i)

    print('Selectionsort2排序后的数组：', array)


Selectionsort1()
Selectionsort2()

Selectionsort1排序后的数组： [-9, -8, -5, -2, 0, 11, 12, 22, 23, 25, 33, 45, 99, 640]
Selectionsort2排序后的数组： [-9, -8, -5, -2, 0, 11, 12, 22, 23, 25, 33, 45, 99, 640]

可选择升序和降序。

# 待排序数组arr，排序方式order>0升序，order<0降序
def selectSort(arr, order):
    rborder = len(arr)
    for i in range(0, rborder):
        p = i
        j = i + 1
        while j < rborder:
            if ((arr[p] > arr[j]) and (int(order) > 0)) or ((arr[p] < arr[j]) and (int(order) < 0)):
                p = j
            j += 1
        arr[i], arr[p] = arr[p], arr[i]
        i += 1
    return arr


A = [64, 25, 12, 22, 11]
print(selectSort(A, -1))
print(selectSort(A, 1))

[64, 25, 22, 12, 11]
[11, 12, 22, 25, 64]

Python 冒泡排序

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

实例

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 = [64, 34, 25, 12, 22, 11, 90]

bubbleSort(arr)

print("排序后的数组:")
for i in range(len(arr)):
    print("%d" % arr[i]),

执行以上代码输出结果为：

排序后的数组:
11
12
22
25
34
64
90

参考：

"""
冒泡排序
Bubblesort.py
"""

from random import randrange, shuffle


def Bubblesort():
    array = []

    while len(array) < 12:  # 范围内随机取12个数值
        array.append(randrange(-99, 101, 3))
    shuffle(array)  # 打乱数组

    print('排序前数组：{}'.format(array))

    for i in range(12):
        for j in range(11 - i):
            if array[j] > array[j + 1]:  # 遇到较小值前后交换
                array[j], array[j + 1] = array[j + 1], array[j]

    print('排序后数组：{}'.format(array))


Bubblesort()

输出结果：

排序前数组：[-42, 9, -51, -24, -42, 27, 9, -87, -42, 90, -93, -6]
排序后数组：[-93, -87, -51, -42, -42, -42, -24, -6, 9, 9, 27, 90]

可选择升序和降序。

# 可选升降序的冒泡排序, order>0升序，order<0降序


def bubbleSort(arr, order):
    max = len(arr)
    for i in range(0, max):
        j = 1
        while j < max - i:
            if ((arr[j - 1] > arr[j]) and (int(order) > 0)) or ((arr[j - 1] < arr[j]) and (int(order) < 0)):
                arr[j - 1], arr[j] = arr[j], arr[j - 1]
            j += 1
        i += 1
    return arr


A = [64, 25, 12, 22, 11]
print(bubbleSort(A, -1))
print(bubbleSort(A, 1))

输出结果：

[64, 25, 22, 12, 11]
[11, 12, 22, 25, 64]