注意：排序方式：从左至右按照由小到大的顺序，即升序。

十兄弟之lowB三人组：

平均时间复杂度为

1.冒泡排序

#冒泡排序
def bubble_sort(li):#最多走n-1趟for i in range(len(li)-1):flag = False #标志位判断是否已经是有序序列#每趟从位置0走到位置n-i-1for j in range(len(li)-i-1):if li[j]>li[j+1]:li[j+1],li[j] = li[j],li[j+1]flag = Trueprint("第{}趟排序为{}".format(i,li))if not flag:breakif __name__ == "__main__":li = [2,3,4,9,7,6,5,10,1]bubble_sort(li)

      

2.选择排序：

#选择排序
def select_sort(li):#排序一共走了n-1趟for i in range(len(li)-1):#最小值的位置为本轮的第一个值位置min_loc = i#每趟排序从未排序的第一个值到末尾for j in range(i+1,len(li)):#如果某值小于min_loc位置的值，就让min_loc指向该值if li[j] < li[min_loc]:min_loc = j#交换位置li[i],li[min_loc] = li[min_loc],li[i]print("第{}趟排序为{}".format(i,li))if __name__ == "__main__":li = [2,3,4,9,7,6,5,10,1]select_sort(li)

输出结果：

3.插入排序：

#插入排序
def insert_sort(li):#从第二个数开始往左面插入，一共有n-1趟for i in range(1,len(li)):#j指向i-1位置j = i-1#temp保存li[i]位置的值，由于Python的列表中存储的是元素的地址，可以认为temp和li[i]都指向同一个值。temp = li[i]#当j往左移动时j<0会退出，temp指向的值比li[j]指向的值大时退出循环while j >=0 and temp < li[j]:#li[j]指向的那一个值传递给li[j+1]li[j+1] = li[j]#j往左边移动j = j-1#退出循环，li[j+1]指向temp指向的那个值，即需要插入的那个值li[j+1] = tempprint("第{}趟排序为{}".format(i,li))if __name__ == "__main__":li = [2,3,4,9,7,6,5,10,1]insert_sort(li)

输出结果：

 

十兄弟之NB三人组：

1.快速排序：平均时间复杂度为,当序列正好是逆排序时，对其进行正排序（由小到大），为最坏情况，时间复杂度为，但这种情况出现次数非常少，一般通过先随机选择中间值降低其出现概率。

#快速排序
def partition(li,left,right):#temp存放初始中间值，默认指向列表第一个元素temp = li[left]while left < right:#当左指针小于右指针且li[right]指向的元素大于等于temp指向的值时，右指针向左移动while left<right and li[right]>=temp:right -= 1把li[right]指向的值传递给li[left]li[left] = li[right]#当左指针小于右指针且li[left]指向的元素小于等于temp指向的值时，左指针向右移动while left<right and li[left]<=temp:left += 1li[right] = li[left]#当左右指针指向同一个位置时，把temp指向的值传递给li[left]或者li[right]   li[left] = temp#返回left或者right指向的位置return left
#快排，用递归
def quick_sort(li,left,right):if left < right:mid = partition(li,left,right)quick_sort(li,left,mid-1)quick_sort(li,mid+1,right)if __name__ == "__main__":li = [2,3,4,9,7,6,5,10,1]quick_sort(li,0,len(li)-1)print(li)

输出结果：

改进版：随机快速排序法

#随机快速排序
import random
def partition(li,left,right):#index表示在列表的下标范围内随机选择一个位置index = random.randint(left,right)#让随机选择的这个位置的值和li[left]指向的值做交换，实际上是两个指针的指向改变li[left],li[index] = li[index],li[left]#temp存放初始中间值，默认指向列表第一个元素temp = li[left]while left < right:#当左指针小于右指针且li[right]指向的元素大于等于temp指向的值时，右指针向左移动while left<right and li[right]>=temp:right -= 1把li[right]指向的值传递给li[left]li[left] = li[right]#当左指针小于右指针且li[left]指向的元素小于等于temp指向的值时，左指针向右移动while left<right and li[left]<=temp:left += 1li[right] = li[left]#当左右指针指向同一个位置时，把temp指向的值传递给li[left]或者li[right]   li[left] = temp#返回left或者right指向的位置return left
#快排，用递归
def quick_sort(li,left,right):if left < right:mid = partition(li,left,right)quick_sort(li,left,mid-1)quick_sort(li,mid+1,right)if __name__ == "__main__":li = [2,3,4,9,7,6,5,10,1]quick_sort(li,0,len(li)-1)print(li)

