java 插入排序算法实现_C程序实现插入排序算法

java 插入排序算法实现

Insertion sort is a simple sorting algorithm that is online, stable, and in-place.

插入排序是一种简单的排序算法，可在线，稳定且就地进行 。

A stable sorting algorithm is the one where two keys having equal values appear in the same order in the sorted output array as it is present in the input unsorted array.
一种稳定的排序算法是一种具有相等值的键在排序后的输出数组中以与输入未排序数组中存在的键相同的顺序出现的算法。
An in-place sorting algorithm has various definitions but a more used one is –
就地排序算法具有多种定义，但使用更广泛的是–

"An in-place sorting algorithm does not need extra space and uses the constant memory for manipulation of the input in-place. Although, it may require some extra constant space allowed for variables."
“就地排序算法不需要额外的空间，而是使用常量内存来就地输入的操作。尽管如此，它可能需要一些额外的常量空间来允许变量使用。”

The basic principle followed in Insertion sort is that the key element is placed at its position in the sorted array in every iteration.

插入排序中遵循的基本原理是，每次迭代中，键元素均位于其在已排序数组中的位置。

Pseudo code:

伪代码：

    for i = 1 to n
          key = arr[i]
          j = i-1
          while  j >= 0 and key < arr[j]
                   arr[j + 1] = arr[j]
                   j = j – 1
          end while
      
          arr[ j + 1 ] = key
    end for

Example:

例：

    Array = 12, 14, 11, 5, 6
    Initially, 
    we run the loop from index = 1 (14) till index = 4 (last value)

    For i = 1, 
    compare 14 with 12 and we see, 12< 14, so no change.
    
    For i = 2, 
    compare 11 with 14, and we see, 11<14, 
    shift 14 to next place. 
    Now, compare 11 with 12, we see that 11<12, 
    shift 12 by one place. 
    Now, put 11 at index 0.
    Array: 11, 12, 14, 5, 6
    
    For i = 3, 
    compare 5 and keep shifting the values.
    Array: 5, 11, 12, 14, 6
    
    For i = 4, 
    compare with all the previous elements and 
    keep shifting the values accordingly.

Time Complexity: The time complexity of Insertion Sort can be described as: T(n) = T(n/2) + C

时间复杂度：插入排序的时间复杂度可以描述为： T(n)= T(n / 2)+ C

Worst case: O(n^2)
最坏的情况：O(n ^ 2)
Average Case: O(n^2)
平均情况：O(n ^ 2)
Best case: O(n), when the array is already sorted
最好的情况：O(n)，当数组已经排序时
Space Complexity: O(1)
空间复杂度：O(1)

C Implementation:

C实现：

#include <stdio.h>

void insertion(int arr[], int n)
{
    int i, j;
    for (i = 1; i < n; i++) {
        int key = arr[i];
        j = i - 1;
        while (key < arr[j] && j >= 0) {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = key;
    }
    printf("\nAfter performing Insertion sort:\n");
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);
}

int main()
{

    int arr[] = { 10, 14, 3, 8, 5, 12, 16, 13 };
    int n = sizeof(arr) / sizeof(arr[0]);

    insertion(arr, n);

    return 0;
}

Output

输出量

After performing Insertion sort:
3 5 8 10 12 13 14 16

Insertion Sort can be optimized using Binary Insertion sorting. We must use Insertion sort where the elements are mostly sorted and only some elements are misplaced. Also, it should be used where there is lesser number of data points due to its large time complexity.

插入排序可以用二进制插入排序进行优化。我们必须使用插入排序，其中元素大多是排序的，只有一些元素放错了位置。另外，由于时间复杂度高，应在数据点数量较少的地方使用。