Implementation and optimization guide for Python selection sort

Steps and optimization methods of Python selection sort

Selection Sort is a simple and intuitive sorting algorithm. Its basic idea is to select the smallest (or largest) element from the data elements to be sorted each time, store it at the beginning of the sequence, and then continue to find the smallest (or largest) element from the remaining unsorted elements. , placed at the end of the sorted sequence. Repeat this process until all data elements to be sorted are arranged.

The steps of selection sorting can be summarized as follows:

1. Traverse the sequence to be sorted and mark the current position as the position of the smallest element.
2. Find an element smaller than the current smallest element from the element behind the mark's position, and update the mark's position.
3. Exchange the element at the mark position with the element at the minimum element position.
4. Take the element after the marked position as the new starting position and repeat steps 2 and 3.

The optimization methods of selection sorting are:

1. In each traversal, find the minimum element and the maximum element at the same time, and exchange them at the same time. This can reduce the number of exchanges and improve sorting efficiency.
2. Add a judgment. If no exchange occurs during the traversal process, that is, the sorting has been completed, the sorting process will be terminated early.

The following is an example of selection sort code in Python:

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_pos = i
        max_pos = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_pos]:
                min_pos = j
            if arr[j] > arr[max_pos]:
                max_pos = j
        if min_pos != i:
            arr[i], arr[min_pos] = arr[min_pos], arr[i]
        if max_pos == i:
            max_pos = min_pos
        if max_pos != n - 1 - i:
            arr[n - 1 - i], arr[max_pos] = arr[max_pos], arr[n - 1 - i]
        if min_pos == n - 1 - i:
            min_pos = max_pos
        if min_pos != i:
            arr[i], arr[min_pos] = arr[min_pos], arr[i]
    return arr

# 测试
arr = [64, 25, 12, 22, 11]
print("排序前:", arr)
sorted_arr = selection_sort(arr)
print("排序后:", sorted_arr)

In the above code, we use the variable min_pos to record the position of the smallest element, and use the variable max_pos Record the position of the largest element. On each pass, the two locations are updated by comparison and then swapped. When the list length is an odd number, if the positions of min_pos and max_pos happen to coincide with the starting position, we need to check and process the swapped positions.

The above are the steps and optimization methods of Python selection sorting, as well as specific code examples. Although selection sorting is simple, it is less efficient and has a time complexity of O(n^2). Therefore, in practical applications, if the sorting scale is large, it is recommended to use more efficient sorting algorithms, such as quick sort or merge sort.

The above is the detailed content of Implementation and optimization guide for Python selection sort. For more information, please follow other related articles on the PHP Chinese website!