数据结构——————排序算法代码实现(未完待续......)

蔚落 2022-04-13 05:40 117阅读 0赞

# 排序算法 #

*  插入排序
 *  折半插入排序
 *  希尔排序
 *  冒泡排序
 *  快速排序
 *  简单选择排序
 *  堆排序
 *  归并排序(未完成)
 *  基数排序(未完成)

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN = 1e6+7;
    int dt[MAXN], MOD = 1e9+7;
    typedef struct
    {
        
        int key;
        char *otherinfo;
    }ElemType;
    ElemType S[MAXN];
    typedef struct
    {
        
        ElemType *r;
        int length;
    }SqList;
    
    void InsertSort(SqList &L)//插入排序
    {
        
        int i,j;
        for(i = 2; i <= L.length; ++i)
        {
        
            if(L.r[i].key<L.r[i-1].key)
            {
        
                L.r[0] = L.r[i];
                L.r[i] = L.r[i-1];
                for(j = i-1; L.r[0].key < L.r[j].key; --j)
                    L.r[j+1] = L.r[j];
                L.r[j+1] = L.r[0];
            }
        }
    }
    
    void BInsertSort(SqList &L)//折半插入排序
    {
        
        int i, j, low, hight, mid;
    
        for(i = 2; i <= L.length; ++i)
        {
        
            L.r[0] = L.r[i];
            low = 1; hight = i-1;
            while(low <= hight)
            {
        
                mid = (low+hight)/2;
                if(L.r[0].key < L.r[mid].key) hight = mid - 1;
                else    low = mid + 1;
            }
            for(j = i - 1; j >= hight+1; --j)
                L.r[j+1] = L.r[j];
            L.r[hight+1] = L.r[0];
        }
    }
    
    void ShellInsert(SqList &L, int dk)
    {
        
        int i,j;
        for(i = dk + 1; i <= L.length; ++i)
        {
        
            if(L.r[i].key < L.r[i - dk].key)
            {
        
                L.r[0] = L.r[i];
                for(j = i - dk; j > 0 && L.r[0].key < L.r[j].key; j -= dk)
                    L.r[j + dk] = L.r[j];
                L.r[j + dk] = L.r[0];
            }
        }
    }
    
    void ShellSort(SqList &L, int t)//希尔排序
    {
        
        int k;
        for(k = t; k > 0; k = k/2)
            ShellInsert(L, k);
    
    //    puts("ss");
    }
    
    void BubbleSort(SqList &L)//冒泡排序
    {
        
        int j, m = L.length - 1, flag = 1;
        while((m > 0) && flag)
        {
        
            flag = 0;
            for(j = 1; j <= m; ++j)
                if(L.r[j].key > L.r[j+1].key)
                {
        
                    flag = 1;
                    ElemType t = L.r[j];
                    L.r[j] = L.r[j+1];
                    L.r[j+1] = t;
                }
                --m;
            }
    }
    
    int Partition(SqList &L,int low, int hight)
    {
        
            L.r[0] = L.r[low];
            int pivotkey = L.r[low].key;
            while(low < hight)
            {
        
                    while(low < hight && L.r[hight].key >= pivotkey)        --hight;
                    L.r[low] = L.r[hight];
                    while(low < hight && L.r[low].key <= pivotkey)          ++low;
                    L.r[hight] = L.r[low];
            }
            L.r[low] = L.r[0];
            return low;
    }
    void QSort(SqList &L, int low, int hight)
    {
        
            if(low < hight)
            {
        
                    int pivotloc = Partition(L, low, hight);
                    QSort(L, low, pivotloc - 1);
                    QSort(L, pivotloc + 1, hight);
            }
    }
    void QuickSort(SqList &L)//快速排序
    {
        
            QSort(L,1,L.length);
    }
    
    void SelectSort(SqList &L)//简单选择排序
    {
        
            for(int i = 1; i < L.length; ++i)
            {
        
                    int k = i;
                    for(int j = i + 1; j <= L.length; ++j)
                            if(L.r[j].key < L.r[k].key)
                                    k = j;
                    if(k != i)
                    {
        
                            ElemType t = L.r[i];
                            L.r[i] = L.r[k];
                            L.r[k] = t;
                    }
            }
    }
    
    void HeapAdjust(SqList &L, int s,int m)//调整为大根堆
    {
        
            ElemType rc = L.r[s];
            for(int j = 2 * s; j <= m; j *= 2)
            {
        
                    if(j < m && L.r[j].key < L.r[j+1].key)          ++j;
                    if(rc.key >= L.r[j].key)                        break;
                    L.r[s] = L.r[j];
                    s =  j;
            }
            L.r[s] = rc;
    }
    void CreatHeap(SqList &L)//建初堆
    {
        
            int  n = L.length;
            for(int i = n/2; i > 0; --i)
                    HeapAdjust(L,i,n);
    }
    void HeapSort(SqList &L)//堆排序
    {
        
            CreatHeap(L);
            for(int i = L.length; i > 1; --i)
            {
        
                    ElemType x =L.r[1];
                    L.r[1] = L.r[i];
                    L.r[i] = x;
                    HeapAdjust(L,1,i-1);
            }
    }
    
    void Merge(ElemType R[], ElemType T[], int low, int mid, int high)
    {
        
            int i = low, j = mid + 1, k = high;
            while(i <= mid && j <= high)
            {
        
                    if(R[i].key <= R[j].key)        T[k++] = R[i++];
                    else                            T[k++] = R[j++];
            }
            while(i <= mid)  T[k++] = R[i++];
            while(j <= high) T[k++] = R[j++];
    }
    
    void MSort(ElemType R[], ElemType T[], int low, int high)
    {
        
            if(low == high) T[low] = R[low];
            else
            {
        
                    int mid = (low + high)/2;
                    MSort(R, S, low,   mid );
                    MSort(R, S, mid+1, high);
                    Merge(S, T, low, mid, high);
            }
    }
    void MergeSort(SqList &L)
    {
        
    
            MSort(L.r, L.r, 1, L.length);
    }
    
    void menu()
    {
        
            cout<< " 1.插入排序\n"\
                   " 2.折半插入排序\n"\
                   " 3.希尔排序\n"\
                   " 4.冒泡排序\n"\
                   " 5.快速排序\n"\
                   " 6.简单选择排序\n"\
                   " 7.堆排序\n"\
                   " 8.归并排序(未完成)\n"\
                   " 9.基数排序(未完成)\n"\
                   " 0.退出\n"<<endl;
    }
    
    int main()
    {
        
            clock_t s,e;
            s = clock();
            /*正式程序*/
            ios::sync_with_stdio(0);
            SqList L;
            L.r = new ElemType[MAXN];
            int choose;
            int x = (int)1000;
            cout<<"请选择："<<endl;
            menu();
            cin>>choose;
    
            while(choose)
            {
        
                    cout<<"请输入随机生成的数据个数：";
                    cin>>x;
                    MOD = x*10+7;
                    srand(time(NULL));
                    L.length = x;
                    for(int i=1; i <= L.length; ++i)
                            L.r[i].key = (rand()*rand()-rand()*2 + MOD )%MOD;
                    cout<<"数据生成完毕，请问是InsertSort否要查看：Y/N"<<endl;
                    char ch;
                    cin>>ch;
                    if(ch == 'Y' || ch == 'y')
                    {
        
                            cout<<"数据如下所示；"<<endl;
                            for(int i = 1; i <= L.length; ++i)
                                    cout<<L.r[i].key<<" ";
                            cout<<endl<<endl;
                    }
                    cout<<"排序之后数据为："<<endl;
                    s = clock();
                    switch (choose)
                    {
        
                            case 1:InsertSort(L);break;
                            case 2:BInsertSort(L);break;
                            case 3:ShellSort(L, L.length);break;
                            case 4:BubbleSort(L);break;
                            case 5:QuickSort(L); break;
                            case 6:SelectSort(L);break;
                            case 7:HeapSort(L);  break;
                            case 8:  break;
                            case 9:  break;
                    }
                    for(int i = 1; i <= L.length; ++i)
                            cout<<L.r[i].key<<" ";
                    e = clock();
    
                    /**输出程序运行时间*****/
                    cout<<endl;
                    cout<<"程序运行时间："<<e - s<<"(ms)"<<endl<<endl;
                    cout<<"****************************************************"<<endl;
                    cout<<"请选择："<<endl;
                    menu();
                    cin>>choose;
            }
            return 0;
    }