Learn and implement the selection sort algorithm in Python

Understand the principle and implementation of selection sorting in Python

Selection Sort is a simple and intuitive sorting algorithm. Its basic idea is to traverse the array each time , select the smallest (or largest) element in the unsorted part, swap its position with the first element of the unsorted part, and then continue to select the smallest (or largest) element from the unsorted part, and so on, until the entire Arrays are ordered. The time complexity of selection sort is O(n^2), and it is an unstable sorting algorithm.

The following uses specific code examples to illustrate the implementation process of selection sorting.

def selection_sort(arr):
    n = len(arr)
    for i in range(n-1):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

The above is the implementation code of the selection sort algorithm. Next we will explain the principle and process of this code step by step.

First, we define a selection_sort function, which receives an array arr to be sorted as a parameter.

In the function body, we first get the length n of the array. This is to iterate n-1 times, because each iteration will put a smallest element in the correct position, so the last element is not needed Sort again.

Then, we use two nested for loops to perform the selection sorting process. The outer loop goes from 0 to n-1, representing the starting position i of the part to be sorted.

The inner loop is from i 1 to n, representing element j in the part to be sorted. We compare j with the element at starting position i. If j is smaller than the element at starting position i, min_idx is updated to j, indicating that j is the index of the smallest element found so far.

When the inner loop ends, we will exchange the position of the smallest element found with the element at starting position i, so that the current iteration will put a smallest element in the correct position.

Through n-1 iterations, we can ensure that the entire array is arranged in ascending order.

Next, we can use the following code to test the effect of selection sorting:

arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("排序后的数组：")
for i in range(len(arr)):
    print(arr[i], end=" ")

The output result is: 11 12 22 25 64, which means that the array has been sorted in ascending order.

In actual use, selection sort is less efficient, so we prefer to use other more efficient sorting algorithms, such as quick sort or merge sort. However, selection sorting is a simple and easy-to-understand sorting algorithm, which is helpful for beginners to understand the basic principles and ideas of sorting algorithms.

To sum up, selection sorting is to select the smallest (or largest) element from the unsorted part each time, put it at the end of the sorted part, and through multiple iterations, finally achieve the purpose of ordering the entire array. Mastering the principle and implementation of selection sort is of great significance for in-depth understanding of sorting algorithms and improvement of programming abilities.

The above is the detailed content of Learn and implement the selection sort algorithm in Python. For more information, please follow other related articles on the PHP Chinese website!