How to implement selection sorting of python sorting algorithm

1. Introduction

Primary sorting algorithm refers to several relatively basic and easy-to-understand sorting algorithms. There are three primary sorting algorithms: insertion sort, selection sort and bubble sort. Although their efficiency is lower than that of advanced sorting algorithms, after understanding the primary sorting algorithm, it will be much easier to learn the relatively complex advanced sorting algorithm.

2. Description

Selection sorting means selecting the smallest or largest data from an unordered array each time, and putting it from the unordered array to the end of the ordered array to achieve sorting Effect.

The average time complexity of selection sort is O(n2), and the time complexity in the best case and the time complexity in the worst case are both O(n2). Additionally, it is an unstable sorting algorithm. The selection sort process is easy to understand. Taking the ascending sorting algorithm as an example, we first traverse the unsorted array and find the smallest element, as shown in Figure 2-4. Then, remove the smallest element from the unsorted array and add it to the end of the sorted array.

Because the smallest element is 1, 1 is added to the end of the ordered array which is still empty.

As shown in Figure 2-5, we continue to traverse the remaining elements. This time, the smallest element is 2. We add it to the end of the sorted array. This operation is correct because the elements in the sorted array must be smaller than the elements in the unsorted array.

As shown in Figure 2-6, repeat the above steps. When there is only one element left in the unsorted array, add it to the end of the sorted array. The entire The sorting of the array is completed.

3. Code implementation

Select sorting code:

nums = [5,3,6,4,1,2,8,7]
res = []　　　#用于存储已排序元素的数组
while len(nums): #当未排序数组内还有元素时，重复执行选择最小数的代码
 minInd = 0 #初始化存储最小数下标的变量，默认为第一个数
 for i in range(1, len(nums)):
  if(nums[i] < nums[minInd]): #更新最小数的下标
    minInd = i
 temp = nums[minInd]
 nums.pop(minInd) #把最小数从未排序数组中删除
 res.append(temp) #把最小数插入到已排序数组的末尾
print(res)

Run the program, the output result is:

[1,2,3,4,5,6,7,8]

In the program, i in the first for loop represents the first position in the unsorted array, that is, the first position after the ordered array. Then, use a for loop to find the subscript of the minimum value in the unsorted array. Initially, the minimum index minInd is assigned the index of the first element of the unsorted array. When an element smaller than the current minimum is encountered, just update the index and iterate through the entire array. After exchanging the minimum value found with the first element in the unsorted array, the minimum value is placed at the end of the ordered array.

The above is the detailed content of How to implement selection sorting of python sorting algorithm. For more information, please follow other related articles on the PHP Chinese website!