Straight select sort

1. Selection sorting overview

Selection sort is a simple and intuitive sorting algorithm. Its working principle is to select the smallest (or largest) element from the data elements to be sorted each time and store it at the beginning of the sequence until all the data elements to be sorted are finished.

2. Basic ideas

The direct selection and sorting of n records can get the ordered results through n-1 direct selection and sorting
Algorithm analysis:

• Number of keyword comparisons
  Select the record with the smallest key i n the i-th sorting, and make n-i comparison, so the total number of comparisons is n(n-1)/2=o(n^2)
• Record the number of moves
  When the initial file is in positive order, the number of moves is 0
  When the initial status of the file is reverse order, the exchange operation shall be performed for each order, and the maximum number of moves is 3 (n-1)
  The average time complexity is O(n^2)
• Stability: unstable

3.python implementation

# Select sorting algorithm model:
# 3,1,2,5,6
# 31256 > 31256 > 31256 > 31256 > 1 3256 find out first round
# 13256 > 13256 > 13256 > 12 356 round 2
# 12356 > 12356 > 123 56 round 3
# 12356 > 1235 6 round 4
# 12356 round 5
# ① from left to right, find the minimum value
list1 = [3, 1, 5, 2, 7, 991, 189, 19, 16, 2, 1, 5]
def select(list1):
    for i in range(len(list1)):  #  len(list1) cycles from left to right
        # num_min = list1[i]   
        location = i   #  Minimum at default i
        for j in range(i, len(list1)-1):  
            if list1[location] > list1[j+1]:  #  If the number at the default minimum position is greater than the number at j+1, then j+1 is the minimum
                location = j + 1
            else:  #  If the minimum < LIST1 [J + 1], continue
                continue   
        mid = list1[location]   # Loop i, find the decimal point, and exchange with the number at i
        list1[location] = list1[i]
        list1[i] = mid
    return list1
print(select(list1))

Here is the variation above, from right to left, find the maximum value each time, and put it at the "starting position" at the beginning of each cycle

# 3,1,2,5,6
# 31256 > 31256 > 31256 > 31256 > 31256 > 3125 6 round 1
# 31256 > 31256 > 31256 second round
# 31256 > 31256 > 12 3456 round 3
# 12356 > 1 2356 round 4
# 12356 round 5
# ② from right to left, find the maximum value
list2 = [25,2,5,3,1]
def select1(list2):
    for i in range(len(list2)-1,-1,-1):
        location = i
        for j in range(i-1,-1,-1):
            if list2[location] < list2[j]:
                location = j
            else:
                continue
        mid = list2[location]
        list2[location] = list2[i]
        list2[i] = mid
    return list2
print(select1(list2))

The above code passed the test in Python 3.7.3 environment