学步园

说明：以下C++代码的实现参考严蔚敏的《数据结构（C语言版）》

实验目的：有序列{{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};其中{a,b}把a视为key，按照key的大小使用插入排序对序列进行排序

算法图示：

实验代码：

c10_1.cpp

#ifndef C10_1_H
#define C10_1_H

#include <iostream>
using namespace std;

#define MAXSIZE 20
typedef int KeyType;
typedef int InfoType;

typedef struct
{
	KeyType key;
	InfoType info;
}RedType;

typedef struct
{
	RedType r[MAXSIZE+1];//r[0]闲置，用作哨兵单元（用来存储要插入的数）
	int length;
}SqList;//连续的存储空间存储排序数据

class CLSort
{
private:
	SqList *list;
public:
	CLSort(SqList &list);
//	CLSort(const CLSort &sort);//拷贝构造函数
	void InsertSort();
	void printSqList();
	
};

#endif

algorithm10_1.cpp

#include "c10_1.h"

CLSort::CLSort(SqList &list)
{
	this->list = &list;
}

void CLSort::InsertSort()
{
	int i,j;
	for(i = 2; i<=(*list).length; i++)
	{
		if((*list).r[i].key<(*list).r[i-1].key)
		{
			(*list).r[0] = (*list).r[i];
//			(*list).r[i] = (*list).r[i-1];
//			for(j=i-2; (*list).r[0].key<(*list).r[j].key; j--)
			for(j=i-1; (*list).r[0].key<(*list).r[j].key; j--)
			{
				(*list).r[j+1] = (*list).r[j]; 
			}
			(*list).r[j+1] = (*list).r[0];
		}
	}
}

void CLSort::printSqList()
{
	for(int i=1; i<= (*list).length; i++)
	{
		cout<<(*list).r[i].key<<","<<(*list).r[i].info<<"  ";
	}
	cout<<endl;
}

main10_1.cpp

#include "c10_1.h"
#define N 8
 
int main()
{
	RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};

	SqList list;
	for(int i=1; i<=N; i++ )
	{
		list.r[i] = d[i-1];
	}
	list.length = N;

	CLSort sort(list);
	cout<<"排序前："<<endl;
	sort.printSqList();
	sort.InsertSort();
	cout<<"排序后："<<endl;
	sort.printSqList();
}

测试结果：

算法复杂度分析：

       对于插入排序，如果含n个数的序列已经按从小到大排列好了，根据程序的实现可知程序只进行了n-1次数据比较和0次数据移动结束了程序的运行。当这个序列是从大到小排列时，程序执行时间最长，需要进行(n-1)(n+2)/2（即1+2+...+n-1+n-1）次数据比较，还需要进行(n-1)(n+4)/2（即2+3+...+n-1+n+n-1）次数据移动。由以上分析，(n-1+0+(n-1)(n+2)/2+(n-1)(n+4)/2)/2=(n-1)(n+4)/2，所以算法复杂度为O(n*n)