冒泡排序

1
2
3
4
5
6
7
def bubbleSort(nums):
    n = len(nums)
    for i in range(n):
        for j in range(n-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
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def merge(arr1, arr2):
    temp = []
    i, j = 0, 0
    n1, n2 = len(arr1), len(arr2)
    while i < n1 or j < n2:
        if i < n1 and j < n2:
            if arr1[i] <= arr2[j]:
                temp.append(arr1[i])
                i += 1
            else:
                temp.append(arr2[j])
                j += 1
        elif i < n1:
            temp.append(arr1[i])
            i += 1
        else:
            temp.append(arr2[j])
            j += 1
    return temp

def mergeSort(nums):
    if len(nums) <= 1: return nums
    mid = len(nums) // 2
    leftArray  = mergeSort(nums[:mid])
    rightArray = mergeSort(nums[mid:])
    sortedArray = merge(leftArray, rightArray)
    return sortedArray

插入排序

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

基数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def bucketSort(nums):
    maxNum = max(nums)
    maxNumSize = 0
    while maxNum:
        maxNumSize += 1
        maxNum //= 10
    
    k, cnt = 1, 0
    while cnt < maxNumSize:
        bucket = {num: [] for num in range(10)}
        for num in nums:
            bucket[num // k % 10].append(num)
        temp = []
        for _, lst in bucket.items():
            temp.extend(lst)
        nums = temp
        cnt += 1
        k *= 10
    
    return nums

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def findIndex(nums):
    temp = nums[0]
    i, j = 0, len(nums)-1
    while i < j:
        while i < j and nums[j] >= temp:
            j -= 1
        nums[i] = nums[j]
        while i < j and nums[i] < temp:
            i += 1
        nums[j] = nums[i]
    nums[i] = temp
    return i
    
def quickSort(nums):
    if len(nums) <= 1:
        return nums  
    index = findIndex(nums)
    quickSort(nums[:index])
    quickSort(nums[index+1:])
    return nums
print(quickSort(nums))