Insertion Sort

Insert an element into a sequence that is already sorted to obtain a new sorted sequence.

1. Treat the first element of the unsorted sequence as a sorted sequence, and treat the remaining elements from the second to the last as the unsorted sequence.
2. Scan the unsorted sequence from beginning to end, inserting each scanned element into an appropriate position within the sorted sequence. (If the element to be inserted is equal to an element in the sorted sequence, insert the element to be inserted after the equal element.)

Code Implementation

::: code-tabs
@tab Java

public class InsertSort implements IArraySort {
    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // Create a copy of arr to avoid modifying the original parameter content
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        // Start selecting an appropriate position for insertion from the element at index 1, as the element at index 0 is inherently sorted
        for (int i = 1; i < arr.length; i++) {
            // Record the data to be inserted
            int tmp = arr[i];
            // Compare starting from the rightmost element of the already sorted sequence to find a smaller number
            int j = i;
            while (j > 0 && tmp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }
            // If there is a number smaller than the current one, insert it
            if (j != i) {
                arr[j] = tmp;
            }
        }
        return arr;
    }
}

@tab JavaScript

function insertionSort(arr) {
    var len = arr.length;
    var preIndex, current;
    for (var i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while(preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex+1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex+1] = current;
    }
    return arr;
}

@tab Python

def insertionSort(arr):
    for i in range(len(arr)):
        preIndex = i-1
        current = arr[i]
        while preIndex >= 0 and arr[preIndex] > current:
            arr[preIndex+1] = arr[preIndex]
            preIndex-=1
        arr[preIndex+1] = current
    return arr

@tab Go

func insertionSort(arr []int) []int {
    for i := range arr {
        preIndex := i - 1
        current := arr[i]
        for preIndex >= 0 && arr[preIndex] > current {
            arr[preIndex+1] = arr[preIndex]
            preIndex -= 1
        }
        arr[preIndex+1] = current
    }
    return arr
}

@tab PHP

function insertionSort($arr){
    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        $preIndex = $i - 1;
        $current = $arr[$i];
        while($preIndex >= 0 && $arr[$preIndex] > $current) {
            $arr[$preIndex+1] = $arr[$preIndex];
            $preIndex--;
        }
        $arr[$preIndex+1] = $current;
    }
    return $arr;
}

:::