插入排序

插入排序

插入排序使用线性搜索来查找排序的列表中第一个元素的位置,在分类列表的一部分。是一个基本排序算法用于排序较小的数据集或插入一个新元素到前面已排序好的列表中。

算法:

插入排序始于第2个元素，把后面的元素依次往前面插入。

1。假设如果数组排序到i位置，我们可以对数组进行排序,直到从第（i+1）个元素到数组最后一个元素正确插入到当前元素的前面。

2。当前元素i正确插入到0元素到i元素。

3。任何数组排序到第0位置(单个元素总是排序),这样就知道如何扩大,怎么对整个数组排序。

 

属性:

1。表现最好的情况下——当数组已经排序O(n)。总数的比较:N - 1和交流总数:N - 1。

2。坏的情况下性能——当数组排序以相反的顺序O(n2)。n - 1迭代比较和交流。

3。平均情况下性能- O(n2)

4。是敏感的输入的数量取决于输入的比较与交流。

5。它不需要任何额外的空间排序,因此O(1)额外的空间。

 

c语言程序

void InsertionSort(int *array , int number_of_elements)
{
        int iter,jter;
        for(iter=1;iter<number_of_elements;iter++)
        {
                int current_element = array[iter];
                jter = iter-1;
                while(jter>=0 && array[jter] > current_element)
                {
                        array[jter+1] = array[jter];
                        jter--;
                }
                array[jter+1] = current_element;
        }
}
int main()
{
        int number_of_elements;
        scanf("%d",&number_of_elements);
        int array[number_of_elements]; 
        int iter;
        for(iter = 0;iter < number_of_elements;iter++)
        {
                scanf("%d",&array[iter]);
        }
        /* Calling this functions sorts the array */
        InsertionSort(array,number_of_elements); 
        for(iter = 0;iter < number_of_elements;iter++)
        {
                printf("%d ",array[iter]);
        }
        printf("
");
        return 0;
}