선택 정렬 알고리즘의 원리에 대한 그래픽 설명과 Python의 구현 예

기본 아이디어: 정렬되지 않은 시퀀스에서 가장 작은 요소를 찾아 첫 번째 위치에 넣은 다음, 정렬되지 않은 나머지 시퀀스에서 가장 작은 요소를 찾아 두 번째 위치에 넣는 식입니다. 모든 요소가 정렬될 때까지 계속됩니다. 총 n+1개의 시퀀스 요소가 있다고 가정하면 시퀀스를 정렬하려면 n 라운드를 찾아야 합니다. 각 라운드에서 다음 작업을 수행할 수 있습니다. 정렬되지 않은 시퀀스의 첫 번째 요소를 시퀀스의 후속 요소와 비교합니다. 후속 요소가 더 작으면 다음 요소와 첫 번째 요소가 한 라운드 후에 교체됩니다. 첫 번째 것이 가장 작아야 합니다. 이런 식으로 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의 구현 예를 보려면 PHP 중국어 웹사이트에서 관련 기사를 주목하세요!