python集合排序_排序算法集合

#### 冒泡排序

### 时间复杂度是： 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

希望与广大网友互动？？

点此进行留言吧！

总结

以上是生活随笔为你收集整理的python集合排序_排序算法集合的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。