常规排序

🏴 常规排序算法实践📶 🏴

1.冒泡排序

平均时间复杂度O(n^2)，最好O(n)

def bubble_sort(l):
    for i in range(len(l)-1):
        for j in range(len(l)-i-1):
            if l[j] > l[j+1]:
                l[j],l[j+1]=l[j+1],l[j]
    return l

l = [4,1,5,7,3,9,2]
print(bubble_sort(l))

2.选择排序

平均时间复杂度O(n^2)，最好O(n^2)

def selection_sort(nums):
    for i in range(len(nums) - 1):  # 遍历 len(nums)-1 次
        minIndex = i
        for j in range(i + 1, len(nums)):
            if nums[j] < nums[minIndex]:  # 更新最小值索引
                minIndex = j
        nums[i], nums[minIndex] = nums[minIndex], nums[i] # 把最小数交换到前面
    return nums

nums = [4,1,5,7,3,9,2]
print(selection_sort(nums))

3.插入排序

平均时间复杂度O(n^2)，最好O(n)

def insertion_sort(nums):
    for i in range(len(nums)): # 遍历 len(nums) 次
         # cursor 保存当前待插入的数
        cursor = nums[i]
        pos = i

        while pos > 0 and nums[pos - 1] > cursor:
            # 将比 cursor 大的元素向后移动
            nums[pos] = nums[pos - 1]
            pos = pos - 1

        nums[pos] = cursor  # 待插入的数的正确位置
    return nums

nums = [4,1,5,7,3,9,2]
print(insertion_sort(nums))

4.快速排序

平均时间复杂度O(nlogn)，最坏O(n^2)

def quick_sort(lists,i,j):
    if i >= j:
        return list
    pivot = lists[i]
    low = i
    high = j
    while i < j:
        while i < j and lists[j] >= pivot:
            j -= 1
        lists[i]=lists[j]
        while i < j and lists[i] <=pivot:
            i += 1
        lists[j]=lists[i]
    lists[j] = pivot
    quick_sort(lists,low,i-1)
    quick_sort(lists,i+1,high)
    return lists

if __name__=="__main__":
    lists=[30,24,5,58,18,36,12,42,39]
    print("排序前的序列为：")
    for i in lists:
        print(i,end =" ")
    print("\n排序后的序列为：")
    for i in quick_sort(lists,0,len(lists)-1):
        print(i,end=" ")

5.归并排序

平均时间复杂度O(nlogn)，最坏O(nlogn)

ef mergeSort(arr):
    import math
    if(len(arr)<2):
        return arr
    middle = math.floor(len(arr)/2)
    left, right = arr[0:middle], arr[middle:]
    return merge(mergeSort(left), mergeSort(right))

def merge(left,right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0));
        else:
            result.append(right.pop(0));
    while left:
        result.append(left.pop(0));
    while right:
        result.append(right.pop(0));
    return result

6. 复杂度一览表

排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	排序方式	稳定性
冒泡排序	O(n²)	O(n)	O(n²)	O(1)	内部排序	稳定
选择排序	O(n²)	O(n²)	O(n²)	O(1)	内部排序	不稳定
插入排序	O(nlogn)	O(n)	O(n²)	O(1)	内部排序	稳定
快速排序	O(nlogn)	O(nlogn)	O(n²)	O(logn)	内部排序	不稳定
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	外部排序	稳定