非递归式：快排

#快速排序(非递归式)
import random
def partition(li,left,right):index = random.randint(left,right)li[left],li[index] = li[index],li[left]temp = li[left]while left < right:while left<right and li[right]>=temp:right -= 1li[left] = li[right]while left<right and li[left]<=temp:left += 1li[right] = li[left]li[left] = tempreturn left
#做一个栈，从栈中先取出right,后取出left,分块排序
def quick_sort(li,left,right):temp = [left,right]while temp:right = temp.pop()left = temp.pop()index = partition(li,left,right)if left < index-1:temp.append(left)temp.append(index-1)if right > index+1:temp.append(index+1)temp.append(right)return liif __name__ == "__main__":li = [2,3,12,9,7,6,5,10,14]quick_sort(li,0,len(li)-1)print(li)

输出结果：

2.归并排序：时间复杂度为,空间复杂度为

#归并排序
def merge(li,low,mid,high):i = low#由中点mid分为两块，一块为（low,mid）,另一块为（mid+1,high）j = mid+1#新建一个列表用于存储排好序的值ltemp = []#要求i<=mid并且j<=highwhile i<=mid and j<=high:#如果li[i]指向的值小于等于li[j]指向的值，将li[i]指向的值添加进ltemp列表中，我认为这里应该加上=等于号，为了稳定性。if li[i] <= li[j]:ltemp.append(li[i])i += 1else:ltemp.append(li[j])j += 1#当i>mid或者j>high时，没遍历完的依次放入ltmp列表中while i <= mid:ltemp.append(li[i])i += 1while j <= high:ltemp.append(li[j])j += 1#这里是要把排好序的部分由ltemp传递给li中对应位置，切不可li=ltempli[low:high+1] = ltempdef merge_sort(li,low,high):#这部分递归，我不太理解，总感觉递归终止条件没有，即终止时没有返回值，我知道最后肯定是low==high，那会返回low和high共同指向的那个值么？感觉应该得返回这个值，但是程序中没给指明if low < high:#选择中间值mid = (low+high)//2#分成左右两部分，再对这两部分比较排序merge_sort(li,low,mid)merge_sort(li,mid+1,high)merge(li,low,mid,high)return liif __name__ == "__main__":li = [2,3,12,9,7,6,5,10,14]li = merge_sort(li,0,len(li)-1)print(li)

输出结果：

3.堆排序：由列表（顺序表）构造

过程：（1）构建大顶堆（由于要使最终的列表按照升序排列）

（2）取出堆顶元素，将堆末尾非叶子节点放在堆顶位置，然后向下调整堆

（3）按照步骤（2）依次进行，直至堆为空（实际上每次从堆顶下来的元素会存储在堆末尾与其对应的节点位置，不再开辟新的存储空间，为了节省内存，将排好序的元素放在原列表中）

#堆排序
#向下调整堆
def sift(li,low,high):#low为堆顶值的下标i = low#j是下标为i的值的左孩子j = 2*i+1#保存li[i]指向的值temp = li[i]#high为堆末尾值的下标while j <= high:#注意：在列表中如果索引对应的值为空，则用该索引调用时会出错，例：li=[],则li[0]会出错。if (j+1)<=high and li[j+1]>li[j]:#让j指向j+1j = j+1#如果li[j]指向的值比temp指向的值大，让li[i]指向大的值if li[j]>temp:li[i] = li[j]#i下移指向ji = jj = 2*i+1else:li[i] = tempbreak#while...else组合，当while中不执行break时会调用else的语句，当li[j]>temp导致的j>high时，执行else       else:li[i] = tempdef heap_sort(li):n = len(li)#构建大顶堆for i in range((n-2)//2,-1,-1):sift(li,i,n-1)#取出堆顶元素，将堆末尾非叶子节点放在堆顶位置，交换位置，然后向下调整堆for j in range((n-1),-1,-1):li[0],li[j] = li[j],li[0]#sift()函数中的high为j-1sift(li,0,j-1)if __name__ == "__main__":li = [2,3,12,9,7,6,5,10,14]heap_sort(li)print(li)

