python实现排序算法解析

Python  /  管理员 发布于 7年前   142

本文实例为大家分享了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

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。