Insertion Sort插入排序C语言实现

#Insertion Sort-插入排序

此贴由戴维营教育学员翻译,鄙人整理,特意为戴维营教育零基础学员课外学习之用.

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

##算法:

插入排序从第1个元素开始,可以认为这个元素已经排序,然后把后面的元素依次插入前面有序列表中。

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

  • 2,第i+1个元素的插入位置必须在遍历第个元素到第i个元素之间找到。

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

##特性:

  • 最佳性能的情况——当数组已经排序:O(n), 总的比较次数:N-1,总的交换次数:N-1

  • 最差性能的情况——当数组排序以相反的顺序: O(n2), n-1次比较和交换的遍历。

  • 平均性能情况: O(n2)

  • 排序过程中的比较次数和交换次数严重依赖于数据的输入.

  • 它排序过程中不需要任何额外的空间,因此空间复杂度是 O(1)

##插入排序-C语言代码

#include <stdio.h>
/* Logic :
Suppose if the array is sorted till index i then we can sort the arry till i+1 by inserting i+1 th element in the correct position from 0 to i+1.
The position at which (i+1)th element has to be inserted has to be found by iterating from 0 to i.
As any array is sorted till 0th postion(Single element is always sorted) and we know how to expand, we can sort the whole array.
 */
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(void)
{
        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("\n");
        return 0;
}

标签:none

添加新评论