Graphical explanation of the principle of selection sorting algorithm and implementation examples in Python-Python Tutorial-php.cn

Graphical explanation of the principle of selection sorting algorithm and implementation examples in Python

高洛峰

Release： 2017-03-06 13:31:37

Original

1258 people have browsed it

Basic idea: Find the smallest element from the unsorted sequence, put it in the first position, then find the smallest element from the remaining unsorted sequence, put it in the second position, and so on And so on until all elements have been sorted. Assuming that there are n+1 sequence elements in total, we need to find n rounds to sort the sequence. In each round, we can do this: compare the first element of the unsorted sequence with the subsequent elements in sequence. If the subsequent elements are smaller, the subsequent elements and the first element will be swapped. In this way, after one round, The first one must be the smallest. In this way, n rounds can be sorted.

Schematic diagram
Figure 1:

Graphical explanation of the principle of selection sorting algorithm and implementation examples in Python

##Figure 2:

Graphical explanation of the principle of selection sorting algorithm and implementation examples in Python

The initial data is not sensitive. No matter whether the initial data is sorted or not, it needs to go through N2/2 comparisons. This is not suitable for some data that are originally sorted or approximately sorted. There is no advantage in terms of sequence. In the best case, that is, everything is sorted, 0 exchanges are needed, and in the worst case, in reverse order, N-1 exchanges are required.

The number of data exchanges is less, if an element is in the correct final position, it will not be moved. In the worst case, only N-1 data exchanges are required. Among all sorting methods that rely entirely on exchanges to move elements, selection sorting is a better one.

Python code implementation:

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

Copy after login

Test it:

>>> 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]

Copy after login

For more pictures and texts explaining the principles of the selection sort algorithm and implementation examples in Python, please pay attention to the PHP Chinese website for related articles!