第二节 插入排序

我的代码执行环境：

操作系统：OS X Yosemite

python版本2.7.6

微信公众平台：今天做了没

插入排序，百度百科解释：

http://baike.baidu.com/view/396887.htm

我自己的理解：就像大家总是举的例子一样，我们打扑克，在拿到牌后都要按大小顺序排好，拿到一张新牌，就放到已经有了的牌的合适位置（就是按大小排序），那么，当你在往已有的牌里插入的时候，后面的牌相对来说，都是向后移了一个位置。保持这么做，当放好最后一张牌时，你已经有一个副排好顺序的牌了。

那么来看C语言的实现：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void insert_sort(int *numbers, int len)
{
    int i, j, k;

    for (i = 1; i < len; i ++) {
        /* k就相当于新拿到的牌 */
        k = numbers[i];
        /* 用k和所有已经排好序的牌比较，插入的合适的位置，
         * 在这个过程中所有比k大的都要向后移一个位置 */
        for (j = i - 1; j >= 0; j --) {
            if (numbers[j] > k) {
                numbers[j+1] = numbers[j];
                numbers[j] = k;
            }
        }
    }
}

int main(int  argc, char *argv[])
{
    int numbers[10];
    int i;

    srand(time(NULL));

    for (i = 0; i < 10; i ++) {
        numbers[i] = rand() % 100 + 1;
    }

    for (i = 0; i < 10; i ++) {
        printf("numbers[%d] = %d\n", i, numbers[i]);
    }

    insert_sort(numbers, 10);

    for (i = 0; i < 10; i ++) {
        printf("numbers[%d] = %d\n", i, numbers[i]);
    }

    return 0;
}

还是C语言实现起来代码就是比较多，如果用高级语言就几行代码就可以了，下面是Python的实现：

#coding:utf-8
#如果要用中文注释需要上面那行，要不然报错(python2.7.6)
import random

def insert_sort(numbers):
    total = len(numbers)

    for i in range(1, total):
        #这就是新拿到的牌
        k = numbers[i]
        #下面range(0,i)[::-1]是逆序使用列表，因为原本序列
        #就是不包含i，所以不用range(0,i-1)
        for j in range(0, i)[::-1]:
            if numbers[j] > k:
                numbers[j+1] = numbers[j]
                numbers[j] = k

    return numbers

numbers = range(1, 20)
random.shuffle(numbers)
print numbers
print insert_sort(numbers)

第二节 插入排序

原文：http://my.oschina.net/bxxfighting/blog/515801