python常用排序算法的實(shí)現(xiàn)代碼

更新時(shí)間：2019年11月08日 16:52:43 作者：Mars.wang

這篇文章主要介紹了python常用排序算法的實(shí)現(xiàn)代碼,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下

排序是計(jì)算機(jī)語(yǔ)言需要實(shí)現(xiàn)的基本算法之一，有序的數(shù)據(jù)結(jié)構(gòu)會(huì)帶來效率上的極大提升。

1.插入排序

插入排序默認(rèn)當(dāng)前被插入的序列是有序的，新元素插入到應(yīng)該插入的位置，使得新序列仍然有序。

def insertion_sort(old_list):
  n=len(old_list)
  k=0
  for i in range(1,n):
    temp=old_list[i]
    j=i
    while j>0 and temp<old_list[j-1]:
      old_list[j]=old_list[j-1]
      j=j-1
    old_list[j]=temp
  return old_list

2.冒泡排序

冒泡排序的原理是對(duì)序列進(jìn)行遍歷，遍歷過程中如果發(fā)現(xiàn)相鄰兩個(gè)元素，左邊的元素大于右邊，則進(jìn)行交換，一次遍歷之后最大的元素被移動(dòng)到對(duì)尾，然后進(jìn)行第二次遍歷，直到隊(duì)列有序。

def bubble_sort(old_list):
  n=len(old_list)
  for i in range(n-1):
    for j in range(n-1-i):
      if old_list[j]>old_list[j+1]:
        old_list[j],old_list[j+1]=old_list[j+1],old_list[j]
  return old_list

3.快速排序

快速排序的實(shí)現(xiàn)方法是設(shè)置兩個(gè)游標(biāo)，一個(gè)從前往后，一個(gè)從后往前，如果左側(cè)游標(biāo)所指數(shù)據(jù)大于右側(cè)，兩數(shù)據(jù)進(jìn)行交換，直到兩個(gè)游標(biāo)指向同一數(shù)據(jù)，則第一趟遍歷結(jié)束。結(jié)束時(shí)游標(biāo)所在數(shù)據(jù)，左側(cè)都比其小，右側(cè)都比其大。

接下來對(duì)游標(biāo)前后的兩個(gè)序列進(jìn)行遞歸操作。

def quick_sort(list,low,high):
  i=low
  j=high  
  if i >= j:
    return list
  key=list[i]
  while i < j:
    while i < j and list[j]>=key:
      j = j - 1
    list[i]=list[j]
    while i < j and list[i]<=key:
      i = i + 1
    list[j]=list[i]
  list[i]=key
  quick_sort(list,low,i-1)
  quick_sort(list,j+1,high)
  return list

4.選擇排序

選擇排序的原理是是先找到起始數(shù)組中最小的元素，將它交換到i=0；然后尋找剩下元素中最小的元素，將它交換到i=1的位置…… 直到找到第二大的元素，將它交換到n-2的位置。這時(shí)，整個(gè)數(shù)組的排序完成。

def select_sort(list):
  length=len(list)
  for i in range(length):
    min_index=i
    for j in range(i,length):
      if list[j]<list[min_index]:
        min_index=j
    list[i],list[min_index]=list[min_index],list[i]
  return list

5.歸并排序

歸并排序是對(duì)數(shù)組進(jìn)行拆分再拆分，直到不能再拆分，然后分別對(duì)最小粒度的子數(shù)組進(jìn)行合并，然后再合并稍微大一點(diǎn)的數(shù)組，直到最終合成一個(gè)最大的數(shù)組。分兩個(gè)函數(shù)完成，一個(gè)負(fù)責(zé)拆分，一個(gè)負(fù)責(zé)排序合并。

def merge_sort(list):
  if len(list)<=1:
    return list
  mid=int(len(list)/2)
  left=merge_sort(list[:mid])
  right=merge_sort(list[mid:])
  return merge(left,right)
def merge(list1,list2):
  list=[]
  i,j=0,0
  while i<len(list1) and j<len(list2):
    if list1[i]<list2[j]:
      list.append(list1[i])
      i=i+1
    elif list1[i]>=list2[j]:
      list.append(list2[j])
      j=j+1
  list.extend(list1[i:])
  list.extend(list2[j:])
  return list

6.希爾排序

def shell_sort(nums):
  step = len(nums)/2
  while step > 0:
    for i in range(step, len(nums)):
      while i >= step and nums[i-step] > nums[i]:
        nums[i], nums[i-step] = nums[i-step], nums[i]
        i -= step
    step = step/2
  return nums

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: