How to write insertion sort algorithm in Python?

How to write insertion sort algorithm in Python?

Insertion sort is a simple and intuitive sorting algorithm. Its idea is to divide the array to be sorted into an ordered part and an unordered part. Each time, an element is selected from the unordered part and inserted into the ordered part. correct position of the part. The implementation of the insertion sort algorithm is usually implemented by comparing and exchanging elements multiple times, with a time complexity of O(n^2).

Let’s take a look at how to write the insertion sort algorithm in Python language, as well as specific code examples.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]              # 当前待插入元素
        j = i - 1                 # 有序部分的最后一个元素索引

        # 将比key大的元素都向后移动一位
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key           # 将key插入正确位置

    return arr

The above is the specific implementation code of the insertion sort algorithm. In the main function, we need to pass in an array arr to be sorted and return the sorted result.

In the main loop of the algorithm, we start from the second element and use it as the key of the element to be inserted. We then compare the key with the last element of the sorted part and move the element larger than the key one position backward until we find the correct position of the key. Finally, we insert the key into the correct location.

Next, we can test this insertion sort algorithm.

arr = [9, 5, 1, 6, 8, 2]
sorted_arr = insertion_sort(arr)
print(sorted_arr)

The output result is:

[1, 2, 5, 6, 8, 9]

As you can see, through the insertion sort algorithm, we successfully arranged the input array in ascending order.

To sum up, writing the insertion sort algorithm in Python is not complicated. We only need to understand the basic idea of ​​insertion sort, and then implement the corresponding code based on the idea. Of course, to make the code more robust and versatile, we can also handle edge cases, such as empty arrays or arrays with only one element.

I hope this article can help you understand and master the insertion sort algorithm!

The above is the detailed content of How to write insertion sort algorithm in Python?. For more information, please follow other related articles on the PHP Chinese website!