排序算法集合

#### 冒泡排序
### 时间复杂度是： O(n^2)
### 空间复杂度是： O(1)
def BubbleSort(li):
    for i in range(len(li)): # i = 0
        flag = True
        for j in range(len(li) - i - 1): ### j = 0, j = 1, j =2
            if li[j] > li[j+1]:  ### li[0]=1 > li[1]=2 | li[1]=2 > li[2]=3 | li[2] > li[3]
                li[j], li[j+1] = li[j+1], li[j]
                flag = False
        if flag:
            return None

#### 选择排序
### 时间复杂度是：O(n^2)
### 空间复杂度是：O(1)
def SelectSort(li):
    for i in range(len(li)):
        minLoc = i
        for j in range(i + 1, len(li)):
           if li[j] < li[minLoc]:
                li[j], li[minLoc] = li[minLoc], li[j]


#### 插入排序
#### 时间复杂度：O(n^2)
#### 空间复杂度；O(1)
def InsertSort(li):
    for i in range(1, len(li)):
        tmp = li[i]  ## i=2, tmp = 4
        j = i - 1   ### j = 1
        while j >= 0 and li[j] > tmp:  ### li[1] = 7 > tmp = 4 | li[0]=5 > tmp=4
            li[j+1] = li[j]  ###  j = 1
            j = j - 1   ### j = 0  | j = -1

        li[j + 1] = tmp  ### li[0] = tmp = 4


#### 快速排序
#### 时间复杂度：O(nlogn)
def partition(li, left, right):
    tmp = li[left]
    while left < right:
        while left < right and li[right] >= tmp:
            right = right - 1
        li[left] = li[right]
        while left < right and li[left] <= tmp:
            left = left + 1
        li[right] = li[left]
    li[left] = tmp
    return left

def Quick_Sort(li, left, right):
    if left < right:
        mid = partition(li, left, right)  ### O(n)
        Quick_Sort(li, left, mid-1)   ####  O(logn)
        Quick_Sort(li, mid+1,right)

### 归并排序
### 时间复杂度：O(nlogn)
### 空间复杂度：O(n)
#### python 底层 sorted()函数， 采用的排序算法是 TimSorted 包含了归并排序和插入排序
#### TimSorted 的时间复杂度是：O(nlogn)
def merge(li, low, mid, high):
    i = low
    j = mid + 1
    ltmp = []
    while i <= mid and j <= high:
        if li[i] <= li[j]:
            ltmp.append(li[i])
            i += 1
        else:
            ltmp.append(li[j])
            j += 1
    while i <= mid:
        ltmp.append(li[i])
        i += 1
    while j <= high:
        ltmp.append(li[j])
        j += 1
    li[low:high+1] = ltmp

def mergeSort(li, low, high):
    if low < high:
        mid = (low+high) // 2
        ### 分解
        mergeSort(li, low, mid)  ### O(logn)
        mergeSort(li, mid+1, high)
        print('分解后：',li[low:high + 1])
        ### 合并
        merge(li, low, mid, high)
        print('合并后：', li[low:high + 1])


###
### 计数排序
def countSort(li):
    count = [0 for x in range(11)]

    for i in li:
        count[i] += 1

    print(count)
    li.clear()
    for n, num in enumerate(count):
        ### n : 索引 对应的是li中的值  n = 2
        ### num: 索引出现的次数 对应的是li中的值出现的次数 num = 1
        for x in range(num):
            li.append(n)




li = [10,4,6,3,8,2,5,7]
countSort(li)
# mergeSort(li, 0, len(li)-1)


exit()




# li = [5,7,4,6,3,1,2,9,8]
#
# Quick_Sort(li, 0, len(li)-1)
# print(li)
# exit()

import time
import random

li = [random.randint(0, 10000) for i in range(100000)]
start_time = time.time()
Quick_Sort(li, 0, len(li)-1)
print("快速排序时间：%s" % (time.time() - start_time))

li = [random.randint(0, 10000) for i in range(100000)]
start_time = time.time()
BubbleSort(li)
print("冒泡排序时间：%s" % (time.time() - start_time))

li = [random.randint(0, 10000) for i in range(100000)]
start_time = time.time()
SelectSort(li)
print("选择排序时间：%s" % (time.time() - start_time))

li = [random.randint(0, 10000) for i in range(100000)]
start_time = time.time()
InsertSort(li)
print("插入排序时间：%s" % (time.time() - start_time))

 

本文地址：https://blog.csdn.net/qq_37156624/article/details/109645732