学步园

/********************************************************************************************************************************
 *功  能：各种排序算法
 *作  者：JarvisChu
 *时  间：2010-05-01
 *知识点：
            直接插入排序：1. 从i=2开始，如果L[i]>L[i-1],则进入2
                                  2. L[0] = L[i],暂存L[i]，我们成L[i]为待插入的元素
                                  3. L[i] = L[i-1],将L[i-1]后移一位，占领原来L[i]的位置
                                  4. 将i-1之前的所有比待插入元素大的数据，都往后移动一位
                                  5. 将待插入的元素插入到不比它大的数的后面一位
            Shell排序思路：先将表分割成几个小组，每个小组进行直接插入排序，然后整体进行一趟直接插入排序
                          理解：小组内进行的直接插入排序使得key小的元素能迅速跳跃式的移动到前面，key大的元素能跳跃式的移动到后面
 *********************************************************************************************************************************/
#include <iostream>
using namespace std;

#define MAX_ARRAY_SIZE 300
typedef int ElemType;                                   //元素类型

/*静态查找表的顺序存储结构*/
typedef struct{
    ElemType elem[MAX_ARRAY_SIZE];
    int length;
}SSTable;

/*初始化静态查找表*/
bool InitSSTable(SSTable* pSSTable){
    pSSTable->length = 8; //实际的元素个数
    pSSTable->elem[0] = 0;//监察哨
    pSSTable->elem[1] = 49;//
    pSSTable->elem[2] = 38;//
    pSSTable->elem[3] = 65;//
    pSSTable->elem[4] = 97;//
    pSSTable->elem[5] = 76;//
    pSSTable->elem[6] = 13;//
    pSSTable->elem[7] = 27;//
    pSSTable->elem[8] = 49;//
    return true;
}

/*显示出静态表*/
void DisplaySSTable(SSTable table){
    for(int i=1;i<=table.length;i++){
        cout<<table.elem[i]<<",  ";
    }
    cout<<endl;
}

/*直接插入排序 O(n*n)*/
void InsertSort(SSTable* pSSTable){
    for(int i=2;i<=pSSTable->length;i++){
        if(pSSTable->elem[i] < pSSTable->elem[i-1]){
            pSSTable->elem[0] = pSSTable->elem[i];
            pSSTable->elem[i] = pSSTable->elem[i-1];

            int j=i-2;
            while(pSSTable->elem[0]<pSSTable->elem[j]){//凡是比它大的都往右移动
                pSSTable->elem[j+1] = pSSTable->elem[j];
                j--;
            }
/*
            int j;
            for(j=i-2;pSSTable->elem[0] < pSSTable->elem[j];j--){
 //               cout<<"将"<<pSSTable->elem[j]<<"移动到"<<pSSTable->elem[j+1]<<endl;
                pSSTable->elem[j+1] = pSSTable->elem[j];
            }
*/
            pSSTable->elem[j+1] = pSSTable->elem[0];
        }
    }
}

/*折半插入排序 O(n*n)*/
void BInsertSort(SSTable* pSSTable){
    for(int i=2;i<=pSSTable->length;i++){
        pSSTable->elem[0] = pSSTable->elem[i];
        int low = 1;
        int high = i-1;
        while(low<=high){
            int mid = (low+high)/2;
            if(pSSTable->elem[mid]>pSSTable->elem[0]) high = mid-1;//在下半区
            else low = mid+1;  //在上半区
        }
        //high+1就是应该插入的位置
        for(int j=i-1;j>=high+1;j--){
            pSSTable->elem[j+1] = pSSTable->elem[j];
        }
        pSSTable->elem[high+1] = pSSTable->elem[0];
    }
}

/*一趟以dk为增量的Shell插入排序*/
void ShellInsert(SSTable* pT,int dk){
    for(int group=1;group<=dk;group++){//分成dk个小组
        for(int i=group+dk;i<=pT->length;i+=dk){//对每一个小组进行直接插入排序
            if(pT->elem[i] < pT->elem[i-dk]){//当前元素值，比它这个小组内的前一个元素值小
                pT->elem[0] = pT->elem[i];//当前的元素暂时放在 0 处保存
                pT->elem[i] =pT->elem[i-dk];//将前一个元素移动到当前位置
                int j = i-2*dk;//小组内，当前位置的前面第二个
                while(j>=group+dk && pT->elem[j] > pT->elem[0]){// j>= 该小组的第一个元素的位置，且，pT[j]大于要比较的元素
                    pT->elem[j+dk] = pT->elem[j];
                    j -= dk;
                }
                pT->elem[j+dk] = pT->elem[0];
            }
        }
    }
}
/*Shell插入排序，用增量序列dlta，对pSSTable所指向的表做t次直接插入排序*/
void ShellSort(SSTable* pSSTable,int dlta[], int t){
    for(int k=0;k<t;k++){
        ShellInsert(pSSTable,dlta[k]);
    }
}

/*冒泡排序（交换排序）*/
void BubbleSort(SSTable* pT){
    for(int i=1;i<pT->length;i++){//控制排序趟数，共pT->length-1趟
        for(int j =1;j <= pT->length-i;j++){
            if(pT->elem[j] > pT->elem[j+1]){
                ElemType temp = pT->elem[j+1];
                pT->elem[j+1] = pT->elem[j];
                pT->elem[j] = temp;
            }
        }
    }
}

/*Partition函数，完成一趟快速排序，并返回轴位置*/
int Partition(SSTable* pT,int low,int high){
    int pivot = pT->elem[low];//以最低位为轴
    while(low < high){
        while(low < high && pT->elem[high] >= pivot) high--;
        pT->elem[low] = pT->elem[high];
        while(low < high && pT->elem[low] <= pivot) low++;
        pT->elem[high] =pT->elem[low];
    }
    pT->elem[low] = pivot;
    return low;
}
/*快排 O(nlogn)*/
void QSort(SSTable* pT,int low,int high){
    if(low < high){
        int pivot = Partition(pT,low,high);
        QSort(pT,low,pivot-1);
        QSort(pT,pivot+1,high);
    }
}

/*简单选择排序*/
void SelectSort(SSTable* pT){
    for(int i=1;i<=pT->length-1;i++){
        for(int j=i+1;j<=pT->length;j++){
            if(pT->elem[j] < pT->elem[i]){
                ElemType temp = pT->elem[j];
                pT->elem[j] = pT->elem[i];
                pT->elem[i] = temp;
            }
        }
    }
}

int main()
{
    SSTable ST;
/* 直接插入排序
    InitSSTable(&ST);
    InsertSort(&ST);
    DisplaySSTable(ST);
*/
/* 折半插入排序
    InitSSTable(&ST);
    BInsertSort(&ST);
    DisplaySSTable(ST);
*/
/* Shell排序
    InitSSTable(&ST);
    int dlta[4] = {5,3,2,1};
    ShellSort(&ST,dlta,4);
    DisplaySSTable(ST);
*/
/* 冒泡排序
    InitSSTable(&ST);
    BubbleSort(&ST);
    DisplaySSTable(ST);
*/
/* 快排
    InitSSTable(&ST);
    QSort(&ST,1,ST.length);
    DisplaySSTable(ST);
*/
/* 简单选择排序
    InitSSTable(&ST);
    SelectSort(&ST);
    DisplaySSTable(ST);
*/
    return 0;
}