各种排序

// sort_test.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#define M 5
#define N 10
#include <cstdio>
#include <iostream>

using namespace std;

//直接插入排序
//直接插入排序的时间复杂度为：O(n^2)
//若待排记录为“正序”时，时间复杂度可提高至：O(n)
void InsertSort_fun(int a[M])
{
    int i,j,key;
    for(i=1;i<M;i++)
        if(a[i]<a[i-1])
        {
            key=a[i];
            a[i]=a[i-1];
            //j=i-2;
            //cout << "j:"<< j <<"  a[j-2]"<< a[j] << endl;
            for(j=i-2;j>=0&&key<a[j];--j)//因为没有设哨兵，所以增加了一个条件j>=0
            {
                //cout << j << endl;
                a[j+1]=a[j];
            }
            a[j+1]=key;
        }
}

void InsertSort_test()
{
    printf("InsertSort test:\n");

    int i,a[5]={5,4,3,2,1};
    for(i=0;i<5;i++)
        printf("%d,",a[i]);
    cout << endl;
    InsertSort_fun(a);
    printf("after sort:\n");
    for(i=0;i<5;i++)
        printf("%d,",a[i]);
}


//折半插入排序
//折半插入相对直接插入减少了关键字的比较次数：O(nlogn)
//但移动次数不变，时间复杂度仍为：O(n^2)
void BInsertSort_fun(int a[M])
{
    int i,key,low,high,mid,j;
    for (i=1;i<M;i++)
    {
        
            key=a[i];
            a[i]=a[i-1];
            low=0;high=i-1;
            while(low<=high)
            {
                mid=(low+high)/2;
                if(key<a[mid])
                    high=mid-1;
                else
                    low=mid+1;
            }
            for(j=i-1;j>high-1;j--)
                a[j+1]=a[j];
            a[high+1]=key;
    }
}
        
void BInsertSort_test()
{
    printf("Bin InsertSort test:\n");

    int i,a[5]={1,3,2,5,4};
    for(i=0;i<5;i++)
        printf("%d,",a[i]);
    cout << endl;
    BInsertSort_fun(a);
    printf("after sort:\n");
    for(i=0;i<5;i++)
        printf("%d,",a[i]);
}


void ShellInsert(int a[N],int dk)
{
    int i,key,j;
    for(i=dk;i<N;i++)
    {
        if(a[i]<a[i-dk])
        {
            key=a[i];
            //a[i]=a[i-dk];
            for(j=i-dk;(j>=0)&&(key<a[j]);j-=dk)
                a[j+dk]=a[j];
        
            a[j+dk]=key;
        }
    }
}


//希尔排序
//注意使增量序列dlta[]中的值没有除1之外的公因子，并且最后一个增量值必须等于1
void ShellSort_fun(int a[N],int dlta[],int t)
{
    int k;
    for(k=0;k<t;++k)
        ShellInsert(a,dlta[k]);
}

void ShellSort_test()
{
    int dlta[3]={3,2,1};
    cout << " Shell sort test :" << endl;
    int i;
    int a[N]={2,1,5,3,6,8,7,10,9,4};
    cout << "befor sort:" << endl;
    for (i=0;i<N;i++)
        cout << a[i] << "," ;
    cout << endl;
    
    
    ShellSort_fun(a,dlta,3);
    cout << "after sort " << endl;
    for(i=0;i<N;i++)
        cout << a[i] << "," ;
    cout <<endl;
}


//冒泡排序
//时间复杂度：O(n^2)
//空间复杂度：1
//稳定性：稳定
void bubble_sort_fun(int a[],int n)
{
    int i,j,tmp,change=1;
    for(i=n-1;i>=1&&change;i--)
        for(j=0;j<i;j++)
        {
            change=0;
            if(a[j]>a[j+1])
            {
                change=1;
                tmp=a[j];
                a[j]=a[j+1];
                a[j+1]=tmp;
            }
        }
}


void bubble_sort_test()
{
    printf("Bubble  Sort test:\n");

    int i,a[5]={1,3,2,5,4};
    for(i=0;i<5;i++)
        printf("%d,",a[i]);
    cout << endl;
    bubble_sort_fun(a,M);
    printf("after sort:\n");
    for(i=0;i<5;i++)
        printf("%d,",a[i]);
}

void exchange(int & a,int &b)
{
    int tmp;
    tmp=a;
    a=b;
    b=tmp;
}



//快速排序
//在所有同数量级O(nlogn)的排序方法中，其平均性能最好
//但若初始记录关键字有序或基本有序时，快速排序将蜕化为冒泡排序，其时间复杂度为O(n^2)
//快速排序需要一个栈空间来实现递归，栈的最大深度为[log2n]+1，最坏情况深度为n
//前提：必须是顺序存储
//稳定性：不稳定

int partition(int a[M],int low,int high)
{
    //交换顺序表a中子表a[low...high]的记录，使枢轴记录到位，并返回其所在位置
    //此时在它之前（后）的记录均不大（小）于它
    int pivotkey;
    pivotkey=a[low];
    while(low<high)
    {
        while(low<high&&a[high]>=pivotkey)
            --high;
        exchange(a[low],a[high]);
        while(low<high&&a[low]<=pivotkey)
            ++low;
        exchange(a[low],a[high]);
    }
    return low;
}

void QSort(int a[],int low,int high)
{
    int pivotloc;
    if(low<high)
    {
        pivotloc=partition(a,low,high);
        QSort(a,low,pivotloc-1);
        QSort(a,pivotloc+1,high);
    }
}

void quick_sort_test()
{
    printf("Quick  Sort test:\n");

    int i,a[M]={1,3,2,5,4};
    for(i=0;i<M;i++)
        printf("%d,",a[i]);
    cout << endl;
    QSort(a,0,M-1);
    printf("after sort:\n");
    for(i=0;i<5;i++)
        printf("%d,",a[i]);
}
        

int SelectMinkey(int a[],int i,int n)
{
    int j,min=a[i],m=i;
    for(j=i+1;j<n;j++)
    {
        if(a[j]<min)
        {
            min=a[j];
            m=j;
        }
    }

    return m;
}

//简单选择排序
//无论记录的初始排列如何，所需进行的关键字间的比较次数相同，均为n(n-1)/2
//空间复杂度：1
void select_sort_fun(int a[],int n)
{
    int i,j;
    for(i=0;i<n;++i)
    {
        j=SelectMinkey(a,i,n);
        if(i!=j)
            exchange(a[i],a[j]);
    }
}

void select_sort_test()
{
    printf("Select  Sort test:\n");

    int i,a[M]={1,3,2,5,4};
    for(i=0;i<M;i++)
        printf("%d,",a[i]);
    cout << endl;
    select_sort_fun(a,M);
    printf("after sort:\n");
    for(i=0;i<5;i++)
        printf("%d,",a[i]);
}

int _tmain(int argc, _TCHAR* argv[])
{
    //
    //InsertSort_test();

    //
    //BInsertSort_test();

    //
    //ShellSort_test();

    //
    //bubble_sort_test();
    
    //
    //quick_sort_test();

    //
    select_sort_test();
    
    while(1);
    return 0;
}