[C++]直接插入排序

//

//  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;

}