Python快速排序，插入排序演算法，自訂排序實例詳解

這篇文章主要介紹了Python實現快速排序和插入排序演算法及自訂排序的範例,自訂排序用到了Python的sort和sorted函數,需要的朋友可以參考下

一、快速排序

    快速排序（Quicksort）是對冒泡排序的一種改進。由C. A. R. Hoare在1962年提出。它的基本想法是：透過一趟排序將要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然後再按此方法對這兩部分資料分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個資料變成有序序列。

    快速排序，遞迴實作

def quick_sort(num_list):
  """
  快速排序
  """
  if num_list == []:
    return num_list
  smallList = []
  bigList = []
  middleElement = num_list[0]
  for i in num_list[1:]:
    if i <= middleElement:
      smallList.append(i)
    else:
      bigList.append(i)
  return quick_sort(smallList)+[middleElement]+quick_sort(bigList)

二、插入排序

    插入排序（Insertion Sort）的演算法說明是一種簡單直覺的排序演算法.它的工作原理是透過建立有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。插入排序在實作上，通常採用in-place排序（即只需用到O(1)的額外空間的排序），因而在從後向前掃描過程中，需要反覆把已排序元素逐步向後挪位，為最新元素提供插入空間。

    插入排序

def insert_sort(num_list):
  """
  插入排序
  """
  for i in range(len(num_list)-1):
    for j in range(i+1, len(num_list)):
      if num_list[i]>num_list[j]:
        num_list[i],num_list[j] = num_list[j],num_list[i]
  return num_list

三、自訂排序
利用 sort() 或 sorted() 的 key 即可實現。

    範例如下：

def sort_key(obj):
  sorted_list = [4, 2, 5, 9, 7, 8, 1, 3, 6, 0]
  return sorted_list.index(obj)
 
 
if name == 'main':
  print sorted(range(10), key=sort_key)
 
# 输出结果如下
[4, 2, 5, 9, 7, 8, 1, 3, 6, 0]

# 利用關鍵字在清單中的索引位置，進行自訂排序

#

以上是Python快速排序，插入排序演算法，自訂排序實例詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！