直接插入排序算法c语言实现。 己它的时间复杂度分析。

问题，用直接插入排序算法实现对顺序表的排序算法。 解决如下。

1纪录类型结构 和 顺序表结构

typedef struct RecordType
{
 int key;
 char data[20];
}RecordType;

#define MAXSIZE 20

typedef struct SqList
{
 RecordType r[MAXSIZE + 1];
 int length;
}SqList;

2。建立算法类

class CAlogrithm
{
public:
 void cout(void); //显示输出
 void setMemKey(int i, int k); 设置 排序关键字字段的值
 void setLength(int l); 设置排序的长度
 void InsertSort(); //排序算法实现
private:
 SqList t;
};

//实现函数

void CAlogrithm::InsertSort()
{
 SqList & L = t;
 int i=0, j=0;
 for(i=2; i<=L.length; i++)
 {
  if(L.r[i].key < L.r[i - 1].key)
  {
   L.r[0] = L.r[i];
   j = i - 1;
   while(L.r[0].key < L.r[j].key)
   {
    L.r[j+1] = L.r[j];
    j--;
   }
   L.r[j+1] = L.r[0];
  }
 }
};

void CAlogrithm::setLength(int l)
{
 this->t.length = l;
}

void CAlogrithm::setMemKey(int i, int k)
{
 this->t.r[i].key = k;
}

void CAlogrithm::cout()
{
 int i=0;
 printf("----------++++++++++++---------------------/n");
 for(i=1; i<= t.length; i++)
  printf("Before sort r[%d].key=%d/n",i, t.r[i].key);
 printf("----------++++++++++++---------------------/n");

}

排序核心算法说明

一，将第一条记录看作有序子序列

二，依次从第二条记录起通过比较逐个插入有序子序列中。

//客户端测试代码

int main(int argc, char* argv[])
{
 int i=0;   
 CAlogrithm demo;
 demo.setLength(5);

 demo.setMemKey(1, 6);
 demo.setMemKey(2, 20);
 demo.setMemKey(3, 15);
 demo.setMemKey(4, 7);
 demo.setMemKey(5, 3);
 
 demo.cout();
 demo.InsertSort();
 demo.cout();
 
 return 0;
}

//结果输出。

　----------++++++++++++---------------------
Before sort r[1].key=6
Before sort r[2].key=20
Before sort r[3].key=15
Before sort r[4].key=7
Before sort r[5].key=3
----------++++++++++++---------------------
----------++++++++++++---------------------
Before sort r[1].key=3
Before sort r[2].key=6
Before sort r[3].key=7
Before sort r[4].key=15
Before sort r[5].key=20
----------++++++++++++---------------------
Press any key to continue

时间复杂度。最好情况= O(n^2)