python实现排序算法解析

本文实例为大家分享了python实现排序算法的具体代码，供大家参考，具体内容如下

一、冒泡排序

def bububle_sort(alist):
"""冒泡排序(稳定|n^2m)"""
n = len(alist)
for j in range(n-1):
 count = 0
 for i in range(0,n-1-j):
  if alist[i]>alist[i+1]:
   count +=1
   alist[i], alist[i+1] = alist[i+1], alist[i]
 if count==0:
  return

二、选择排序

def select_sort(alist):
 """选择排序(不稳定|n^2)"""
 n = len(alist)
 for j in range(n-1):
   min_index = j
   for i in range(j+1,n):
     if alist[min_index] > alist[i]:
       min_index = i
   alist[j], alist[min_index] = alist[min_index], alist[j]

三、插入排序

def insert_sort(alist):
 """插入排序(稳定|n^2)"""
 n = len(alist)
 for j in range(1,n):
   i = j
   while i>0:
     if alist[i] < alist[i-1]:
       alist[i], alist[i-1] = alist[i-1], alist[i]
       i -= 1
     else:
       break

四、希尔排序

def shell_sort(alist):
 """希尔排序(不稳定|n^2)"""
 n = len(alist)
 gap = n//2

while gap>=1:
   for j in range(gap,n):
     i=j
     while i>0:
       if alist[i]<alist[i-gap]:
         alist[i], alist[i-gap] = alist[i-gap], alist[i]
         i -= gap
       else:
         break
   gap //=2

五、快速排序

def quick_sort(alist, first, last):
 """快速排序(不稳定|n^2)"""
 if first >= last:
   return
 mid_value = alist[first]
 low = first
 high = last
 while low < high:
   #high左移
   while low <high and alist[high] >= mid_value:
     high -= 1
   alist[low] = alist[high]
   #low右移
   while low < high and alist[low] < mid_value:
     low += 1
   alist[high] =alist[low]
 #从循环退出时，low=high
 alist[low] = mid_value

#对low左边的列表执行快速排序
 quick_sort(alist, first, low-1)
 #对low右边的列表执行快速排序
 quick_sort(alist, low+1, last)

六、归并排序

def merge_sort(alist):
 """归并排序(稳定|nlgn)"""
 n = len(alist)
 if n <= 1:
   return alist
 mid = n//2

#left 采用归并排序后形成新的有序列表
 left_li = merge_sort(alist[:mid])
 #right 采用归并排序后形成新的有序列表
 right_li = merge_sort(alist[mid:])

#merge(left, right) 将两个有序的子序列合并为一个新的整体
 left_pointer, right_pointer = 0, 0
 result = []

while left_pointer < len(left_li) and right_pointer<len(right_li):
   if left_li[left_pointer] < right_li[right_pointer]:
     result.append(left_li[left_pointer])
     left_pointer += 1
   else:
     result.append(right_li[right_pointer])
     right_pointer += 1

result += left_li[left_pointer:]
 result += right_li[right_pointer:]
 return result

来源：https://blog.csdn.net/weixin_38748717/article/details/79427316