기본 아이디어: 정렬되지 않은 시퀀스에서 가장 작은 요소를 찾아 첫 번째 위치에 넣은 다음, 정렬되지 않은 나머지 시퀀스에서 가장 작은 요소를 찾아 두 번째 위치에 넣는 식입니다. 모든 요소가 정렬될 때까지 계속됩니다. 총 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): ''' 获取最大值或者最小值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]
선택 정렬 알고리즘의 원리를 설명하는 더 많은 그림과 텍스트와 Python의 구현 예를 보려면 PHP 중국어 웹사이트에서 관련 기사를 주목하세요!