V-Note

A female robot

站点工具


river:20210219_python_sort

Python 排序算法

参考这里的记录。

生成随机数列

实际上只要引入 randint 就可以了。

from random import randint
def generateRandomArray(n, min, max):
    arr = []
    arr = [randint(min, max) for x in range(n)]
    return arr

判断数列是否有序

遍历列表,需要前项比后项小。

def isSorted(alist):
    for i in range(0, len(alist)-1):
        if alist[i] > alist[i+1]:
            return False
    return True

冒泡排序

依次对比相邻两项,并排序,直到顺序正确。
——费时,唯一的优势:可以在发现列表已排好时立刻结束,时间复杂度O(n^2^),空间复杂度O(1)

1.gif

# 冒泡排序
def bubbleSort(alist):
    n = len(alist)
    for i in range(n-1, 0, -1):
        for j in range(0, i):
            if alist[j] > alist[j+1]:
                alist[j], alist[j+1] = alist[j+1], alist[j]
    return alist

优化的冒泡排序(如果已排序好即结束):

# 冒泡排序
def bubbleSort(alist):
    n = len(alist)
    exchange = False
    for i in range(n-1, 0, -1):
        for j in range(0, i):
            if alist[j] > alist[j+1]:
                alist[j], alist[j+1] = alist[j+1], alist[j]
                exchange = True
        # 如果发现整个排序过程中没有交换,提前结束
        if not exchange:
            break
    return alist

选择排序

每次抽取最小的元素往前排列。。
——需要 n-1 次遍历,时间复杂度O(n^2^)

2.gif

# 选择排序
def selectionSort(alist):
    n = len(alist)

    for i in range(n - 1):
        # 寻找[i,n]区间里的最小值
        min_index = i
        for j in range(i+1, n):
            if alist[j] < alist[min_index]:
                min_index = j
        alist[i], alist[min_index] = alist[min_index], alist[i]
    return alist

插入排序

和选择排序一样,只是读取下一个元素往前面插入。

3.gif

# 插入排序
def insertionSort(alist):
    for i in range(1,len(alist)):
        currentvalue=alist[i]
        position=i
        while alist[position-1]>currentvalue and position>0:
            alist[position]=alist[position-1]
            position=position-1
        alist[position]=currentvalue
    return alist

希尔排序

相当于将数组下再分由长到短的区间做插入排序。

4.gif

# 希尔排序
def shellSort(alist):
    n = len(alist)
    gap = n // 2
    while gap > 0:
        for i in range(gap):
            gapInsetionSort(alist, i, gap)
        gap = gap // 2
    return alist

# # start子数列开始的起始位置, gap表示间隔

def gapInsetionSort(alist,startpos,gap):
    #希尔排序的辅助函数
    for i in range(startpos+gap,len(alist),gap):
        position=i
        currentvalue=alist[i]

        while position>startpos and alist[position-gap]>currentvalue:
            alist[position]=alist[position-gap]
            position=position-gap
        alist[position]=currentvalue

归并排序

待补充。。

5.gif

快速排序

每次选取未排序部分的一个元素(通常是第一个),把后续元素相对较小的都放左边,相对较大的都放右边。
——问题是,如果已经有近似正确的排序,其时间复杂度依然要到O(n^2^)。。

6.gif

def __quickSort(alist, l, r):

    #当数列的大小比较小的时候,数列近乎有序的概率较大
    # if (r - l <= 15):
    #     insertionSortHelp(alist, l, r)
    #     return

    if l >= r:
        return
    # p = partition(alist, l, r)
    p = partitionQS(alist, l, r)

    __quickSort(alist, l, p-1)
    __quickSort(alist, p+1, r)

# 在alist[l...r]中寻找j,使得alist[l...j] <= alist[l], alist[j+1...r] >alist[l]
def partition(alist, l, r):
    pos = randint(l, r)
    alist[pos], alist[l] = alist[l], alist[pos]
    v = alist[l]
    # v = alist[l]
    j = l
    i = l + 1
    while i <= r:
        if alist[i] <= v:
            alist[j+1],alist[i] = alist[i],alist[j+1]
            j += 1
        i += 1
    alist[l], alist[j] = alist[j], alist[l]
    return j
river/20210219_python_sort.txt · 最后更改: 2021/09/15 12:14 由 站点编辑1