排序算法-插入算法

描述

大多数纸牌游戏都采用插入排序来排列他们手中的纸牌。他们保持已发到手中的牌有序，当拿到一张新牌时，将其插入到合适的位置。为了将数组x[n]按升序排列，我们首先将第一个元素视为有序子数组x[0..0],然后插入x[1],…,x[n-1],下面4行展示了该止算法在一个四元数组上的执行过程，“|”代表变量i,它左边是有序的，而它右边的元素则还是初始顺序。

筛选过程通过一个从右到左的循环实现，该循环使用变量j跟踪被筛选的元素。只要该元素具有前驱(即j>0)且没有到达最终位置(即该元素小于它的前驱),就交换该元素和它的前驱。完整的程序如下所示

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


#include<stdio.h>

void isort(int a[], int num)
{
    int i,j;
    int t;
    for(i=1;i<num;i++)
    {
        t=a[i];
        for(j=i;j>0&&a[j-1]>t;j--)
            a[j]=a[j-1];
        a[j]=t;
    }
}
int main()
{
    int a[10]={1,4,3,9,8,2,10,23,24,7};
    int i;
    isort(a,10);
    for(i=0;i<10;i++)
        printf("%d ",a[i]);
    printf("\n");
}

说明: 本文非原创，是编程珠玑的看书笔记

Contents

描述