快捷導(dǎo)航

圖文講解選擇排序算法的原理及在Python中的實現(xiàn)

更新時間：2016年05月04日 10:34:31 作者：張志鵬yi

這篇文章主要介紹了選擇排序的原理及在Python中的實現(xiàn),選擇排序的時間復(fù)雜度為О(n²),需要的朋友可以參考下

基本思想：從未排序的序列中找到一個最小的元素，放到第一位，再從剩余未排序的序列中找到最小的元素，放到第二位，依此類推，直到所有元素都已排序完畢。假設(shè)序列元素總共n+1個，則我們需要找n輪，就可以使該序列排好序。在每輪中，我們可以這樣做：用未排序序列的第一個元素和后續(xù)的元素依次相比較，如果后續(xù)元素小，則后續(xù)元素和第一個元素交換位置放到，這樣一輪后，排在第一位的一定是最小的。這樣進行n輪，就可排序。

原理圖
圖1：

201654103109156.gif (288×288)

圖2：

201654103139716.gif (723×224)

初始數(shù)據(jù)不敏感，不管初始的數(shù)據(jù)有沒有排好序，都需要經(jīng)歷N2/2次比較，這對于一些原本排好序，或者近似排好序的序列來說并不具有優(yōu)勢。在最好的情況下，即所有的排好序，需要0次交換，最差的情況，倒序，需要N-1次交換。

數(shù)據(jù)交換的次數(shù)較少，如果某個元素位于正確的最終位置上，則它不會被移動。在最差情況下也只需要進行N-1次數(shù)據(jù)交換，在所有的完全依靠交換去移動元素的排序方法中，選擇排序?qū)儆诒容^好的一種。

python代碼實現(xiàn)：

def sort_choice(numbers, max_to_min=True):
 """
 我這沒有按照標準的選擇排序，假設(shè)列表長度為n，思路如下：
  1、獲取最大值x，將x移動到列最后。[n1, n2, n3, ... nn]
  2、將x追加到排序結(jié)果[n1, n3, ... nn, n2]
  3、獲取排序后n-1個元素[n1, n3, ... nn]，重復(fù)第一步，重復(fù)n-1次。

 max_to_min是指從大到小排序，默認為true；否則從小到大排序。
 對[8, 4, 1, 0, 9]排序，大致流程如下：
 sorted_numbers = []
 [8, 4, 1, 0, 9], sorted_numbers = [9]
 [4, 1, 0, 8], sorted_numbers = [9, 8]
 [1, 0, 4], sorted_numbers = [9, 8, 4]
 [0, 1], sorted_numbers = [9, 8, 4, 1]
 [0], sorted_numbers = [9, 8, 4, 1, 0]
 """
 if len(numbers) <= 1:
  return numbers
 sorted_list = []
 index = 0
 for i in xrange(len(numbers) - index):
  left_numbers = _get_left_numbers(numbers, max_to_min)
  numbers = left_numbers[:-1]
  sorted_list.append(left_numbers[-1])
  index += 1
 return sorted_list

def _get_left_numbers(numbers, get_max=True):
 '''
 獲取最大值或者最小值x，并且將x抽取出來，置于列表最后.
 Ex: get_max=True, [1, 4, 3] ⇒ [1, 3, 4] 
  get_max=False, [1, 4, 3] ⇒ [4, 3 ,1] 
 '''
 max_index = 0
 for i, num in enumerate(numbers):
  if get_max:
   if num > numbers[max_index]:
    max_index = i
  else:
   if num < numbers[max_index]:
    max_index = i
 numbers = numbers[:max_index] + numbers[max_index + 1:] + [numbers[max_index]]
 return numbers

測試一下：

>>> get_left_numbers([0, 4, 0, 31, 9, 19, 89,67], get_max=True)
[0, 4, 0, 31, 9, 19, 67, 89]
>>> get_left_numbers([0, 4, 0, 31, 9, 19, 89,67], get_max=False)
[4, 0, 31, 9, 19, 89, 67, 0]

>>> sort_choice([0, 4, 0, 31, 9, 19, 89,67], max_to_min=False)
[0, 0, 4, 9, 19, 31, 67, 89]
>>> sort_choice([0, 4, 0, 31, 9, 19, 89,67], max_to_min=True)
[89, 67, 31, 19, 9, 4, 0, 0]

您可能感興趣的文章: