排序算法总结

发表于 | 更新于: | 分类于 ， | | 阅读数
字数统计: 790 | 阅读时长 ≈ 4

生成随机数列

1
2
3
4
from random import randint

def generateRandomArray(n=10, min=0, max=100):
    return [randint(min, max) for _ in range(n)]

生成基本有序的数列

1
2
3
4
5
6
def generateNearlyOrderedArray(n=10, swapTimes=2):
    arr = list(range(n))
    for _ in range(swapTimes):
        i,j = randint(0, n-1),randint(0, n-1)
        arr[i], arr[j] = arr[j], arr[i]
    return arr

测试算法性能

1
2
3
4
5
6
7
8
from timeit import Timer

def testSort(func, nums):# func：检测的算法函数；nums：传入的数组
    nums =  func(nums)
    assert len(nums), "返回数组为空\n"

t1 = Timer('testSort(XXXSort, nums)', 'from __main__ import testSort, XXXSort, nums')
print('XX排序算法：%s s' %t1.timeit(number=1))

冒泡排序

1
2
3
4
5
6
7
def bubbleSort(nums):
    n=len(nums)
    for i in range(n-1,0,-1):
        for j in range(i):
            if nums[j]>nums[j+1]:
                nums[j],nums[j+1]=nums[j+1],nums[j]
    return nums

上面这个是向后冒泡，还有个向前冒泡的版本：(可以由i判断向哪冒泡)

1
2
3
4
5
6
def bubbleSort(nums):
    for i in range(n:=len(nums)):
        for j in range(n-1,i,-1):
            if nums[j]<nums[j-1]:
                nums[j], nums[j - 1] = nums[j - 1], nums[j]
    return nums

选择排序

1
2
3
4
5
6
7
8
9
def selectionSort(nums):
    n = len(nums)
    for i in range(n - 1):
        idx = i
        for j in range(i+1, n):
            if nums[j] < nums[idx]:
                idx = j
        nums[i], nums[idx] = nums[idx], nums[i]
    return nums

插入排序

1
2
3
4
5
6
7
8
def insertionSort(nums):
    n=len(nums)
    for i in range(1,n):
        value,pos=nums[i],i
        while nums[pos-1]>value and pos>0:
            nums[pos],pos=nums[pos-1],pos-1
        nums[pos]=value
    return nums

快速排序

1
2
3
4
5
6
7
8
9
def quickSort(nums,l,r):	# 闭区间[l,r]
    if l>=r:return
    i,j,x=l,r,nums[l+r>>1]
    while i<j:
        while nums[i]<x:i+=1
        while nums[j]>x:j-=1
        if i<j:nums[i],nums[j]=nums[j],nums[i]
    quickSort(nums,l,j)
    quickSort(nums,j+1,r)

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
tmp=[0]*n
def mergeSort(nums,l,r):	# 闭区间[l,r]
    if l>=r:return
    mid=l+(r-l>>1)
    mergeSort(nums,l,mid)
    mergeSort(nums,mid+1,r)

    k,i,j=0,l,mid+1
    while i<=mid and j<=r:
        if nums[i]<nums[j]:
            tmp[k]=nums[i];k+=1;i+=1
        else:
            tmp[k] = nums[j];k += 1;j += 1
    while i<=mid:
        tmp[k] = nums[i];k += 1;i += 1
    while j<=r:
        tmp[k] = nums[j];k += 1;j += 1

    nums[l:r+1]=tmp[0:r+1-l]

中间部分可以这样记忆（虽然不可以这样运行）

1
2
3
4
5
6
7
8
9
10
k,i,j=0,l,mid+1	# 分成两部分，[l,mid],[mid+1,r]
while i<=mid and j<=r:
    if nums[i]<nums[j]:
        tmp[k++]=nums[i++]
    else:
        tmp[k++] = nums[j++]
while i<=mid:
    tmp[k++] = nums[i++]
while j<=r:
    tmp[k++] = nums[j++]

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def shellSort(nums):
    gap = len(nums)
    while gap:=gap//2 > 0:
        for i in range(gap):
            gapInsetionSort(nums, i, gap)
    return nums
    
def gapInsetionSort(nums,startpos,gap): # 辅助函数
    n=len(nums)
    for i in range(startpos+gap,n,gap):
        value,pos=nums[i],i
        while pos>startpos and nums[pos-gap]>value:
            nums[pos],pos=nums[pos-gap],pos-gap
        nums[pos]=value
为什么python不支持自增(i++)?

《learning python》这样解释:

although Python now supports statements like X += Y, it still does not have C’s auto-increment/decrement operators (e.g., X++, −−X). These don’t quite map to the Python object model because Python has no notion of in-place changes to immutable objects like numbers.

不要打赏，只求关注呀QAQ