//
// D_InsertSort.cpp
// Sort
//
// Created by pOH7 on 12-11-10.
// Copyright (c) 2012年 pOH7. All rights reserved.
//
//直接插入排序
#include <iostream>
using namespace std;
#define ElemType int
#define MAXSIZE 20
class SqList
{
public:
SqList(ElemType *t, int length)
{
this->length = length;
for (int i = 1; i <= length; ++i)
{
r[i] = t[i - 1];
}
}
void D_InsertSort();
void display();
private:
ElemType r[MAXSIZE + 1];//r[0]作哨兵
int length;
};
void SqList::D_InsertSort()
{
int i, j;
for (i = 2; i <= length; ++i)
{
r[0] = r[i];//r[0] = r[j + 1]
for (j = i - 1; r[0] < r[j]; --j) r[j + 1] = r[j];
r[j + 1] = r[0];//将r[j + 1]插入有序区r[1..j]
}
}
void SqList::display()
{
//cout << "length = " << length << endl;
for (int i = 1; i <= length; ++i)
{
cout << r[i] << " ";
}
cout << endl;
}
int main()
{
ElemType t[] = {2, 4, 6, 8, 7, 1, 4, 1, 5};
int length = sizeof(t) / sizeof(*t);
SqList L(t, length);
L.display();
L.D_InsertSort();
L.display();
return 0;
}