template_sort.cpp

/*
 * template_sort.cpp
 *
 *  Created on: 2013-9-29
 *      Author: Administrator
 */
#include<iostream.h>
#if 0
/*template<class T>
//插入法
void Sort(T a[], int n)
{
    T temp;
    for(int i = 1; i < n; ++i)
    {
        int j = i; temp = a[i];
        while(j > 0&&temp<a[j-1])
        {
            a[j] = a[j-1];
            j--;
        }
        a[j] = temp;
    }
}*/

/*template <class T>
//冒泡法
void Sort(T a[], int n)
{
    int temp;
    for(int i = 0 ; i < n; i++)
    {
        for(int j = i+1; j < n; j++)
        {
            if(a[j]<a[i])
            {
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }
}*/
/*
template <class T>
//选择排序
void Sort(T a[], int n)
{
    int min,tmp;//必须要有一个tmp来记录交换时的j
    int j;
    for(int i = 0; i < n; i++)
    {
        min = a[i];
        for(j = i; j < n; j++)
        {
            //min = min<a[i]?min:a[i];
            if(a[j]<min)
            {
                min = a[j];
                tmp = j;
            }
        }
        if(a[i] != min)
        {
            a[tmp] = a[i];
            a[i] = min;
        }
    }
}
*/

template <class T>
//希尔排序
void Sort(T a[], int n)
{
    int flag,gap=n;
    int tmp;
    while(gap>0)
    {
        gap = gap/2;
        do{
            flag=0;
            for(int i = 0; i + gap < n;i++)
            {
                if(a[i]>a[i+gap])
                {
                    tmp = a[i];
                    a[i] = a[i+gap];
                    a[i+gap] = tmp;
                    flag = 1;
                }
            }//必须要有个flag 只有当for循环里不再交换时才可以跳出此\
            //while循环继续gap减半的操作
        }while(flag !=0);
    }
}

void swap(int *a,int *b)
{
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

template <class T>
//快速排序  传进来的t必须是长度减1 即最大下标值
void Sort(T a[],int s,int t)
{
    int i,j;
    if(s<t)
    {
        i = s;
        j = t+1;//因为下面的do while循环中j先减减 故此先加一
        while(1)
            {
            do
            {
                i++;//在基准元素的右边找出比基准元素小的元素
            }while(!(a[i] <= a[s] || i == t));
            do
            {
                j--;//在基准元素右边找出比基准元素大的元素
            }while(!(a[s]<=a[j] || j == s));
            if(i<j)
            {    //使得左边的是大的右边的是小的
                swap(&a[i],&a[j]);
            }
            else
                break;//当i>=j时跳出while循环
        }
        swap(&a[s],&a[j]);//交换基准元素和a[j]的位置真正实现、
                            //基准元素左边的都大于基准元素 右边的都小于基准元素
        Sort(a,s,j-1);         //递归对基准元素的左边进行排序
        Sort(a,j+1,t);        //递归对基准元素的右边进行排序
    }
}

template <class T>
void Display(T a[], int n)
{
    for(int i = 0; i < n; i++)
    {
        cout << a[i]<< "," ;
    }
    cout << endl;
}

int main(void)
{
    int a[] = {1,3,5,7,9,8,6,4,2,0,100};
    char b[] = {'i','d','A','2','g','z','e','h','k','7'};
    int *c = (int *)(&a+1);
    cout << "length is" << (c-a)<<endl;
    cout <<"整形数组原序列为:";
    Display(a,(c-a));
    cout <<"整形数组排序后序列为:";
    Sort(a,0,(c-a)-1);
    Display(a,(c-a));
    cout <<"字符数组原序列为:";
    Display(b,10);
    cout <<"字符数组排序后序列为:";
    Sort(b,10);
    Display(b,10);
    return 0;
}

#endif