精华内容
下载资源
问答
  • 六种内部排序算法比较:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。包含实验报告和源代码设计。
  • 内部排序算法比较

    2018-12-13 18:54:10
    (1) 对6种常用内部排序算法进行比较:冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序 (2) 待排序的表长不小于100,其中数据要用伪随机数产生,至少用5组不同的输入数据做比较 (3) 比较...
  • 内部排序算法比较.rar

    2019-05-22 14:07:45
    (1)对以下6中常用的内部排序算法进行比较:冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序和堆排序。 (2)待排序表的表长不小于100;其中的数据要用伪随机数产生程序产生;至少要用5组不同的输入...
  • 内部排序算法比较

    千次阅读 多人点赞 2018-12-13 19:24:18
    (1) 对6种常用内部排序算法进行比较:冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序 (2) 待排序的表长不小于100,其中数据要用伪随机数产生,至少用5组不同的输入数据做比较 ...

    《内部排序算法比较》

    一、【问题描述】
    在教科书中,各种内部排序算法的时间复杂度分析结果只给出算法的大致执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数,以获得直观感受
    【基本要求】
    (1) 对6种常用内部排序算法进行比较:冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序
    (2) 待排序的表长不小于100,其中数据要用伪随机数产生,至少用5组不同的输入数据做比较
    (3) 比较指标为关键字参加的比较次数和关键字的移动次数

    二、概要设计
    1(可排序表的抽象数据类型定义:
    ADT OrderableList{
    数据对象:D={ai|ai?IntegerSet,i=1,2,„,n,n?0}
    数据关系:R1={<ai-1,ai>|ai-1,ai?D,i=2,„,n}
    基本操作:
    InitList(n)
    操作结果:构造一个长度为n,元素值依次为1,2,„,n的有序表。
    RandomizeList(d,isInverseOrder)
    操作结果:首先根据isInverseOrder为True或False,将表置为逆序或正序,然后将表进行d(0
    ?d?8)级随机打乱。d为0时表不打乱,d越大,打乱程度越高。
    RecallList()
    操作结果:恢复最后一次用RandomizeList随机打乱得到的可排序表。
    ListLength()
    操作结果:返回可排序表的长度。
    ListEmpty()
    操作结果:若可排序表为空表,则返回Ture,否则返回False。
    BubbleSort( &c, &s)
    操作结果:进行起泡排序,返回关键字比较次数c和移动次数s。
    InsertSort( &c, &s)
    操作结果:进行插入排序,返回关键字比较次数c和移动次数s。
    SelectSort ( &c, &s)
    操作结果:进行选择排序,返回关键字比较次数c和移动次数s。
    QuickSort(&c, &s)
    操作结果:进行快速排序,返回关键字比较次数c和移动次数s。
    ShellSort(long &c, long &s)
    操作结果:进行希尔排序,返回关键字比较次数c和移动次数s。
    HeapSort (&c, &s)
    操作结果:进行堆排序,返回关键字比较次数c和移动次数s。
    ListTraverse(visit())
    操作结果:依次对L中的每个元素调用函数visit()。 }ADT OrderableList
    2(本程序包含两个模块:
    1)主程序模块
    void main(){
    初始化;
    do{
    接受命令;
    处理命令;
    }while(“命令”~=“退出”);
    }
    2)可排序表单元模块——实现可排序表的抽象数据类型; 各模块之间的调用关系如下:
    主程序模块
    可排序表单元模块
    三、详细设计
    1(根据题目要求和可排序表的基本操作特点,可排序表采用整数顺序表存储结构。

      //可排序表的元素类型 
        #define MAXSIZE 10000 //用作示例的顺序表的最大长度 typedef int BOOL; 
        typedef struct{ 
        int key; //关键字项 
        } RedType; //记录类型 
        typedef struct LinkList{ 
        RedType r[MAXSIZE]; 
        int Length; //顺序表长度 } LinkList; 
        int RandArray[MAXSIZE]; //内部操作 
        void RandomNum(){ 
        int i; 
        srand(20000); 
        for (i = 0; i < MAXSIZE; i++) 
        RandArray[i] = (int)rand(); //构建随机序列 } 
        void InitLinkList(LinkList *L){ //建立表 
        int i; 
        memset(L, 0, sizeof(LinkList)); 
        RandomNum(); 
        for (i = 0; i < MAXSIZE; i++) 
        L->r[i].key = RandArray[i]; //赋值 
        L->Length = i; 
        } 
        bool LT(int i, int j, int *CmpNum){ //比较i与j大小,返回0或1 
        (*CmpNum)++; 
        if (i < j) 
        return TRUE; 
        else 
        return FALSE; 
        } 
        void Display(LinkList *L){ //存储表到SortRes.txt文件中 
        FILE *f; 
        int i; 
        if ((f = fopen("SortRes.txt", "w")) == NULL){ 
        printf("can't open file\n"); 
        exit(0); 
        } 
        for (i = 0; i < L->Length; i++) 
        fprintf(f, "%d\n", L->r[i].key); 
        fclose(f); 
        } 
        //部分操作的伪码算法 
        //希尔排序 
        void ShellInsert(LinkList *L, int dk, int *CmpNum, int *ChgNum){ 
        int i, j; 
        RedType Temp; 
        for (i = dk; i < L->Length; i++){ 
        if (LT(L->r[i].key, L->r[i - dk].key, CmpNum)){ 
        memcpy(&Temp, &L->r[i], sizeof(RedType)); 
        for (j = i - dk; j >= 0 && LT(Temp.key, L->r[j].key, CmpNum); j -= dk){ 
        (*ChgNum)++; 
        memcpy(&L->r[j + dk], &L->r[j], sizeof(RedType)); 
        } 
        memcpy(&L->r[j + dk], &Temp, sizeof(RedType)); 
        } 
        } 
        } 
        void ShellSort(LinkList *L, int dlta[], int t, int *CmpNum, int *ChgNum){ 
        int k; 
        for (k = 0; k < t; k++) 
        ShellInsert(L, dlta[k], CmpNum, ChgNum); 
        } 
        //快速排序 
        int Partition(LinkList *L, int low, int high, int *CmpNum, int *ChgNum){ 
        RedType Temp; 
        int PivotKey; 
        memcpy(&Temp, &L->r[low], sizeof(RedType)); 
        PivotKey = L->r[low].key; 
        while (low < high){ 
        while (low < high && L->r[high].key >= PivotKey){ 
        high--; 
        (*CmpNum)++; 
        } 
        (*ChgNum)++; 
        memcpy(&L->r[low], &L->r[high], sizeof(RedType)); 
        while (low < high && L->r[low].key <= PivotKey){ 
        low++; 
        (*CmpNum)++; 
        } 
        (*ChgNum)++; 
        memcpy(&L->r[high], &L->r[low], sizeof(RedType)); 
        } 
        memcpy(&L->r[low], &Temp, sizeof(RedType)); 
        return low; 
        } 
        void QSort(LinkList *L, int low, int high, int *CmpNum, int *ChgNum){ 
        int PivotLoc = 0; 
        if (low < high){ 
        PivotLoc = Partition(L, low, high, CmpNum, ChgNum); 
        QSort(L, low, PivotLoc - 1, CmpNum, ChgNum); 
        QSort(L, PivotLoc + 1, high, CmpNum, ChgNum); 
        } 
        } 
        void QuickSort(LinkList *L, int *CmpNum, int *ChgNum){ 
        QSort(L, 0, L->Length - 1, CmpNum, ChgNum); } 
        //堆排序 
        void HeapAdjust(LinkList *L, int s, int m, int *CmpNum, int *ChgNum){ 
        RedType Temp; 
        int j = 0; 
        s++; 
        memcpy(&Temp, &L->r[s - 1], sizeof(RedType)); 
        for (j = 2 * s; j <= m; j *= 2){ 
        if (j < m && LT(L->r[j - 1].key, L->r[j].key, CmpNum)) 
        ++j; 
        if (!LT(Temp.key, L->r[j - 1].key, CmpNum)) 
        break; 
        (*ChgNum)++; 
        memcpy(&L->r[s - 1], &L->r[j - 1], sizeof(RedType)); 
        s = j; 
        } 
        memcpy(&L->r[s - 1], &Temp, sizeof(RedType)); } 
        void HeapSort(LinkList *L, int *CmpNum, int *ChgNum){ 
        int i = 0; 
        RedType Temp; 
        for (i = L->Length / 2-1; i >= 0; i--) 
        HeapAdjust(L, i, L->Length, CmpNum, ChgNum); 
        for (i = L->Length; i > 1; i--){ 
        memcpy(&Temp, &L->r[0], sizeof(RedType)); 
        (*ChgNum)++; 
        memcpy(&L->r[0], &L->r[i - 1], sizeof(RedType)); 
        memcpy(&L->r[i - 1], &Temp, sizeof(RedType)); 
        HeapAdjust(L, 0, i - 1, CmpNum, ChgNum); 
        } 
        } 
        //冒泡排序 
        void BubbleSort(LinkList *L, int *CmpNum, int *ChgNum){ 
        int i, j; 
        RedType temp; 
        for (i = 1; i <= MAXSIZE; i++){ 
        for (j = 1; j <= MAXSIZE - i; j++){ 
        if (!LT(L->r[j].key, L->r[j + 1].key, CmpNum)){ 
        (*ChgNum)++; 
        memcpy(&temp, &L->r[j], sizeof(RedType)); 
        memcpy(&L->r[j], &L->r[j + 1], sizeof(RedType)); 
        memcpy(&L->r[j + 1], &temp, sizeof(RedType)); 
        } 
        } 
        } 
        } 
        //选择排序 
        int SelectMinKey(LinkList *L, int k, int *CmpNum){ 
        int Min = k; 
        for (; k < L->Length; k++){ 
        if (!LT(L->r[Min].key, L->r[k].key, CmpNum)) 
        Min = k; 
        } 
        return Min; 
        } 
        void SelSort(LinkList *L, int *CmpNum, int *ChgNum){ 
        int i, j; 
        RedType temp; 
        for (i = 0; i < L->Length; i++){ 
        j = SelectMinKey(L, i, CmpNum); 
        if (i != j){ 
        (*ChgNum)++; 
        memcpy(&temp, &L->r[i], sizeof(RedType)); 
        memcpy(&L->r[i], &L->r[j], sizeof(RedType)); 
        memcpy(&L->r[j], &temp, sizeof(RedType)); 
        } 
        } 
        } 
    

    四:调试分析:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    五、代码清单:

    内部排序算法比较.cpp 
    //主程序 
    #include <stdio.h> 
    #include <stdlib.h> 
    #include <string.h> 
    #include <time.h> 
    #include <windows.h> 
    #include <winbase.h> 
    #define MAXSIZE 5000 
    #define TRUE 1 
    #define FALSE 0 
    typedef int BOOL; 
    typedef struct{ 
    int key; 
    } RedType; 
    typedef struct LinkList{ 
    RedType r[MAXSIZE+1]; 
    int Length; 
    } LinkList; 
    int RandArray[MAXSIZE+1]; 
    void RandomNum(){ 
    int i; 
    srand(2000); 
    for (i = 1; i <= MAXSIZE; i++) 
    RandArray[i] = (int)rand(); } 
    void InitLinkList(LinkList *L){ 
    int i; 
    memset(L, 0, sizeof(LinkList)); 
    RandomNum(); 
    for (i = 1; i <= MAXSIZE; i++) 
    L->r[i].key = RandArray[i]; 
    L->Length = i; 
    } 
    bool LT(int i, int j, int *CmpNum){ 
    (*CmpNum)++; 
    if (i < j) 
    return TRUE; 
    else 
    return FALSE; 
    } 
    void Display(LinkList *L){ 
    FILE *f; 
    int i; 
    if ((f = fopen("SortRes.txt", "w")) == NULL){ 
    printf("can't open file\n"); 
    exit(0); 
    } 
    for (i = 0; i < L->Length; i++) 
    fprintf(f, "%d\n", L->r[i].key); 
    fclose(f); 
    } 
    //希尔排序 
    void ShellInsert(LinkList *L, int dk, int *CmpNum, int *ChgNum){ 
    int i, j; 
    RedType Temp; 
    for (i = dk; i < L->Length; i++){ 
    if (LT(L->r[i].key, L->r[i - dk].key, CmpNum)){ 
    memcpy(&Temp, &L->r[i], sizeof(RedType)); 
    for (j = i - dk; j >= 0 && LT(Temp.key, L->r[j].key, CmpNum); j -= dk){ 
    (*ChgNum)++; 
    memcpy(&L->r[j + dk], &L->r[j], sizeof(RedType)); 
    } 
    memcpy(&L->r[j + dk], &Temp, sizeof(RedType)); 
    } 
    } 
    } 
    void ShellSort(LinkList *L, int dlta[], int t, int *CmpNum, int *ChgNum){ 
    int k; 
    for (k = 0; k < t; k++) 
    ShellInsert(L, dlta[k], CmpNum, ChgNum); } 
    //快速排序 
    int Partition(LinkList *L, int low, int high, int *CmpNum, int *ChgNum){ 
    RedType Temp; 
    int PivotKey; 
    memcpy(&Temp, &L->r[low], sizeof(RedType)); 
    PivotKey = L->r[low].key; 
    while (low < high){ 
    while (low < high && L->r[high].key >= PivotKey){ 
    high--; 
    (*CmpNum)++; 
    } 
    (*ChgNum)++; 
    memcpy(&L->r[low], &L->r[high], sizeof(RedType)); 
    while (low < high && L->r[low].key <= PivotKey){ 
    low++; 
    (*CmpNum)++; 
    } 
    (*ChgNum)++; 
    memcpy(&L->r[high], &L->r[low], sizeof(RedType)); 
    } 
    memcpy(&L->r[low], &Temp, sizeof(RedType)); 
    return low; 
    } 
    void QSort(LinkList *L, int low, int high, int *CmpNum, int *ChgNum){ 
    int PivotLoc = 0; 
    if (low < high){ 
    PivotLoc = Partition(L, low, high, CmpNum, ChgNum); 
    QSort(L, low, PivotLoc - 1, CmpNum, ChgNum); 
    QSort(L, PivotLoc + 1, high, CmpNum, ChgNum); 
    } 
    } 
    void QuickSort(LinkList *L, int *CmpNum, int *ChgNum){ 
    QSort(L, 0, L->Length - 1, CmpNum, ChgNum); } 
    //堆排序 
    void HeapAdjust(LinkList *L, int s, int m, int *CmpNum, int *ChgNum){ 
    RedType Temp; 
    int j = 0; 
    s++; 
    memcpy(&Temp, &L->r[s - 1], sizeof(RedType)); 
    for (j = 2 * s; j <= m; j *= 2){ 
    if (j < m && LT(L->r[j - 1].key, L->r[j].key, CmpNum)) 
    ++j; 
    if (!LT(Temp.key, L->r[j - 1].key, CmpNum)) 
    break; 
    (*ChgNum)++; 
    memcpy(&L->r[s - 1], &L->r[j - 1], sizeof(RedType)); 
    s = j; 
    } 
    memcpy(&L->r[s - 1], &Temp, sizeof(RedType)); } 
    void HeapSort(LinkList *L, int *CmpNum, int *ChgNum){ 
    int i = 0; 
    RedType Temp; 
    for (i = L->Length / 2-1; i >= 0; i--) 
    HeapAdjust(L, i, L->Length, CmpNum, ChgNum); 
    for (i = L->Length; i > 1; i--){ 
    memcpy(&Temp, &L->r[0], sizeof(RedType)); 
    (*ChgNum)++; 
    memcpy(&L->r[0], &L->r[i - 1], sizeof(RedType)); 
    memcpy(&L->r[i - 1], &Temp, sizeof(RedType)); 
    HeapAdjust(L, 0, i - 1, CmpNum, ChgNum); 
    } 
    } 
    //冒泡排序 
    void BubbleSort(LinkList *L, int *CmpNum, int *ChgNum){ 
    int i, j; 
    RedType temp; 
    for (i = 1; i <= MAXSIZE; i++){ 
    for (j = 1; j <= MAXSIZE - i; j++){ 
    if (!LT(L->r[j].key, L->r[j + 1].key, CmpNum)){ 
    (*ChgNum)++; 
    memcpy(&temp, &L->r[j], sizeof(RedType)); 
    memcpy(&L->r[j], &L->r[j + 1], sizeof(RedType)); 
    memcpy(&L->r[j + 1], &temp, sizeof(RedType)); 
    } 
    } 
    } 
    } 
    //选择排序 
    int SelectMinKey(LinkList *L, int k, int *CmpNum){ 
    int Min = k; 
    for (; k < L->Length; k++){ 
    if (!LT(L->r[Min].key, L->r[k].key, CmpNum)) 
    Min = k; 
    } 
    return Min; 
    } 
    void SelSort(LinkList *L, int *CmpNum, int *ChgNum){ 
    int i, j; 
    RedType temp; 
    for (i = 0; i < L->Length; i++){ 
    j = SelectMinKey(L, i, CmpNum); 
    if (i != j){ 
    (*ChgNum)++; 
    memcpy(&temp, &L->r[i], sizeof(RedType)); 
    memcpy(&L->r[i], &L->r[j], sizeof(RedType)); 
    memcpy(&L->r[j], &temp, sizeof(RedType)); 
    } 
    } 
    } 
    void SelectSort(){ 
    printf("1. 插入排序\n"); 
    printf("2. 希尔排序\n"); 
    printf("3. 快速排序\n"); 
    printf("4. 堆排序\n"); 
    printf("5. 冒泡排序\n"); 
    printf("6. 选择排序\n"); 
    printf("7. 以上所有排序方式\n"); 
    printf("8. 退出程序\n\n"); 
    printf("Please Select the Operate:"); } 
    void AllAbove(LinkList *L, int *CmpNum, int *ChgNum){ 
    int TempTime, i,j; 
    int SpendTime; 
    int dlta[3] = { 
    7, 3, 1 
    }; 
    int Indata[1] = { 
    1 
    }; 
    for (i = 1; i <= MAXSIZE; i++) 
    L->r[i].key = RandArray[i]; //随机数列复位 
    printf("\n插入排序:\n"); 
    TempTime = (int)GetTickCount(); 
    ShellSort(L, Indata, 1, &CmpNum[0], &ChgNum[0]); 
    SpendTime = (int)GetTickCount() - TempTime; 
    printf("\nCompareNumber=%d\tChageNumber=%d\tTimeSpent=%dms\n", CmpNum[0], 
    ChgNum[0],SpendTime); 
    for (i = 1; i <= MAXSIZE; i++) 
    L->r[i].key = RandArray[i]; //随机数列复位 
    printf("\n希尔排序:\n"); 
    TempTime = (int)GetTickCount(); 
    ShellSort(L, dlta, 3, &CmpNum[1], &ChgNum[1]); 
    SpendTime = (int)GetTickCount() - TempTime; 
    printf("\nCompareNumber=%d\tChageNumber=%d\tTimeSpent=%dms\n", CmpNum[1], 
    ChgNum[1],SpendTime); 
    for (i = 1; i <= MAXSIZE; i++) 
    L->r[i].key = RandArray[i]; //随机数列复位 
    printf("\n快速排序:\n"); 
    TempTime = (int)GetTickCount(); 
    QuickSort(L, &CmpNum[2], &ChgNum[2]); 
    SpendTime = (int)GetTickCount() - TempTime; 
    printf("\nCompareNumber=%d\tChageNumber=%d\tTimeSpent=%dms\n", CmpNum[2], 
    ChgNum[2],SpendTime); 
    for (i = 1; i <= MAXSIZE; i++) 
    L->r[i].key = RandArray[i]; //随机数列复位 
    printf("\n堆排序:\n"); 
    TempTime = (int)GetTickCount(); 
    HeapSort(L, &CmpNum[3], &ChgNum[3]); 
    SpendTime = (int)GetTickCount() - TempTime; 
    printf("\nCompareNumber=%d\tChageNumber=%d\tTimeSpent=%dms\n", CmpNum[3], 
    ChgNum[3],SpendTime); 
    for (i = 1; i <= MAXSIZE; i++) 
    L->r[i].key = RandArray[i]; //随机数列复位 
    printf("\n冒泡排序:\n"); 
    TempTime = (int)GetTickCount(); 
    BubbleSort(L, &CmpNum[4], &ChgNum[4]); 
    SpendTime = (int)GetTickCount() - TempTime; 
    printf("\nCompareNumber=%d\tChageNumber=%d\tTimeSpent=%dms\n", CmpNum[4], 
    ChgNum[4],SpendTime); 
    for (i = 1; i <= MAXSIZE; i++) 
    L->r[i].key = RandArray[i]; //随机数列复位 
    printf("\n选择排序:\n"); 
    TempTime = (int)GetTickCount(); 
    SelSort(L, &CmpNum[5], &ChgNum[5]); 
    SpendTime = (int)GetTickCount() - TempTime; 
    printf("\nCompareNumber=%d\tChageNumber=%d\tTimeSpent=%dms\n", CmpNum[5], 
    ChgNum[5],SpendTime); 
    } 
    void main(){ 
    int i,j; 
    int select = 0; 
    int dlta[3] = {7, 3, 1}; 
    int Indata[1] = {1}; 
    int CmpNum[8], ChgNum[8]; 
    int SpendTime = 0; 
    int TempTime; 
    LinkList L; 
    InitLinkList(&L); 
    memset(CmpNum, 0, sizeof(CmpNum)); 
    memset(ChgNum, 0, sizeof(ChgNum)); 
    do{ 
    SelectSort(); 
    for (i = 0; i < MAXSIZE; i++) 
    L.r[i].key = RandArray[i]; //随机数列复位 
    scanf("%d", &select); 
    switch (select){ 
    case 1: 
    printf("\n插入排序:\n"); 
    TempTime = (int)GetTickCount(); 
    ShellSort(&L, Indata, 1, &CmpNum[select], &ChgNum[select]); 
    SpendTime = (int)GetTickCount() - TempTime; 
    for(i=1;i<=MAXSIZE;i++){ 
    printf("%5d ",L.r[i].key); 
    if(++j%10==0)printf("\n"); 
    } 
    printf("\n\nCompareNumber=%d\tChageNumber=%d\tTimeSpent=%dms\n", 
    CmpNum[select],ChgNum[select], SpendTime); 
    break; 
    case 2: 
    printf("\n希尔排序:\n"); 
    TempTime = (int)GetTickCount(); 
    ShellSort(&L, dlta, 3, &CmpNum[select], &ChgNum[select]); 
    SpendTime = (int)GetTickCount() - TempTime; 
    for(i=1;i<=MAXSIZE;i++){ 
    printf("%5d ",L.r[i].key); 
    if(++j%10==0)printf("\n"); 
    } 
    printf("\n\nCompareNumber=%d\tChageNumber=%d\tTimeSpent=%dms\n", 
    CmpNum[select],ChgNum[select], SpendTime); 
    break; 
    case 3: 
    printf("\n快速排序:\n"); 
    TempTime = (int)GetTickCount(); 
    QuickSort(&L, &CmpNum[select], &ChgNum[select]); 
    SpendTime = (int)GetTickCount() - TempTime; 
    for(i=1;i<=MAXSIZE;i++){ 
    printf("%5d ",L.r[i].key); 
    if(++j%10==0)printf("\n"); 
    } 
    printf("\n\nCompareNumber=%d\tChageNumber=%d\tTimeSpent=%dms\n", 
    CmpNum[select],ChgNum[select], SpendTime); 
    break; 
    case 4: 
    printf("\n堆排序:\n"); 
    TempTime = (int)GetTickCount(); 
    HeapSort(&L, &CmpNum[select], &ChgNum[select]); 
    SpendTime = (int)GetTickCount() - TempTime; 
    for(i=1;i<=MAXSIZE;i++){ 
    printf("%5d ",L.r[i].key); 
    if(++j%10==0)printf("\n"); 
    } 
    printf("\n\nCompareNumber=%d\tChageNumber=%d\t\tTimeSpent=%dms\n",CmpNum[select], 
    ChgNum[select], SpendTime); 
    break; 
    case 5: 
    printf("\n冒泡排序:\n"); 
    TempTime = (int)GetTickCount(); 
    BubbleSort(&L, &CmpNum[select], &ChgNum[select]); 
    SpendTime = (int)GetTickCount() - TempTime; 
    for(i=1;i<=MAXSIZE;i++){ 
    printf("%5d ",L.r[i].key); 
    if(++j%10==0)printf("\n"); 
    } 
    printf("\n\nCompareNumber=%d\tChageNumber=%d\tTimeSpent=%dms\n", 
    CmpNum[select],ChgNum[select], SpendTime); 
    break; 
    case 6: 
    printf("\n选择排序:\n"); 
    TempTime = (int)GetTickCount(); 
    SelSort(&L, &CmpNum[select], &ChgNum[select]); 
    SpendTime = (int)GetTickCount() - TempTime; 
    for(i=1;i<=MAXSIZE;i++){ 
    printf("%5d ",L.r[i].key); 
    if(++j%10==0)printf("\n"); 
    } 
    printf("\n\nCompareNumber=%d\tChageNumber=%d\tTimeSpent=%dms\n", 
    CmpNum[select],ChgNum[select], SpendTime); 
    break; 
    case 7: 
    AllAbove(&L, CmpNum, ChgNum); 
    break; 
    } 
    } 
    while (select != 8 ); 
    Display(&L); 
    } 
    
    
    

    答疑群:675511725

    展开全文
  • (1)对以下10种常用的内部排序算法进行比较:直接插入排序;折半折入排序;二路插入排序;希尔排序;冒泡排序;快速排序;简单选择排序;堆排序;归并排序;基数排序。 (2)待排序表的表长不少于100;其中的数据要...
  • 本演示程序对以下6种常用的内部排序算法进行实测比较:起泡排序,直接插入排序,简单选择排序,快速排序,希尔排序,堆排序
  • (1)对以下6种常用的内部排序算法进行比较z起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 (2)待排序表的表长不小于1005其中的数据要用伪随机数产生程序产生:至少要用5组不同的输入数据作比较...
  • 内部排序算法比较

    2012-07-04 22:46:33
    对以下六种常用的内部排序算法进行比较:希尔排序、直接选择排序、快速排序、直接插入排序、堆排序、冒泡排序。
  • 要求对以下6种常用的内部排序算法进行比较:起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。待排序表的表长不小于1000;其中的数据要用伪随机数产生程序产生,至少要用5组不同的输入数据作比较...
  • 《数据结构》之内部排序算法比较

    千次阅读 2020-06-29 15:00:16
    (1) 从以下常用的内部排序算法至少选取5种进行比较:直接插入排序;折半折入排序;希尔排序;起泡排序;快速排序;简单选择排序;堆排序;归并排序。 (2) 待排序表的表长为20000;其中的数据要用伪随机数产生...

    前言

    各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数,以取得直观感受。
    基本要求:
    (1) 从以下常用的内部排序算法至少选取5种进行比较:直接插入排序;折半折入排序;希尔排序;起泡排序;快速排序;简单选择排序;堆排序;归并排序。
    (2) 待排序表的表长为20000;其中的数据要用伪随机数产生程序产生;至少要用5组不同的输入数据作比较;比较的指标为有关键字参加的比较次数和关键字移动次数(关键字交换计为3次移动)。

    直接上代码
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <time.h>
    #define MAX 20000
    typedef struct SORTTYPE
    {
        char name[30]; //排序名称
        int num_compare;       //比较的次数
        int num_move;       //移动的次数
    } ST;        //存储分析效率的数据
    int num_compare = 0, num_move = 0; //关键字比较和移动的次数
    ST st[5];                 //五种算法的分析数据
    //直接插入排序算法
    void InsertSort(int a[], int n);
    //折半插入排序法
    void BinInsertSort(int a[], int n);
    //希尔排序算法
    void ShellSort(int a[], int n);
    //冒泡排序算法
    void BubbleSort(int a[], int n);
    /*快速排序算法*/
    int partition(int a[], int s, int t); //一趟划分
    //对a[s..t]的元素进行快速排序
    void QuickSort(int a[], int s, int t);
    //菜单
    void menu();
    //调用直接插入排序的实现函数,即菜单1
    void op1(int a[]);
    void op2(int a[]);
    void op3(int a[]);
    void op4(int a[]);
    void op5(int a[]);
    void op6(int a[]);
    //打印数组数据
    void printArray(int a[]);
    //给数组生成随机数
    void GetaandArray(int a[]);
    //五种常见的算法
    ///
    //直接插入排序算法
    void InsertSort(int a[], int n)
    {
        int i, j;
        int tmp;
        for (i = 1; i < n; i++) //for循环内一定比较了n-1次,if判断语句
        {
            if (a[i] < a[i - 1]) //一旦出现了逆序的关键字,就进行插入
            {
                tmp = a[i];
                j = i - 1;
                num_compare++;
                do //往后移动一个位置,腾空间给tmp;
                {
                    a[j + 1] = a[j];
                    num_move++; //移动加一
                    j--;
                    num_compare++; //比较次数加一
                }
                while (j >= 0 && a[j] > tmp);
    
                a[j + 1] = tmp; //最后把tmp放在对应的位置
                num_move += 2;  //移动的temp
            }
        }
    }
    
    //折半插入排序法
    //把无序区插入到有序区里,由于前面的插入排序法实现了有序,所以直接在
    //有序区利用折半查找来寻找的改进算法
    void BinInsertSort(int a[], int n)
    {
        int i, j, low, high, mid;
        int tmp;
        for (i = 1; i < n; i++) //已经比较了n-1次
        {
            if (a[i] < a[i - 1])
            {
                tmp = a[i];
                low = 0;
                high = i - 1;
                num_compare++;
                while (low <= high)
                {
                    num_compare++; //while进入比较
                    mid = (low + high) / 2;
                    if (tmp < a[mid])
                        high = mid - 1;
                    else
                        low = mid + 1;
                }
                for (j = i - 1; j >= high + 1; j--)
                {
                    a[j + 1] = a[j];
                    num_move++; //移动次数加一
                }
                a[high + 1] = tmp;
                num_move += 2; //tmp交换
            }
        }
    }
    ///
    //希尔排序算法
    void ShellSort(int a[], int n)
    {
        int i, j, d;
        int tmp;
        d = n / 2;
    
        while (d > 0)
        {
            for (i = d; i < n; i++)
            {
                tmp = a[i];
                j = i - d;
    
                while (j >= 0 && tmp < a[j])
                {
                    num_compare++;
                    num_move++;
                    a[j + d] = a[j];
                    j = j - d;
                }
                a[j + d] = tmp;
                num_move += 2; //tmp进行两次操作
            }
            d = d / 2;
        }
    }
    ///
    //冒泡排序算法
    void BubbleSort(int a[], int n)
    {
        int i, j;
        int tmp;
        for (i = 0; i < n - 1; i++)
        {
            for (j = n - 1; j > i; j--)
                if (a[j] < a[j - 1])
                {
                    num_compare++;
                    num_move += 3;
                    tmp = a[j - 1];
                    a[j - 1] = a[j];
                    a[j] = tmp;
                }
        }
    }
    /
    /*快速排序算法*/
    int partition(int a[], int s, int t) //一趟划分
    {
        int i = s, j = t;
        int tmp = a[i]; //以a[i]为基准
        while (i < j)   //从两端交替向中间扫描,直至i=j为止
        {
            while (j > i && a[j] >= tmp)
            {
                j--;           //从右向左扫描,找一个小于tmp的a[j]
                num_compare++; //进行比较
            }
            a[i] = a[j]; //找到这样的a[j],放入a[i]处
            num_move++;  //移动+1
            while (i < j && a[i] <= tmp)
            {
                i++;           //从左向右扫描,找一个大于tmp的a[i]
                num_compare++; //比较加一
            }
            a[j] = a[i]; //找到这样的a[i],放入a[j]处
            num_move++;  //移动加一
        }
        a[i] = tmp;
        num_move += 2; //temp的交换
        return i;
    }
    
    void QuickSort(int a[], int s, int t)
    //对a[s..t]的元素进行快速排序
    {
        int i;
        if (s < t) //区间内至少存在两个元素的情况
        {
            i = partition(a, s, t);
            QuickSort(a, s, i - 1); //对左区间递归排序
            QuickSort(a, i + 1, t); //对右区间递归排序
        }
    }
    /
    
    void menu()
    {
        printf("***************************************************\n");
        printf("\t\t1.直接插入排序法\n");
        printf("\t\t2.折半插入排序法\n");
        printf("\t\t3.希尔排序法\n");
        printf("\t\t4.冒泡排序法\n");
        printf("\t\t5.快速排序法\n");
        printf("\t\t6.效率比较\n");
        printf("\t\t7.退出\n");
        printf("***************************************************\n");
        printf("请选择操作:");
    }
    void printArray(int a[]) //打印数组数据
    {
        int i;
        for (i = 0; i < MAX; i++)
            printf("%2d%c", a[i], (i+1)%40 ? ' ' : '\n');
        putchar(10);
    }
    
    //调用直接插入排序的实现函数,即菜单1
    void op1(int a[])
    {
        GetaandArray(a);
        printf("伪随机数已经生成的20000个新的随机数\n");
        //打印排序前的数组
        // printArray(a);
        InsertSort(a, MAX);
        // printf("\n利用直接插入排序后的数列如下:\n");
        //打印排序后的数组
        // printArray(a);
        printf("\n\n直接插入排序法:\n一共比较了%d次,移动了%d次\n", num_compare, num_move);
        st[0].num_compare = num_compare;
        st[0].num_move = num_move;
        strcpy(st[0].name, "直接插入排序");
    }
    void op2(int a[])
    {
        GetaandArray(a);
        printf("已经生成20000个新的随机数\n");
        //打印排序前的数组
        //  printArray(a);
        num_compare = 0;
        num_move = 0;
        BinInsertSort(a, MAX);
        //  printf("\n利用折半插入排序后的数列如下:\n");
        //打印排序后的数组
        // printArray(a);
        printf("\n\n折半插入排序:\n一共比较了%d次,移动了%d次\n", num_compare, num_move);
        st[1].num_compare = num_compare;
        st[1].num_move = num_move;
        strcpy(st[1].name, "折半插入排序");
    }
    
    void GetaandArray(int a[]) //为数组获得随机数
    {
        int i;
        for (i = 0; i < MAX; i++)
            a[i] = rand() % 100;
    }
    void op3(int a[])
    {
        GetaandArray(a);
        printf("已经生成20000个新的随机数\n");
        //打印排序前的数组
        //printArray(a);
        num_compare = 0;
        num_move = 0;
        ShellSort(a, MAX);
        //printf("\n利用希尔排序算法后的数列如下:\n");
        //打印排序后的数组
        //printArray(a);
    
    
        printf("\n\n希尔排序算法:\n一共比较了%d次,移动了%d次\n", num_compare, num_move);
        st[2].num_compare = num_compare;
        st[2].num_move = num_move;
        strcpy(st[2].name, "希尔排序算法");
    }
    void op4(int a[])
    {
        GetaandArray(a);
        printf("已经生成20000个新的随机数\n");
    
        //打印排序前的数组
        // printArray(a);
    
        num_compare = 0;
        num_move = 0;
        BubbleSort(a, MAX);
    
        //  printf("\n利用冒泡排序法后的数列如下:\n");
        //打印排序后的数组
    
        //  printArray(a);
    
        printf("\n\n冒泡排序算法:\n一共比较了%d次,移动了%d次\n", num_compare, num_move);
        st[3].num_compare = num_compare;
        st[3].num_move = num_move;
        strcpy(st[3].name, "冒泡排序算法");
    }
    void op5(int a[])
    {
        GetaandArray(a);
        printf("已经生成20000个新的随机数\n");
    
        //打印排序前的数组
        //printArray(a);
        num_compare = 0;
        num_move = 0;
        QuickSort(a, 0, MAX);
        //  printf("\n利用快速排序算法后的数列如下:\n");
        //打印排序后的数组
        // printArray(a);
        printf("\n\n快速排序算法:\n一共比较了%d次,移动了%d次\n", num_compare, num_move);
        st[4].num_compare = num_compare;
        st[4].num_move = num_move;
        strcpy(st[4].name, "快速排序算法");
    }
    void op6(int a[])
    {
        int i;
        printf("各种排序算法的比较于移动次数的对比:\n\n");
        printf("   名称          比较次数          移动次数\n");
    
        for (i = 0; i < 5; i++)
        {
            printf("%-18s%-18d %d\n", st[i].name, st[i].num_compare, st[i].num_move);
        }
    }
    int main()
    {
        int a[MAX]; //列表数组
        int op;
        srand((unsigned)time(NULL)); //随机种子
        do
        {
            system("cls");
            menu();
            scanf("%d", &op);
            switch (op)
            {
            case 1:
                op1(a);
                break;
            case 2:
                op2(a);
                break;
            case 3:
                op3(a);
                break;
            case 4:
                op4(a);
                break;
            case 5:
                op5(a);
                break;
            case 6:
                op6(a);
                break;
            default:
                break;
            }
            system("pause");
    
        }while(op!=7);
        return 0;
    }
    
    

    效果图

    在这里插入图片描述

    展开全文
  • c++内部排序算法比较

    2010-12-22 21:20:50
    列举了直接插入排序,折半插入排序,冒泡排序,简单选择排序,希尔排序,快速排序,堆排序七种内部排序关键字的比较次数和移动次数,对它们的优劣取得直观的感受。并附有文档。
  • 内部排序算法比较 第一章 问题描述 排序是数据结构中重要的一个部分也是在实际开发中易遇到的问题所以研究各种排 算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使 用哪种算法可以...
  • 1、本演示程序对以下6种常用的内部排序算法进行实测比较:起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 2、待排序表的表的元素的关键字为整数,表长不小于100;其中的数据要用伪随机数产生...
  • 前言堆排序是以堆为原型的排序。堆首先是一棵二叉树,具有以下两个性质:每个节点的值大于或者等于其左右孩子结点的值,称为大顶堆;或者每个节点的值都小于或者等于其左右孩子结点的值,称为小顶堆。从这个定义中...

    前言

    堆排序是以堆为原型的排序。堆首先是一棵二叉树,具有以下两个性质:每个节点的值大于或者等于其左右孩子结点的值,称为大顶堆;或者每个节点的值都小于或者等于其左右孩子结点的值,称为小顶堆。从这个定义中可以发现,堆得根节点要么是最大值要么是最小值。实现堆排序的基本思想是:将待排序的序列构造成一个大顶堆或者小顶堆。此时整个堆满足根节点是最大值或者最小值。将根节点移走,并与堆数组的最后一个值进行交换,这样的话最后一个值就是最大值或者最小值了。然后将剩余n-1(假设原来总共有n个元素)未排序的序列重新构造成一个最大堆或者最小堆,再与除原来最大值之外的最后一个元素进行交换,得到次小值。如此反复进行,就得到一个排序的序列。

    堆排序算法的Java实现

    package com.rhwayfun.algorithm.sort;
    
    public class HeapSort2 {
    
        public void heapSort(int[] a){
            for(int i = a.length/2-1; i >= 0; i--){
                //建立一个最大堆
                heapAdjust(a,i,a.length - 1);
            }
            for (int i = a.length - 1; i > 0; i--) {
                //将堆顶元素与当前未经排序的最后一个记录交换
                swap(a,0,i);
                //将数组a中下标从0到i-1的子序列重新调整为最大堆
                heapAdjust(a, 0, i - 1);
            }
    
            for (int i = 0; i < a.length; i++) {
                System.out.println(a[i]);
            }
        }
    
        private void swap(int[] a, int i, int j) {
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    
        private void heapAdjust(int[] a, int s, int m) {
            int temp = 0,j=0;
            //把堆顶元素保存在临时变量中
            temp = a[s];
            //由于s可能是0,所以需要+1。此外,如果当前结点的序号是s,那么其左孩子是2*s+1(+1是因为s可能是0)
            for(j = 2*s+1; j <= m; j = 2*j+1){
                //找出左右孩子较大的结点的下标
                if(j < m && a[j] < a[j+1]){
                    ++j;
                }
                if(temp >= a[j]){
                    break;
                }
                //把较大的孩子结点的赋给当前结点
                a[s] = a[j];
                //把更大孩子结点的下标赋给s
                s = j;
            }
            //把原来s下标位置的值赋给新的下标为s的值,这样就完成了当前结点与更大孩子结点值的交换
            a[s] = temp;
        }
    
        public static void main(String[] args) {
            new HeapSort2().heapSort(new int[]{90,70,80,60,10,40,50,30,20});
        }
    }
    
    

    可以发现在建立最大堆的时候, i 是从a.length/2开始的,为什么要从这个位置开始呢?比如有一个数组 {90,70,80,60,10,40,50,30,20} ,初始情况是这样的:

    一共有9个元素,那么 a.length/21 的值是3,也就是第4个元素,执行for循环,i的值从3->2->1->0变化,可以发现这几个下标的结点都是有孩子结点的元素,所以第一个for循环就很好理解了:其实就是从下往上、从右到左,将每个非终端结点当做根节点,将其和子树调整成最大堆,所以下标3->2->1->0的变化,也就是60,80,70,90结点的调整过程。

    堆排序算法的时间复杂度

    可以发现堆排序的主要时间主要花在建堆和重建堆时的反复筛选上。在初始建堆的时候,由于只涉及两个节点的交换操作,所以建堆的时间复杂度是 O(n) 。在正式排序的时候,第i次取堆顶的元素并重建堆需要花去 O(logi) 的时间,需要n-1次取堆顶记录,所以排序的过程的时间复杂度是 O(nlogn) 。而且这是最好、最坏和平均的时间复杂度,但是由于记录的交换与比较是跳跃式的,所以与归并排序不同,堆排序是一种不稳定的排序算法。

    由于初始建堆的比较次数比较多,所以堆排序不适合记录数较少的情况(使用简单排序算法是一种不错的选择,没必要大材小用了)。

    展开全文
  • 《数据结构》--内部排序算法比较

    多人点赞 2020-06-15 21:45:03
    (1) 从以下常用的内部排序算法至少选取5种进行比较:直接插入排序;折半折入排序;希尔排序;起泡排序;快速排序;简单选择排序;堆排序;归并排序。 (2) 待排序表的表长为20000;其中的数据要用伪随机数产生...

    题目
    各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数,以取得直观感受。
    基本要求:
    (1) 从以下常用的内部排序算法至少选取5种进行比较:直接插入排序;折半折入排序;希尔排序;起泡排序;快速排序;简单选择排序;堆排序;归并排序。
    (2) 待排序表的表长为20000;其中的数据要用伪随机数产生程序产生;至少要用5组不同的输入数据作比较;比较的指标为有关键字参加的比较次数和关键字移动次数(关键字交换计为3次移动)。

    代码

    #ifndef _HEAD_H
    #define _HEAD_H
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <time.h>
    #define MAX 20002
    typedef int KeyType;
    typedef int InfoType;
    typedef struct SS
    {
        KeyType key;   //关键字项
        InfoType data; //其他数据项
    } RecType;         //排序的元素的类型
    
    typedef struct SSS
    {
        char name[30]; //排序名称
        int com;  //比较的次数
        int mov;  //移动的次数
    }Analysis;    //存储分析效率的4数据
    
    
    //交换函数
    void swap(RecType &a, RecType &b)
    {
        RecType c;
        c = a;
        a = b;
        b = c;
    }
    int compare = 0 , move = 0;  //关键字比较和移动的次数
    Analysis Analy[5];             //五种算法的分析数据
    //直接插入排序算法
    //时间复杂度O(n^2)
    void InsertSort(RecType R[], int n);
    //折半插入排序法 
    //把无序区插入到有序区里,由于前面的插入排序法实现了有序,所以直接在
    //有序区利用折半查找来寻找的改进算法
    void BinInsertSort(RecType R[], int n);
    //希尔排序算法
    void ShellSort(RecType R[], int n);
    //冒泡排序算法
    void BubbleSort(RecType R[], int n);
    /*快速排序算法*/
    int partition(RecType R[], int s, int t); //一趟划分
    //对R[s..t]的元素进行快速排序
    void QuickSort(RecType R[], int s, int t);
    //菜单
    void menu();
    //调用直接插入排序的实现函数,即菜单1
    void FirstFun(RecType a[], int n);
    //菜单2
    void SecondFun(RecType a[], int n);
    //菜单3
    void ThirdFun(RecType a[], int n);
    //菜单4
    void FourthFun(RecType a[], int n);
    //菜单5
    void FifthFun(RecType a[], int n);
    //菜单6
    void SixthFun(RecType a[], int n);
    #endif
    
    //五种常见的算法
    ///
    //直接插入排序算法
    //时间复杂度O(n^2)
    void InsertSort(RecType R[], int n)
    {
        int i, j;
        RecType tmp;
    
        for (i = 1; i < n; i++)    //for循环内一定比较了n-1次,if判断语句
        {
            if (R[i].key < R[i - 1].key) //一旦出现了逆序的关键字,就进行插入
            {
                tmp = R[i];
                j = i - 1;
                compare++;
                do    //往后移动一个位置,腾空间给tmp;
                {
                    R[j + 1] = R[j];
                    move++;    //移动加一
                    j--;
                    compare++; //比较次数加一
                } while (j >= 0 && R[j].key > tmp.key);
    
                R[j + 1] = tmp; //最后把tmp放在对应的位置
                move+=2; //移动的temp
            }
        }
        
    }
    
    //折半插入排序法 
    //把无序区插入到有序区里,由于前面的插入排序法实现了有序,所以直接在
    //有序区利用折半查找来寻找的改进算法
    void BinInsertSort(RecType R[], int n)
    {
        int i, j, low, high, mid;
        RecType tmp;
    
        for (i = 1; i < n; i++)  //已经比较了n-1次
        {
            if (R[i].key < R[i - 1].key)
            {
                tmp = R[i];
                low = 0;
                high = i - 1;
                
                compare++;
    
                while (low <= high)  
                {
                    compare++;  //while进入比较
                    mid = (low + high) / 2;
                    if (tmp.key < R[mid].key)
                        high = mid - 1;
                    else
                        low = mid + 1;
                }
    
                for (j = i - 1; j >= high + 1; j--)
                {      
                    R[j + 1] = R[j];
                    move++;//移动次数加一
                }
                R[high + 1] = tmp;
                move += 2;//tmp交换
            }
        }
    
    }
    ///
    //希尔排序算法
    void ShellSort(RecType R[], int n)
    {
        int i, j, d;
        RecType tmp;
        d = n / 2;
    
        while (d > 0)
        {
            for (i = d; i < n; i++)
            {
                tmp = R[i];
                j = i - d;
    
                while (j >= 0 && tmp.key < R[j].key)
                {
                    compare++;
                    move++;
                    R[j + d] = R[j];
                    j = j - d;
                }
                R[j + d] = tmp;
                move += 2;//tmp进行两次操作
            }
            d = d / 2;
        }
    }
    ///
    //冒泡排序算法
    void BubbleSort(RecType R[], int n)
    {
        int i, j;
        bool exchange;
        RecType tmp;
    
        for (i = 0; i < n - 1; i++)
        {
            exchange = false;
    
            for (j = n - 1; j > i; j--)
                if (R[j].key < R[j - 1].key)
                {
                    compare ++;
                    move += 3;
                    tmp = R[j - 1];
                    R[j - 1] = R[j];
                    R[j] = tmp;
                    exchange = true;
                }
    
            if (!exchange)
                return;
        }
    }
    /
    /*快速排序算法*/
    int partition(RecType R[], int s, int t) //一趟划分
    {
        int i = s, j = t;
        RecType tmp = R[i]; //以R[i]为基准
        while (i < j)       //从两端交替向中间扫描,直至i=j为止
        {
            while (j > i && R[j].key >= tmp.key)
            {
                    j--;     //从右向左扫描,找一个小于tmp.key的R[j]
                    compare++;//进行比较
            }
            R[i] = R[j]; //找到这样的R[j],放入R[i]处
            move++;      //移动+1
            while (i < j && R[i].key <= tmp.key)
            {    i++;      //从左向右扫描,找一个大于tmp.key的R[i]
                 compare++;//比较加一
            }
            R[j] = R[i]; //找到这样的R[i],放入R[j]处
            move++;      //移动加一
        }
        R[i] = tmp;
        move+=2; //temp的交换
        return i;
    }
    
    void QuickSort(RecType R[], int s, int t)
    //对R[s..t]的元素进行快速排序
    {
        int i;
        if (s < t) //区间内至少存在两个元素的情况
        {
            i = partition(R, s, t);
            QuickSort(R, s, i - 1); //对左区间递归排序
            QuickSort(R, i + 1, t); //对右区间递归排序
        }
    }
    /
    
    void menu()
    {
        printf("***************************************************\n");
        printf("\t\t1.直接插入排序法\n");
        printf("\t\t2.折半插入排序法\n");
        printf("\t\t3.希尔排序法\n");
        printf("\t\t4.冒泡排序法\n");
        printf("\t\t5.快速排序法\n");
        printf("\t\t6.效率比较\n");
        printf("\t\t7.退出\n");
        printf("***************************************************\n");
    }
    
    
    //调用直接插入排序的实现函数,即菜单1
    void FirstFun(RecType a[], int n)
    {
         int i;
         for (i = 0; i < MAX; i++)
            a[i].key = rand() % 100;
        printf("伪随机数生成的20002个随机数:\n\n\n");
        for (i = 0; i < MAX; i++)
            printf("%3d%c", a[i].key, (i + 1) % 20 ? ' ' : '\n');
            putchar(10);
        
        InsertSort(a, MAX);
    
        printf("\n\n\n利用直接插入排序后的数列如下:\n\n\n");
        for (i = 0; i < MAX; i++)
            printf("%3d%c", a[i].key, (i + 1) % 20 ? ' ' : '\n');
        
        printf("\n\n直接插入排序法:\n一共比较了%d次,移动了%d次\n",compare,move);
        Analy[0].com = compare;
        Analy[0].mov = move;
        strcpy(Analy[0].name, "直接插入排序");
    }
    //菜单2
    void SecondFun(RecType a[], int n)
    {
        int i;
         for (i = 0; i < MAX; i++)
            a[i].key = rand() % 100;
        printf("伪随机数生成的20002个随机数:\n\n\n");
        for (i = 0; i < MAX; i++)
            printf("%3d%c", a[i].key, (i + 1) % 20 ? ' ' : '\n');
            putchar(10);
    
        compare = 0;
        move = 0;
        BinInsertSort(a, MAX);
    
        printf("\n\n\n利用折半插入排序后的数列如下:\n\n\n");
        for (i = 0; i < MAX; i++)
            printf("%3d%c", a[i].key, (i + 1) % 20 ? ' ' : '\n');
        
        printf("\n\n折半插入排序:\n一共比较了%d次,移动了%d次\n",compare,move);
        Analy[1].com = compare;
        Analy[1].mov = move;
        strcpy(Analy[1].name, "折半插入排序");
    }
    
    //菜单3
    void ThirdFun(RecType a[], int n)
    {
        int i;
         for (i = 0; i < MAX; i++)
            a[i].key = rand() % 100;
        printf("伪随机数生成的20002个随机数:\n\n\n");
        for (i = 0; i < MAX; i++)
            printf("%3d%c", a[i].key, (i + 1) % 20 ? ' ' : '\n');
            putchar(10);
    
        compare = 0;
        move = 0;
        ShellSort(a,MAX);
    
            printf("\n\n\n利用希尔排序算法后的数列如下:\n\n\n");
        for (i = 0; i < MAX; i++)
            printf("%3d%c", a[i].key, (i + 1) % 20 ? ' ' : '\n');
        
        printf("\n\n希尔排序算法:\n一共比较了%d次,移动了%d次\n",compare,move);
        Analy[2].com = compare;
        Analy[2].mov = move;
        strcpy(Analy[2].name, "希尔排序算法");
    }
    //菜单4
    void FourthFun(RecType a[], int n)
    {
         int i;
         for (i = 0; i < MAX; i++)
            a[i].key = rand() % 100;
        printf("伪随机数生成的20002个随机数:\n\n\n");
        for (i = 0; i < MAX; i++)
            printf("%3d%c", a[i].key, (i + 1) % 20 ? ' ' : '\n');
            putchar(10);
    
        compare = 0;
        move = 0;
        BubbleSort(a,MAX);
    
         printf("\n\n\n利用冒泡排序法后的数列如下:\n\n\n");
        for (i = 0; i < MAX; i++)
            printf("%3d%c", a[i].key, (i + 1) % 20 ? ' ' : '\n');
        
        printf("\n\n冒泡排序算法:\n一共比较了%d次,移动了%d次\n",compare,move);
        Analy[3].com = compare;
        Analy[3].mov = move;
        strcpy(Analy[3].name, "冒泡排序算法");
    }
    //菜单5
    void FifthFun(RecType a[], int n)
    {
        int i;
         for (i = 0; i < MAX; i++)
            a[i].key = rand() % 100;
        printf("伪随机数生成的20002个随机数:\n\n\n");
        for (i = 0; i < MAX; i++)
            printf("%3d%c", a[i].key, (i + 1) % 20 ? ' ' : '\n');
            putchar(10);
        
        compare = 0;
        move = 0;
        QuickSort(a,0,MAX);
             printf("\n\n\n利用快速排序算法后的数列如下:\n\n\n");
        for (i = 0; i < MAX; i++)
            printf("%3d%c", a[i].key, (i + 1) % 20 ? ' ' : '\n');
    
        printf("\n\n快速排序算法:\n一共比较了%d次,移动了%d次\n",compare,move);
        Analy[4].com = compare;
        Analy[4].mov = move;
        strcpy(Analy[4].name, "快速排序算法");
    }
    //菜单6
    void SixthFun(RecType a[], int n)
    {
        int i;
        printf("各种排序算法的比较于移动次数的对比:\n\n");
        //printf("   名称\t\t\t\t比较次数\t\t\t移动次数\n");
        printf("   名称          比较次数          移动次数\n");
    
        for(i = 0; i < 5; i++)
            printf("%-17s%-18d%d\n",Analy[i].name,Analy[i].com,Analy[i].mov);
    }
    
    int main ()
    {
        RecType a[MAX];
        int i, k;
        srand((unsigned)time(NULL));
        menu();
        printf("请选择操作:");
        scanf("%d",&k);
    
        while(k!=7)
        {
            switch(k) {
                case 1:  FirstFun(a,MAX);  break;
                case 2:  SecondFun(a,MAX); break;
                case 3:  ThirdFun(a,MAX);  break;
                case 4:  FourthFun(a,MAX); break;
                case 5:  FifthFun(a,MAX);  break;
                case 6:  SixthFun(a,MAX);  break;
                default:   break;
            }
            
            system("pause");
            system("cls");
            menu();
            printf("请选择操作:");
            scanf("%d",&k);
    
        }
    
    
        system("pause");
        return 0;
    }
    

    运行结果
    结果如图所示
    记得点赞啊!!
    在这里插入图片描述

    展开全文
  • 排序算法堆排序

    2014-06-07 15:29:36
    排序算法堆排序
  • 设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。 【基本要求】 (1)实现各种内部排序。包括冒泡排序,直接选择排序,希尔排序,快速排序,堆排序。 (2) 待排序的元素的关键字为整数...
  • 进行典型内部排序算法比较,随机产生整数样本,进行四种排序,并比较各种排序算法的执行时间。 #include "stdio.h" #include "stdlib.h" #include "conio.h" #include "time.h" #define MAXSIZE 20 typedef ...
  • 内部排序算法

    2012-07-04 15:13:32
    问题描述:对以下各种常用的内部排序算法进行比较: 冒泡排序、直接排序、简单选择排序、快速排序、希尔排序、排算法的表长不少于100,要求采用随机数,至少要用5组不同的输入数据做比较比较的次数为有关键字...
  • (1)对以下6种常用的内部排序算法进行比较:起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 (2)待排序表的表长不小于100;其中的数据要用伪随机数产生程序产生;至少要用5组不同的输入数据...
  • 选择排序,插入排序,希尔排序,堆排序,快速排序,冒泡排序,性能比较。 对于一个随机的数组,可以知道排序所需的比较次数和移动次数。用c++面向对象构建。
  • 排序基本上属于算法里面必须要...为了方便对比分析,首先先把九大内部排序算法在时间、空间以及稳定性方面的性能总结如下: 九大内部排序 分类 方法 时间复杂度 空间复杂度 稳定性 最好 最坏 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 69,878
精华内容 27,951
关键字:

内部排序算法比较堆排序