精华内容
下载资源
问答
  • 数据结构起泡排序

    2020-03-14 17:27:21
    数据结构算法写在前面起泡排序算法粗暴版提前终止版提前终止加强版 写在前面 看了b站上清华老师邓俊辉邓老师的视频,把代码写下来自己记录记录,方便记忆和理解。 起泡排序算法 粗暴版 起泡排序是个很简单也很容易...

    写在前面

    看了b站上清华老师邓俊辉邓老师的视频,把代码写下来自己记录记录,方便记忆和理解。

    起泡排序算法

    bubbleSort.1

    这是个很简单也很容易理解的起泡排序算法。
    算法开始逐行扫描,每次能找到最大者然后放在最后。因此需要的扫描的次数逐行递减,最后排序完成。
    代码如下

    void bubblesort ( int A[], int n ) { //起泡排序算法(版本0):0 <= n
        while ( n-- ) { //在尚未确认已全局排序之前,逐趟进行扫描交换
           for ( int i = 0; i < n; i++ ) { //自左向右逐对检查当前范围A[0, n)内的各相邻元素
              if ( A[i] > A[i+1] ) { //一旦A[i]与A[i+1]逆序,则
                 swap ( A[i], A[i+1] ); //交换之,并
              }
           }
        }
     } //蛮力算法,不能及时提前退出,总是必须做n-1趟扫描交换
    

    算法的正确性:
    1.经过k趟扫描交换后,最大的k个元素必然就位。
    2.经过k趟扫描后,问题规模缩减至n-k。
    3.至多经过n-1趟,算法必然终止,且给出正确答案。
    4.时间效率在最好最坏情况下都是O(n^2)

    显然,我们有更好的策略改进这个算法。
    可能出现这种情况,当机器经过某次扫描后可能剩下的都是有序的,这个时候我们就想可不可以提前终止这个算法,显然,是可以的。

    bubbleSort.2

    while版本

    void bubblesort1A ( int A[], int n ) { //起泡排序算法(版本1A):0 <= n
        bool sorted = false; //整体排序标志,首先假定尚未排序
        while ( !sorted ) { //在尚未确认已全局排序之前,逐趟进行扫描交换
           sorted = true; //假定已经排序
           for ( int i = 1; i < n; i++ ) { //自左向右逐对检查当前范围A[0, n)内的各相邻元素
              if ( A[i - 1] > A[i] ) { //一旦A[i - 1]与A[i]逆序,则
                 swap ( A[i - 1], A[i] ); //交换之,并
                 sorted = false; //因整体排序不能保证,需要清除排序标志
              }
           }
           n--; //至此末元素必然就位,故可以缩短待排序序列的有效长度
        }
     } //
    

    for循环版本

    void bubbleSort(int A[],int n){
    	for(bool sorted=false;sorted=!sorted;n--){
    		for(int i=0;i<n-1;i++){
    			if(A[i]>A[i+1]){
    				swap(A[i],A[i+1]);
    				sorted=false;
    			}
    		}
    	}
    }
    

    注意while和for版本的区别,在while版本中,我们的i起始位置是1,for版本起始位置是0;
    我们可能经常是让i从0开始(例如上面的bubbleSort.1),所以要注意两者之间的区别。
    当i从0开始时,我们需要在i<n-1时跳出内层循环,不然可能会造成A[n-1]和A[n]比较并交换数据,造成结果错误;当i从1时,我们则需进行A[i-1]和A[i]的比较,在i<n时跳出内层循环。

    在bubbleSort.2中我们借助布尔型标志位sorted,可及时提前退出,而不致总是蛮力地做n - 1趟扫描交换。不过,如果我们在完成某次扫描就位后,可能会发现这种情况:
    在这里插入图片描述
    在这里发现hi前面的一段元素是就位好了的,我们就发现可以让遍历次数大幅度的减小,让n=last,
    这样就可以减少我们扫描时比较的次数。于是,有了下面的版本。

    bubbleSort.3

    void bubbleSort(int A[],int n){
    	for(int m;1<n;n=m){//在尚未确认已全局排序之前,逐趟进行扫描交换
    		for(int i=m=0;i<n-1;i++){ //自左向右逐对检查当前范围A[0, m)内的各相邻元素
    			if(A[i]>A[i+1]){//一旦A[i-1]与A[i]逆序,则
    				swap(A[i],A[i+1]);//交换之,并
    				m=i+1;//更新待排序区间的长度
    			}
    		}
    	}
    } 
    

    我们让m=i+1,也就是此趟扫描最后交换元素的秩,直接让n=m,就能跳过Last到hi之间排序正确的元素,省略了在bubbleSort.2版本中下一趟需要比较的次数。
    特点:
    **1.对尾部有序(或接近有序)的输入,算法收敛的速度大大提高
    2.元素交换的次数仅取决于输入序列
    分析:
    该算法在输入数据都是顺序时时间效率最好,为O(n),即为算遍历比较一遍然后退出。
    输入数据是逆序排列时时间效率最坏,为O(n^2),即为每次都就位最大的元素,重复n-1次。
    同时,该算法也是稳定的。**如下图所示:稳定性
    在上图中,有三个值相同但下标有序的数,当我们排序为7a,7b,7c时,我们认为它是稳定的。
    显然,bubbleSort算法的三个版本都是稳定的,因为只有前一个元素严格大于后一个元素(A[i]>A[i+1])时,我们才执行swap语句。

    写在后面

    排序算法有很多种,选择排序、归并排序以及还可能学习的堆排序、快速排序。
    不过,起泡排序就值得我们多多练习,多多思考。

    展开全文
  • 初次基于向量实现起泡排序与归并排序,以为有所得,故记录下来。 2 整体程序 #include <iostream> #include <vector> using namespace std; bool bubble( int* A, int lo, int hi); void bubbleSort( ...

    1 绪论

    初次基于向量实现起泡排序与归并排序,以为有所得,故记录下来。

    2 整体程序

    #include <iostream>
    #include <vector>
    using namespace std;
    
    bool bubble( int* A, int lo, int hi);
    void bubbleSort( int* A, int lo, int hi);
    void mergeSort ( int *A, int lo, int hi);
    void merge( int *&A, int lo, int mi, int hi );
    
    int main()
    {
        int A[] = { 4, 5, 3, 7, 12, 13, 0, 15};
        int size = sizeof(A)/sizeof(A[0]);
        int (&AA)[8] = A; //数组的引用
        //bubbleSort(A, 0, 7); 
        mergeSort (AA, 0, size);
    
        //输出排序结果
        for (int i = 0; i < size - 1;i++){
            cout << A[i] << ", ";
        }
        cout << A[size - 1] <<endl;
    
       
    }
            
    //起泡排序
    void bubbleSort( int* A, int lo, int hi){
        while ( !bubble (A, lo, hi--));
    }
    
    bool bubble( int* A, int lo, int hi){
        bool sorted = true; //整体有序标志
        while (++lo < hi){
            if (A[lo - 1] > A[lo]){
                sorted = false;
                swap (A[lo -1 ], A[lo]);
            }
        }
        return sorted;
    }
    
    
    //归并排序
    void mergeSort (int *A, int lo, int hi){
        if (hi - lo < 2) return;
        int mi = (lo + hi) / 2;
        mergeSort ( A, lo, mi); 
        //展示递归的过程(1)
        for (int i = lo; i < mi ;i++){
            cout << A[i] << ", ";
        }
        cout << "end0" << endl;
    
        mergeSort(A, mi, hi);
        //展示递归的过程(2)
        for (int i = mi; i < hi ;i++){
            cout << A[i] << ", ";
        }
        cout << "end1" << endl;
    
        merge(A, lo, mi, hi); //归并
    
    }
    
    void merge(int *&A, int lo, int mi, int hi ){//各自有序的向量[lo,mi)和[mi,hi)
        int* A1 = A + lo;              
        int lb = mi - lo;
        int* B1 = new int[lb];//前子向量B1[0,lb) = A[lo,mi)
        for ( int i = 0; i < lb; i++) B1[i] = A1[i];  //不能写成for ( int i = 0; i < lb; B1[i] = A1 [i++])
        int lc = hi - mi; int* C1 = A + mi;//后子向量C1[0, lc) = A[mi, hi)        
        for ( int i = 0, j = 0, k = 0; (j < lb)||(k < lc);){
            if((j < lb )&&(!(k < lc)||( B1[j] <= C1[k]))) A1[i++] = B1[j++];
            if((k < lc )&&(!(j < lb)||( C1[k] < B1[j]))) A1[i++] = C1[k++];
        }
        delete [] B1;
    }
    
    
    
    

    3 起泡排序

    • 作为最简单的排序方式之一,起泡排序采用减而治之的策略。每一个轮回之后,最大的值都会回到最末端,以此可以不断减小问题的规模。
    //起泡排序
    void bubbleSort( int* A, int lo, int hi){
        while ( !bubble (A, lo, hi--));
    }
    
    bool bubble( int* A, int lo, int hi){
        bool sorted = true; //整体有序标志
        while (++lo < hi){
            if (A[lo - 1] > A[lo]){
                sorted = false;
                swap (A[lo -1 ], A[lo]);
            }
        }
        return sorted;
    }
    

    4 归并排序

    • 归并排序的思想朴素而深沉,分而合之,正如“将欲取之,必须与之”,化整为零,然后可以成你所想
    //归并排序
    void mergeSort (int *A, int lo, int hi){
        if (hi - lo < 2) return;
        int mi = (lo + hi) / 2;
        mergeSort ( A, lo, mi); 
        //展示递归的过程(1)
        for (int i = lo; i < mi ;i++){
            cout << A[i] << ", ";
        }
        cout << "end0" << endl;
    
        mergeSort(A, mi, hi);
        //展示递归的过程(2)
        for (int i = mi; i < hi ;i++){
            cout << A[i] << ", ";
        }
        cout << "end1" << endl;
    
        merge(A, lo, mi, hi); //归并
    
    }
    
    void merge(int *&A, int lo, int mi, int hi ){//各自有序的向量[lo,mi)和[mi,hi)
        int* A1 = A + lo;              
        int lb = mi - lo;
        int* B1 = new int[lb];//前子向量B1[0,lb) = A[lo,mi)
        for ( int i = 0; i < lb; i++) B1[i] = A1[i];  //不能写成for ( int i = 0; i < lb; B1[i] = A1 [i++])
        int lc = hi - mi; int* C1 = A + mi;//后子向量C1[0, lc) = A[mi, hi)        
        for ( int i = 0, j = 0, k = 0; (j < lb)||(k < lc);){
            if((j < lb )&&(!(k < lc)||( B1[j] <= C1[k]))) A1[i++] = B1[j++];
            if((k < lc )&&(!(j < lb)||( C1[k] < B1[j]))) A1[i++] = C1[k++];
        }
        delete [] B1;
    }
    
    • 下面是该程序运行出的结果,通过展示递归过程,可以帮助对归并的理解
      4, end0
      5, end1
      4, 5, end0
      3, end0
      7, end1
      3, 7, end1
      3, 4, 5, 7, end0
      12, end0
      13, end1
      12, 13, end0
      0, end0
      15, end1
      0, 15, end1
      0, 12, 13, 15, end1
      0, 3, 4, 5, 7, 12, 13, 15

    5 总结

    归并排序借鉴了邓俊辉老师的代码,没有用其中的模板。遇到了总是输出出错的问题。自己化整为零地分析一行行代码,来分析整个代码逻辑,最终终于找到了有问题的语句。通过这个过程,我对于归并的思想理解得更加深刻。

    展开全文
  • 冒泡算法:是排序算法中的基本算法,基本概念就是逐个比较大小,由开始到末尾逐次比较,比较一次确定一个数的位置,例如数组元素个数n,则比较(n-1)+(n-2)+…+1次。 demon: #include<stdio.h> void ...

    冒泡算法:是排序算法中的基本算法,基本概念就是逐个比较大小,由开始到末尾逐次比较,比较一次确定一个数的位置,例如数组元素个数n,则比较(n-1)+(n-2)+…+1次。

    demon:

    #include<stdio.h>
    
    void bubble_sort(int *arry,int n)
    {
    	int tmp,i,j;
    	for(i=0;i<n-1;i++)
    		for(j=0;j<n-i-1;j++)
    			if(arry[j]>arry[j+1])
    			{
    				tmp=arry[j];
    				arry[j]=arry[j+1];
    				arry[j+1]=tmp;
    			}
    }
    
    int main()
    {
    	int i;
    	int arry[10]={10,8,1,3,6,7,4,2,9,5};
    	int n=sizeof(arry)/sizeof(arry[0]);
    	bubble_sort(arry,n);
    	printf("排序后数组为:");
    	for(i=0;i<n;i++)
    	{
    		printf("%d ",arry[i]);
    	}
    	printf("\n");
    	return 0;
    }
    
    

    运行结果:
    在这里插入图片描述

    展开全文
  • A选项起泡算法:相邻元素两两比较,一个元素大于右侧相邻元素交换位置,否则位置不变。 一趟排序为:46,56,38,40,79,84 B选项直接插入:每一步将一个待排序的记录,插入到前面已经排好序的有序序列中去,直到...

    文章目录

    叶子节点数=度为2的节点数+1
    总叶子节点数=叶子节点数+度为1的节点数+度为2的节点数

    排序

    栗子:

    一组记录的排序码为(46,79,56,38,40,84),一趟排序的结果为(40,38,46,56,79,84),则采用的是()排序算法。

    • A选项起泡算法:相邻元素两两比较,一个元素大于右侧相邻元素交换位置,否则位置不变。 一趟排序为:46,56,38,40,79,84

    • B选项直接插入:每一步将一个待排序的记录,插入到前面已经排好序的有序序列中去,直到插完所有元素为止。
      一趟排序为:38,40,46,79,56,84

    找到一个最小的放最前面,其他不变

    • C选项快速:挑选一个基准元素,大于基准元素的放在其右边,小于基准元素的放在其左边,从而拆分为两部分,以此类推直到不可拆分为止。
      以源数据第一个元素46为基准,采用双边循环法设置left和right两个指针指向数组最左和最右两端,从右指针开始,如果大于或等于基准元素则指针向左移动,如果小于基准元素则停止。转向left指针向右移动如果小于或等于基准元素则继续向右移动,如果大于基准元素则停止。交换两指针元素后,右指针继续上述操作比较,直到最后把基准元素和两指针重复元素交换位置。第一趟排序结束得出如下排序,所以C正确。
      一趟排序为:40,38,46,56,79,84
    • D选项2-路归并:将一个数组分成两个数组,分别对两个数组进行排序,循环第一步,直到划分出来的“小数组”只包含一个元素,只有一个元素的数组默认为已经排好序
      一趟排序为:46,56,79合并;38,40,84合并
      栗子:
      在这里插入图片描述
      p^.llink 表示 p 的前驱结点,p^.rlink表示 p 的后继结点。删除 p 所指结点时须将 p 的前驱结点的rlink指向 p 的后继结点,将 p 的后继结点的 llink 指向 p 的前驱结点。
    展开全文
  • 冒泡算法 这里是按照从小到大排序,从大到小排序原理相同,判断不同。 原理: 依次比较相邻两个元素大小,大的放在右边,小的放在左边。 思路: 第一次排序:比较第一个元素和第二个的大小,小的放在左边,大的放在...
  • 常用数据结构与常用算法

    万次阅读 多人点赞 2018-08-08 20:32:54
    1. 常见数据结构 人们进行程序设计时通常关注两个重要问题,一是如何将待处理的数据存储到计算机内存中,即数据表示;...可以看出数据结构算法是程序的两个重要组成部分,数据结构是指数据的逻辑结构和存储方法...
  • 如何分析排序算法(时间复杂度、空间复杂度、稳定性) 1、排序算法的执行效率 最好情况,最坏情况,平均情况时间复杂度(有序和无序的数据,对时间复杂度有影响) 冒泡排序最好情况数据已经有序,时间复杂度为O(n)...
  • C语言实现冒泡排序算法 1.基本思想:        从小到大的冒泡排序是每次从头开始,两两比较,将较大的数放在两个数中的后面一位,循环此过程,将最大的数放在最后的位置;接着再...
  • 数据结构常见的八大排序算法之冒泡排序
  • 北京工业大学,电控学院,《数据结构算法》。本资源是北工大电控学院大一下学期课程《数据结构算法》的课程作业。 本资源为数据结构算法第三章(排序)的作业程序代码。包含以下的两个程序: 3.4 rk作哨兵直接...
  • 数据结构算法实验报告 需求分析 问题描述在教科书中各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶或大概执行时间试通过随机数据比较各算法的关键字比较次数和关键字移动次数以取得直观感受 基本...
  • 摘录《数据结构算法与应用》中对冒泡排序的描述,及时间复杂度分析 我的C++实现: #include <iostream> using namespace std; // 单次冒泡:比较数组a[]的前n个数,从左到右两两比较,将最大值移...
  • 起泡排序 https://www.bilibili.com/video/av49361421?p=75 初始版本时间复杂度O(n^2)。 改进:考虑到向量中的前段和后段是不是已经是有序的。前段有的话就不再继续排序,后段有的话就把hi点放到前段最大值那里。 ...
  • 1、数据结构算法 1.1、算法特性 正确性 健壮性 可理解性 抽象分级 高效性(时间复杂度,空间复杂度) 1.2、算法的描述方法 自然语言 流程图 结构化流程图 N-S图 伪代码 计算机语言 1.3、查找问题的经典算法 ...
  • 排序算法太多了,有很多可能你连名字都没听说过,比如猴子排序、睡眠排序、面条排序等。我只讲众多排序算法中的一小撮,也是最经典的、最常用的:冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数...
  • 虽然之前上了一些关于数据结构算法之类的课,但之前都没有怎么搞懂,尤其是算法里面的一些算法思想,现在看能不能补上,就是一些大佬的算法指导,刷LeetCode的一些题,回看之前的书上面的重点。 教材是清华大学...
  • 另外,冒泡排序算法的结束条件是一趟排序中没有进行过交换。 三、代码实现 : public int[] sortArray(int[] nums) { int N=nums.length,temp;// boolean M=false;//交换判别 for(int i=N-1;i>0&&!M;i--){ M=true; ...
  • 数据结构跳跃式起泡算法 如下: n为数组规模,代码可以灵活更改 void bubblesort1(int R[], int n) { int lo=0,last=n,t=0; while (last>0) { for (int i = 0; i < n-1; i++) { if (R[i] > R[i + 1]) {...
  • 数据结构算法冒泡排序

    千次阅读 2018-08-08 15:21:17
    证明这个算法严格来说并不是冒泡算法。 接下来,这个算法的时间复杂度:(大O记法) 最好时间复杂度: 数组本来就是有序的,只需要比较n-1次,则最好时间复杂度:O(n); 最坏时间复杂度: n+n-1+…+1—->根据数列求和...
  • 数据结构所有排序算法性能分析与比较 通过对数据结构的学习,我发现数据结构中各种排序算法的排序方法,过程,以及时间性能,空间性能都比较容易混淆,现就这些情况做如下总结,希望对大家有所帮助。 起泡排序...
  • 数据结构和常用算法

    万次阅读 多人点赞 2015-10-02 14:04:00
    1. 常见数据结构 人们进行程序设计时通常关注两个重要问题,一是如何将待处理的数据存储到计算机内存中,即数据表示;...可以看出数据结构算法是程序的两个重要组成部分,数据结构是指数据的逻辑结构和存储方法
  • 引言:我们的数据结构已经学习完基本的知识,但是光有数据结构是不可以的,现在我们将目光放在接下来的内容,基础算法部分。现在我们就开始第一部分的学习——排序算法 排序一.排序简介二.桶排序1.定义2.代码原理3....
  • void BubbleSort(int A[],int n) {  int i,j;  int flag;  int temp;  for(i=n-1,flag=1;i>0 && flag; i--)  {  flag = 0;  for(j=0;j  if(A[j+1]  {  flag = 1;  temp = A[j+1];... 
  • 接下来计算其复杂度 时间复杂度:1+2+ … + n-1 =n(n-1)/2= O( n^2) 封底估算 除了使用大O记号对算法进行定性分析,有时候还需要对算法进行粗略的定量分析,这时可以使用封底估算。下面列出一些我们常见的一些时间...
  • 利用随机函数产生30000个随机整数,利用插入排序、起泡排序、选择排序、快速排序、堆排序、归并排序等排序方法进行排序,并统计每一种排序上机所花费的时间。提示:用顺序存储结构
  • 数据结构排序算法综合运用及比较(C语言实现)

    千次阅读 多人点赞 2020-04-29 20:30:09
    排序算法综合及效率比较 实验目的 实验内容 ...培养综合运用所学知识,根据具体问题进行数据结构设计和算法设计的能力。 (2)熟练掌握简单的演示菜单与人机交互设计方法。 2.实验内容 (1)用r...
  • 目录 一、各排序算法的时间复杂度与空间复杂度比较 二、直接插入排序 1、算法思想 2、代码实现 3、输出结果 4、时间复杂度与空间复杂度...1、算法思想 ...四、起泡排序 1、算法思想 2、代码实现 3、输出结果 ...
  • 起泡排序算法_气泡排序算法

    千次阅读 2020-07-28 18:04:57
    起泡排序算法 气泡排序算法 (Bubble Sort Algorithm) Bubble Sort is a simple algorithm which is used to sort a given set of n elements provided in form of an array with n number of elements. Bubble Sort...
  • 算法就是一系列的计算步骤,用来将输入数据转换成输出数据。 书中有一句话非常好: Having a solid base of algorithm knowledge and technique is one characteristic that separates the truly skilled ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,142
精华内容 856
关键字:

数据结构起泡算法

数据结构 订阅