输出：

针对以上六种算法的小总结：  

                  

7.lowB三人组中插入排序的进化版即希尔排序（时间复杂度依gap设置不同分情况讨论）

#希尔排序
#gap为需排序两数的间隔
def insert_gap(li,gap):for i in range(gap,len(li)):temp = li[i]j = i-gapwhile j>=0 and temp<li[j]:li[j+gap] = li[j]j = j-gapli[j+gap] = tempdef shell_sort(li):d = len(li)//2#间隔d每次除以2while d>=1:insert_gap(li,d)d //= 2if __name__ == "__main__":li = [2,3,12,9,7,6,5,10,14,20,17,16,18,19]shell_sort(li)print(li)

输出：

十兄弟之高大上三人组：

平均时间复杂度为

1.计数排序：将要排序的值作为新列表的下标，缺点：取值范围应为要排序的值的最大值+1,需开辟较大存储空间

#计数排序\
#设置存储范围max_count
def count_sort(li,max_count=100):count = [0 for _ in range(max_count+1)]#把要排序的值作为count列表的下标for val in li:count[val] += 1li.clear()#data为index的出现次数for index,data in enumerate(count):for i in range(data):li.append(index)if __name__ == "__main__":li = [2,3,12,9,7,6,5,10,14,20,17,16,18,19]count_sort(li)print(li)

2.桶排序：平均时间复杂度为，其中k为列表的长度n与桶的个数求出的值，最坏时间复杂度为， 空间复杂度为。

#桶排序
def bucket_sort(li, n=4,max_length=20):#构建二维数组，在列表内建多个桶buckets = [[] for _ in range(n)]for val in li:i = min(val//(max_length//n),n-1)buckets[i].append(val)#每个桶内进行冒泡排序for j in range(len(buckets[i])-1,0,-1):if buckets[i][j]<buckets[i][j-1]:buckets[i][j-1],buckets[i][j] = buckets[i][j],buckets[i][j-1]else:breaksorted_li = []for buc in buckets:#extend函数可以在列表内添加多个值sorted_li.extend(buc)return sorted_liif __name__ == "__main__":li = [2,3,12,9,7,6,5,10,14,20,17,16,18,19]li = bucket_sort(li)print(li)

3.基数排序：注意：当要排序的数中最大值很大，而要排序的这些数的个数较少时，时间复杂度会变大。因为时间复杂度为（kn）,k为,其中k由最大值影响，而不受个数影响。

基数排序的时间复杂度为，空间复杂度为

而快速排序的时间复杂度为,n为排序总个数。

#基数排序
def radix_sort(li):max_num = max(li)k = 0#例如:1000->4（个十百千），100000->6位while 10**k <= max_num:#依次从个位开始排序，个位排好后再排十位。。。#每次设置10个桶buckets = [[] for _ in range(10)]for val in li:#例如：987，取个位：987//1%10;取十位：987//10%10;取百位：987//100%10i = val//(10**k)%10buckets[i].append(val)li.clear()for buc in buckets:li.extend(buc)k += 1if __name__ == "__main__":li = [2,3,12,9,7,6,5,10,14,20,17,16,18,19]radix_sort(li)print(li)

总结：以上十种排序算法中前7种针对实数（小数、正负整数）都可以进行排序，而后三种排序算法只能针对正整数，对于小数以及负数的排序，这三种算法得稍作改进，有时间的话我会再整理出来。

注：我正在复习这些排序算法准备职场笔试，通过看一些视频和其他资料在博客上进行了整理，非常欢迎大家给我提出问题，与我积极讨论，让我们共同进步！