首先来看比较简单的选择排序(Selection sort)，插入排序(Insertion sort)，然后在分析插入排序的特征和缺点的基础上，介绍在插入排序基础上改进的希尔排序(Shell sort)。

一 选择排序

原理：现在假设我们给一个队伍排序。首先我们找到那个最矮的叫他站第一位，再找出第二矮的叫他站第二位，以此类推。既然是根据身高排序，那么我们是不是还应该有一个参照物，现在我们就假设最左边的同学的升高作为参照，一旦找到了就叫最矮的同学和最左边的这位同学交换位置，排完第一个后，我们又应该排第二个了，现在我们又以左数第二个同学作为参照，一次类推。选择排序就是这种排序方法。

[20:59:31] cat selectsort.c #include
     
      int main(){    int i,j,t,a[]={
    5,2,1,4,3,6,9,7,8,0};    int length=sizeof(a)/sizeof(a[0]);    for(i=0;i
      
       a[j])//if find number lesser than a[i] ,swap them,because we just need the more lesser number go to right location            {                t=a[i];                a[i]=a[j];                a[j]=t;            }        }    }    for(i=0;i
      
     

二 插入排序

原理：

我们可以假想选择排序为打牌，我们打牌时每得到一张牌，正常情况下我们都会先给牌排序的对吗。现在我们手里有四张牌，从左到右分别为1349，那么现在刚好有拿了一张5，我们是不是应该把5放在3和4直接。选择排序也是如此，每得到一个数，就把它插到正确的位置上，有一点需要注意，就是我们找到那个位置后，还需要把前面比它大的数往后挪一个位置，空出一个位置用来存放刚得到的数

选择排序很简单，他的步骤如下：

[20:19:47] vi selectsort.c [20:24:39] cat selectsort.c #include
     
      int main(){    int i,j,min,a[]={
      5,2,1,4,3,6,9,7,8,0};    int len=sizeof(a)/sizeof(a[0]);    for(i=0;i
      
       min)//next number is lesser than a[i],if we use for circle to compare ,it need more step to calculate,waste time        {            j=i;//we need to change number ,but we can change the values of i,so we need j            while(min
      
     

三 希尔排序(Shell Sort)

原理：这个排序方法是根据步长来进行排序的，每次比较的步长越小，序列就越有序。这个我讲不清楚，我经常搞错的地方就是步长的比较次数那里，正确的方法是比较数组的长度减去步长大小的次数，比较完一次之后，还要从头开始再比较，知道数组里的数据全部都是安装步长数排好的

[23:12:03] vi shellsort.c [23:20:06] gcc shellsort.c [23:20:09] ./a.out0 1 2 3 4 5 6 7 8 9 [23:20:11] cat shellsort.c #include
     
      int main(){    int i,j,c,x,k,h=1,a[]={
    5,2,1,4,3,6,9,7,8,0};    int length=sizeof(a)/sizeof(a[0]);    while(h
      
       =1)//circle step    {    for(i=0;i
       
        a[j+h])//compare two numbers,if true then swap            {                x=a[j];                a[j]=a[j+h];                a[j+h]=x;            }        }    }        h=h/2;    }    for(i=0;i