排序的故事---插入排序
说起插入排序，其实它的工作原理十分简单，举例来说一下，按照从小到大顺序排列下面的一组数：9 5 7 3 4
从第二个数起，把它之后的部分看成是未排列的部分，第一个元素是已排序的部分，然后依次把未排序的部分的第一个元素取出，插入到已排好的部分的正确位置，于是已排好部分的元素个数加一，未排好部分元素个数减一。一直到未排好部分元素的个数为零时结束。于是上述的例子的排序过程如下：
9 5 7 3 4
5 9 7 3 4
5 7 9 3 4
3 5 7 9 4
3 4 5 7 9
在一些传统的教科书里面中一般这样来作插入工作：如果要把X从X插入到X这一个已经排好的段落之中，令X与X,X,...,X,X相比较，如果X>=X(0<=j<=i-1)，就把X向后移一位，直到X小于X，X就放在X处。C语言的代码如下：
<div class="dp-highlighter"><div class="bar">
[*]void sort(int input[], int n)
[*]{
[*] int current;
[*] int x;
[*] int i;
[*] for(current=1; current
[*] {
[*] x = input;
[*] i = current - 1;
[*] while(x=0)
[*] {
[*] input = input;
[*] i--;
[*] }
[*] input = x;
[*] }
[*]}
页:
[1]