插入排序算法学习——算法导论学习笔记

今天第一次写算法的笔记，从今天开始正式步入学习算法的行列。白天的时间保质保量的把工作完成，然后就是开始学习unix环境高级编程，还有就是算法了。学习要思考，要总结，才能有收获。回归正题。

插入排序 来一个例子排序的过程如下：给定无需序列：（3，6，9，7，1，8，2，4）

① 3，6，9，7，1，8，2，4 （将6插入到有序序列3中）

② 3，6，9，7，1，8，2，4 （将9插入到有序序列3，6中）

③ 3，6，9，7，1，8，2，4 （将7插入到有序序列3，6，9中）

④ 3，6，7，9，1，8，2，4 （将1插入到有序序列3，6，7，9中）

⑤ 1，3，6，7，9，8，2，4 （将8插入到有序序列1，3，6，7，9中）

⑥ 1，3，6，7，8，9，2，4 （将2插入到有序序列1，3，6，7，8，9中）

⑦ 1，2，3，6，7，8，9，4 （将4插入到有序序列1，2，3，6，7，8，9中）

⑧ 1，2，3，4，6，7，8，9 (排序成功)

在上代码，因为我一直在学习C++,所以目前都在用c++写代码了。

// algorithm.cpp : 定义控制台应用程序的入口点。
//author :wallwind
//time:2011.8.1
//插入排序算法：插入排序算法的算法复杂度是 虽然在最坏情况下复杂性为<em>θ</em>(n<sup>2</sup>)，但是他是原地置换的程序所以，会减少资源的分配。对一些数据量小的算法比较合适。其思想就是将一个数字插入到一个已
//排好序的数组中。分为外围循环和内部循环。
#include "stdafx.h"
#include<iostream>
#include <string>
using namespace std;
void insert_sort(int a[],int size)
{
    for (int j=1;j<size;j++)
    {    
        int key=a[j];
        int i=j-1;
    
        while (i>-1&&a[i]>key)
        {
            a[i+1]=a[i];
            i=i-1;    
        }
    a[i+1]=key;
    }
}
int _tmain(int argc, _TCHAR* argv[])
{
    int aa[8]={7,9,2,6,4,3,8,1};
    
    insert_sort(aa,8);
    for (int i=0;i<8;i++)
    {
        cout<<aa[i]<<" ";
    }
    
    return 0;
}

还有就是设置哨兵的算法，带以后写出代码和原理。