首页 / 算法 / 《数据结构》--内部排序算法比较

《数据结构》--内部排序算法比较

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了《数据结构》--内部排序算法比较，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含8499字，纯文字阅读大概需要13分钟。

内容图文

题目：
各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。
基本要求：
（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;
}

支持一下吧！

内容总结

以上是互联网集市为您收集整理的《数据结构》--内部排序算法比较全部内容，希望文章能够帮你解决《数据结构》--内部排序算法比较所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/629014.html

来源：【匿名】

【上一篇】【数据结构与算法】数组与矩阵经典题【下一篇】浅谈php实现映射的两种方法（链表和二叉树）

更多 ►

【《数据结构》--内部排序算法比较】教程文章相关的互联网学习教程文章

数据结构：二算法

1. 定义算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作 2. 五个基本特性输入和输出算法具有零个或多个输入算法至少有一个或多个输出有穷性指算法在执行有限的步骤后，自动结束而不会出现循环，并且每一个步骤在可接受的时间内完成实际应用中合理的，可以接受的“有边界”确定性算法的每一步骤都具有确定的含义，不会出现二义性算法在一定条件下，只有一条执行路径，相同的输入...

浅谈算法和数据结构: 六符号表及其基本实现【代码】【图】

前面几篇文章介绍了基本的排序算法，排序通常是查找的前奏操作。从本文开始介绍基本的查找算法。在介绍查找算法，首先需要了解符号表这一抽象数据结构，本文首先介绍了什么是符号表，以及这一抽象数据结构的的API，然后介绍了两种简单的符号表的实现方式。一符号表在开始介绍查找算法之前，我们需要定义一个名为符号表（Symbol Table）的抽象数据结构，该数据结构类似我们再C#中使用的Dictionary，他是对具有键值对元素的一种抽象，...

数据结构和算法绪论（一）【图】

1、什么是数据结构？程序设计=数据结构+算法物理结构+逻辑结构=数据结构一、4大逻辑结构：集合结构，线性结构，树形结构，图形结构，二、物理结构顺序存储结构，链式存储结构，（指针也需要存储空间）原文：https://www.cnblogs.com/zhzJAVA11/p/9896616.html

MySQL索引背后的数据结构及算法原理

摘要本文以MySQL数据库为研究对象，讨论与数据库索引相关的一些话题。特别需要说明的是，MySQL支持诸多存储引擎，而各种存储引擎对索引的支持也各不相同，因此MySQL数据库支持多种索引类型，如BTree索引，哈希索引，全文索引等等。为了避免混乱，本文将只关注于BTree索引，因为这是平常使用MySQL时主要打交道的索引，至于哈希索引和全文索引本文暂不讨论。文章主要内容分为三个部分。第一部分主要从数据结构及算法理论层面讨论M...

数据结构算法【代码】【图】

#include<iostream> usingnamespace std;/* 算法算法概念算法是特定问题求解步骤的描述在计算机中表现为指令的有限序列算法是独立存在的一种解决问题的方法和思想。对于算法而言，语言并不重要，重要的是思想。算法和数据结构区别数据结构只是静态的描述了数据元素之间的关系高效的程序需要在数据结构的基础上设计和选择算法程序=数据结构+算法总结：算法是为了解决实际问题而设计的数据结构是算法需要处理的问题载体数据...

【数据结构】算法 Binary Tree Zigzag Level Order Traversal 二叉树的锯齿形层序遍历【代码】【图】

目录Binary Tree Zigzag Level Order Traversal 二叉树的锯齿形层序遍历TagBinary Tree Zigzag Level Order Traversal 二叉树的锯齿形层序遍历给一个二叉树的root，返回其节点值从上到下遍历，奇数层从左到右遍历，偶数层从右到左。Input: root = [3,9,20,null,null,15,7] Output: [[3],[20,9],[15,7]] /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right...

数据结构和算法【代码】

