# Python代码实现十大经典排序算法，纯干货，建议收藏，遗失不补

O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序。

n：数据规模

k：“桶”的个数

In-place：占用常数内存，不占用额外内存

Out-place：占用额外内存

1. 算法步骤

2. 动图演示

3. 什么时候最快

4. 什么时候最慢

5. Python 代码实现

def bubbleSort(arr):

for i in range(1, len(arr)):

for j in range(0, len(arr)-i):

if arr[j] > arr[j+1]:

arr[j], arr[j + 1] = arr[j + 1], arr[j]

return arr

1. 算法步骤

2. 动图演示

3. Python 代码实现

def selectionSort(arr):

for i in range(len(arr) - 1):

# 记录最小数的索引

minIndex = i

for j in range(i + 1, len(arr)):

if arr[j]

minIndex = j

# i 不是最小数时，将 i 和最小数进行交换

if i != minIndex:

arr[i], arr[minIndex] = arr[minIndex], arr[i]

return arr

1. 算法步骤

2. 动图演示

3. Python 代码实现

def insertionSort(arr):

for i in range(len(arr)):

preIndex = i-1

current = arr[i]

while preIndex >= 0 and arr[preIndex] > current:

arr[preIndex+1] = arr[preIndex]

preIndex-=1

arr[preIndex+1] = current

return arr

1. 算法步骤

2. Python 代码实现

def shellSort(arr):

import math

gap=1

while(gap

gap = gap*3+1

while gap > 0:

for i in range(gap,len(arr)):

temp = arr[i]

j = i-gap

while j >=0 and arr[j] > temp:

arr[j+gap]=arr[j]

j-=gap

arr[j+gap] = temp

gap = math.floor(gap/3)

return arr

However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.

1. 算法步骤

2. 动图演示

3. Python 代码实现

def mergeSort(arr):

import math

if(len(arr)

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]

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

1. 算法步骤

2. 动图演示

3. Python 代码实现

def quickSort(arr, left=None, right=None):

left = 0 if not isinstance(left,(int, float)) else left

right = len(arr)-1 if not isinstance(right,(int, float)) else right

if left

partitionIndex = partition(arr, left, right)

quickSort(arr, left, partitionIndex-1)

quickSort(arr, partitionIndex+1, right)

return arr

def partition(arr, left, right):

pivot = left

index = pivot+1

i = index

while i

if arr[i]

swap(arr, i, index)

index+=1

i+=1

swap(arr,pivot,index-1)

return index-1

def swap(arr, i, j):

arr[i], arr[j] = arr[j], arr[i]

1. 算法步骤

2. 动图演示

3. Python 代码实现

def buildMaxHeap(arr):

import math

for i in range(math.floor(len(arr)/2),-1,-1):

heapify(arr,i)

def heapify(arr, i):

left = 2*i+1

right = 2*i+2

largest = i

if left arr[largest]:

largest = left

if right arr[largest]:

largest = right

if largest != i:

swap(arr, i, largest)

heapify(arr, largest)

def swap(arr, i, j):

arr[i], arr[j] = arr[j], arr[i]

def heapSort(arr):

global arrLen

arrLen = len(arr)

buildMaxHeap(arr)

for i in range(len(arr)-1,0,-1):

swap(arr,0,i)

arrLen -=1

heapify(arr, 0)

return arr

1. 动图演示

2. Python 代码实现

def countingSort(arr, maxValue):

bucketLen = maxValue+1

bucket = [0]*bucketLen

sortedIndex =0

arrLen = len(arr)

for i in range(arrLen):

if not bucket[arr[i]]:

bucket[arr[i]]=0

bucket[arr[i]]+=1

for j in range(bucketLen):

while bucket[j]>0:

arr[sortedIndex] = j

sortedIndex+=1

bucket[j]-=1

return arr

1. 什么时候最快

2. 什么时候最慢

1. 基数排序 vs 计数排序 vs 桶排序

2. LSD 基数排序动图演示

• 发表于:
• 原文链接http://kuaibao.qq.com/s/20180322A1C7W700?refer=cp_1026
• 腾讯「云+社区」是腾讯内容开放平台帐号（企鹅号）传播渠道之一，根据《腾讯内容开放平台服务协议》转载发布内容。
• 如有侵权，请联系 yunjia_community@tencent.com 删除。

2018-03-20

2021-09-28

2021-09-28

2018-03-16

2018-03-15

2021-09-28

2018-07-19

2018-04-23

2018-03-21

2021-09-28

2021-09-28

2021-09-28