選択ソートアルゴリズムの原理とPythonでの実装例を図解で解説

基本的な考え方: ソートされていないシーケンスから最小の要素を見つけて最初の場所に置き、次に残りのソートされていないシーケンスから最小の要素を見つけて2番目の場所に置き、というように、すべての要素がソートされるまで続きます。合計で n+1 個のシーケンス要素があると仮定すると、シーケンスをソートするには n ラウンドを見つける必要があります。各ラウンドで、次のことを行うことができます。ソートされていないシーケンスの最初の要素とシーケンス内の後続の要素を比較し、後続の要素が小さい場合は、1 ラウンド後に後続の要素と最初の要素が交換されます。最初のものは最小でなければなりません。このようにして、n ラウンドをソートできます。

概略図
図 1:

図 2:

初期データは、ソートされているかどうかに関係なく、N2 を通過する必要があります。 /2 の比較。これは、元々ソートされている、またはほぼソートされている一部のシーケンスには利点がありません。最良の場合、つまりすべてがソートされている場合、0 回の交換が必要ですが、最悪の場合、逆の順序で N-1 回の交換が必要です。

データ交換の頻度は低くなり、要素が正しい最終位置にある場合は移動されません。最悪の場合、要素の移動に完全に依存するすべての並べ替え方法の中で、N-1 個のデータ交換だけが必要になります。選択並べ替えはより優れた方法です。

Pythonコードの実装:

def sort_choice(numbers, max_to_min=True):
 """
 我这没有按照标准的选择排序，假设列表长度为n，思路如下：
  1、获取最大值x，将x移动到列最后。[n1, n2, n3, ... nn]
  2、将x追加到排序结果[n1, n3, ... nn, n2]
  3、获取排序后n-1个元素[n1, n3, ... nn]，重复第一步，重复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):
 &#39;&#39;&#39;
 获取最大值或者最小值x，并且将x抽取出来，置于列表最后.
 Ex: get_max=True, [1, 4, 3] ⇒ [1, 3, 4] 
  get_max=False, [1, 4, 3] ⇒ [4, 3 ,1] 
 &#39;&#39;&#39;
 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]

選択ソートアルゴリズムの原理とPythonでの実装例を説明する画像とテキストの詳細については、注目してください。関連記事へ。