找出那个特殊的字母给定两个字符串s和t，它们只包含小写字母。字符串t由字符串s随机重排，然后在随机位置添加一个字母。请找出在t中被添加的字母。示例如果字符串s = "abcd";，t = "abdec";，则输出为e。方法一：使用异或运算求和char FindTheDiffAlp(const std::string s, const std::string t) {const std::string st = s + t;char c = 0;for (std::size_t i = 0; i < st.size(); ++i) {c ^= st.at(i);}return c; }方法二：分别...

Java数据结构和算法（十二）——2-3-4树【代码】【图】

通过前面的介绍，我们知道在二叉树中，每个节点只有一个数据项，最多有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点，就是多叉树。本篇博客我们将介绍的——2-3-4树，它是一种多叉树，它的每个节点最多有四个子节点和三个数据项。1、2-3-4 树介绍　　2-3-4树每个节点最多有四个字节点和三个数据项，名字中 2,3,4 的数字含义是指一个节点可能含有的子节点的个数。对于非叶节点有三种可能的情况：　　①、有一个数...

《常见算法与数据结构》符号表ST（3）——二叉查找树（附动画）【代码】【图】

符号表（3）——二叉查找树本系列文章主要介绍常用的算法和数据结构的知识，记录的是《Algorithms I/II》课程的内容，采用的是“算法（第4版）”这本红宝书作为学习教材的，语言是java。这本书的名气我不用多说吧？豆瓣评分9.4，我自己也认为是极好的学习算法的书籍。通过这系列文章，可以加深对数据结构和基本算法的理解（个人认为比学校讲的清晰多了），并加深对java的理解。符号表3二叉查找树二叉查找树1 代码框架2 节点表示3 取...

第4章数据结构算法【代码】

py内置数据结构算法常考常用内置的算法和数据结构sorted list/set/dict/tuple常用内置数据结构和算法数据结构/算法语言内置内置库线性结构list(列表)/tuple(元组)array(数组, 不常用)/collections.namedtuple链式结构collections.deque(双端队列)字典结构dict(集合)collections.Counte(计数器)/OrderedDict(有序字典)集合结构set(集合)/frozenset(不可变集合)排序算法sorted二分算法bisect模块堆算法heapq模块缓存算法functools.lr...

数据结构 - 相关标签

数据结构导论数据结构是什么数据结构习题数据结构严蔚敏数据结构与算法分析

算法 - 最热教程

浅谈SQLServer查询优化器中的JOIN算法有没那种可逆算法是密文比明文短的呢？...javascript-类似Excel里面的NORMDIST函...C++中的分治算法及常见题目汇总压缩感知重构算法综述-学习笔记 c++中内置函数qsort（快速排序）和bsea...一、fpga图像处理算法整合基于遗传算法（deap）的非线性函数寻优...集成学习-Bagging集成学习算法随机森林...机器学习笔记（九）聚类算法及实践（K-...

首页 / 算法 / 《数据结构》--内部排序算法比较

《数据结构》--内部排序算法比较

内容导读

内容图文

内容总结

内容备注

内容手机端

【《数据结构》--内部排序算法比较】教程文章相关的互联网学习教程文章

数据结构：二算法

浅谈算法和数据结构: 六符号表及其基本实现【代码】【图】

数据结构和算法绪论（一）【图】

MySQL索引背后的数据结构及算法原理

数据结构算法【代码】【图】

【数据结构】算法 Binary Tree Zigzag Level Order Traversal 二叉树的锯齿形层序遍历【代码】【图】

数据结构和算法【代码】

Java数据结构和算法（十二）——2-3-4树【代码】【图】

《常见算法与数据结构》符号表ST（3）——二叉查找树（附动画）【代码】【图】

第4章数据结构算法【代码】

Java数据结构和算法之栈与队列【图】

数据结构和算法_队列

【uva 1471】Defense Lines（算法效率--使用数据结构）

数据结构和算法————二分查找【代码】

数据结构与算法-数据结构和算法概述、评判程序优劣、数据结构【代码】

数据结构 - 相关标签

算法 - 相关标签

算法 - 最新教程

算法 - 最热教程