首页 > 代码库 > 算法导论之——插入排序

算法导论之——插入排序

#include<stdio.h>
/*我们希望排序的数也称为关键字*/
void sort_on(void);
void sort_down(void);
int A[6] = { 5,2,4,6,1,3 };
int main(void)
{
    //sort_down();
    sort_on();
    for (int num = 0; num<6; num++)
        printf("%d ", A[num]);
    return 0;
}
//升序
void sort_on(void)
{
    int key ;
    int i ;
    for (int j = 1; j<6; j++)
    {
         key = A[j];//得到我们需要排序的数,即关键字,这句有保存作用
         i = j - 1;//记录当前要排序的数的前一个位置
        while (i >= 0 && A[i]>key)//如果当前数大于要排序的数,则把大的数后移一个位置
        {
            A[i + 1] = A[i]; 
            i--;
        }
        A[i + 1] = key;//把保存的key移到指定位置
    }
}
//降序
void sort_down(void)
{
    int key ;
    int i ;
    for (int j = 1; j<6; j++)
    {
         key = A[j];
         i = j - 1;
        while (i >= 0 && A[i]<key)
        {
            A[i + 1] = A[i];
            i--;
        }
        A[i + 1] = key;
    }
}

算法思路(已升序为例):

key=A[j];保存需要的比较值,while循环中,A[i]>key,当前key值的前一个值如果大于key值,就把A[i]的值后移一位,此时后移的位覆盖了key,然后i--,又循环重复,一直到循环结束,循环结束时,从小到大排列,但是此时由于之前i--的原因,跳出循环之后,要把第一步保存的key值给A[i+1];必须要是i+1。这样,保证了要排序的值在本次排序之后是从左到右依次变大的。

文字的分析还是不够直接,需要自己推导过程去理解。

在这之后,我们应该要知道这个数学交换比较过程怎么用算法去实现。

 在设计模式上存在缺陷,其实应该写成移植性更高的代码,试想要是我现在要排序100个元素的数组时,这个代码需要更改很多地方,但这次作为练手,就先这样了。以后注意改进。O(∩_∩)O

算法导论之——插入排序