精华内容
下载资源
问答
  • 基于指针冒泡排序函数 使用在使用数组排序时,如果我们使用函数,就会面临数据传输的问题:例如其中的交换步骤写成函数,就会存在只在该函数中交换,而无法影响主函数的数值。 如果我们不使用指针,那么要想返回多...

    基于指针的冒泡排序函数

    使用在使用数组排序时,如果我们使用函数,就会面临数据传输的问题:例如其中的交换步骤写成函数,就会存在只在该函数中交换,而无法影响主函数的数值。

    如果我们不使用指针,那么要想返回多个值就只能使用函数返回map、数组或是封装一个实体类。

    例如如下的java实现冒泡排序:

    public class Bubble {
        public static int[] bubbleArray(int[] arr) {
            for (int i = 0; i < arr.length - 1; ++i) {
                for (int j = 0; j < arr.length - i - 1; ++j) {
                    if (arr[j] > arr[j + 1]) {
                        int t[] = swap2(new int[]{arr[j], arr[j + 1]});
                        arr[j] = t[0];
                        arr[j + 1] = t[1];
                    }
                }
            }
            return arr;
        }
    
        public static int[] swap2(int[] arr) {
            arr[0] += arr[1];
            arr[1] = arr[0] - arr[1];
            arr[0] -= arr[1];
            return arr;
        }
    }
    
    class Test {
        public static void main(String[] args) {
            int[] array = Bubble.bubbleArray(new int[]{4, 2, 8, 0, 5, 7, 1, 3, 9});
            for (int i : array) {
                System.out.println(i);
            }
        }
    }
    

    在这个java实现中,使用数组传递各个函数之间的值,bubbleArray()函数负责双循环,swap2()函数负责交换数值。当然在这种情况下不如直接实现数值交换,这里我们为了体现使用指针的方便之处还是使用的函数来交换数值。

    使用指针的C++版本:

    #include<iostream>
    
    using namespace std;
    void swap2(int * p1, int *p2)
    {
        int temp = *p1;
        *p1 = *p2;
        *p2 = temp;
    }
    
    void bubble(int *arr, int len)
    {
        for (int i = 0; i < len - 1; ++i) {
            for (int j = 0; j < len-i-1; ++j) {
                if (arr[j] > arr[j+1]){
                    swap2(&arr[j], &arr[j + 1]);
                }
            }
        }
    }
    
    void priarr( const int *arr, int len)
    {
        for (int i = 0; i < len; ++i) {
            cout << arr[i] << " ";
        }
    }
    
    int main() {
    
        int arr[9] = {4, 2, 8, 0, 5, 7, 1, 3, 9};
    
        int len = sizeof(arr)/sizeof(arr[0]);
        bubble(arr, len);
        priarr(arr, len);
    
        system("pause");
    
        return 0;
    }
    

    使用指针时,我们直接实现数字对应地址的交换,便可以无序数值传递,直接进行内容修改。将函数中的形参改为指针也可以减少内存空间,而且不会复制出新的副本。

    展开全文
  • 排序算法系列:冒泡排序与双向冒泡排序

    万次阅读 多人点赞 2016-01-29 15:25:32
    **排序算法**应该算是一个比较热门的话题,在各个技术博客平台上也都有一些博文进行了一定程度的讲解。...本文就先从最简单的冒泡排序开始说起,别说你已经彻底了解了冒泡排序算法(虽然一开始我也是这样以为的)。

    概述

    排序算法应该算是一个比较热门的话题,在各个技术博客平台上也都有一些博文进行了一定程度的讲解。但还是希望能从自我完善的角度出发,可以更详细、全面、形象地表达这些算法的精髓。本文就先从最简单的冒泡排序开始说起,别说你已经彻底了解了冒泡排序算法(虽然一开始我也是这样以为的)。


    版权说明

    著作权归作者所有。
    商业转载请联系作者获得授权,非商业转载请注明出处。
    本文作者:Q-WHai
    发表日期: 2016年01月29日
    本文链接:https://qwhai.blog.csdn.net/article/details/50591859
    来源:CSDN
    更多内容:分类 >> 算法与数学


    目录

    冒泡排序

    冒泡排序(Bubble Sort)是一种交换排序1,它的基本思想是:两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。
                                           — 《大话数据结构》


    教科书版


    算法原理

    一般来说,我们学习排序算法的入门都是从教科书中获得。而教科书上讲解的内容都是一些相对比较简单的,其目的是为了让人能够很好地去理解它,也可以让人能够很容易地编写出可行的代码。
      教科书版冒泡排序的原理是对数组进行两层循环遍历。让数组中较小的关键字能够较快地移动到数组的顶部,从而当两层循环结束,排序即可完成。


    算法实现

    public void sort(int[] array) {
            int arrayLength = array.length;
            for (int i = 0; i < arrayLength; i++) {
                for (int j = i + 1; j < arrayLength; j++) {
                    if (array[i] > array[j]) {
                        ArrayUtils.swap(array, i, j);
                    }
                }
            }
        }
    

    算法过程图

    通过上面的代码实现,我们可以很容易地画出如下过程图。

    ![这里写图片描述](https://img-blog.csdn.net/20160128105700126) 图-1 冒泡排序-初级版

    复杂度分析

    排序方法时间复杂度空间复杂度稳定性复杂性
    平均情况最坏情况最好情况
    冒泡排序(教科书版)O(n2)O(n2)O(n)O(1)稳定简单

    标准版


    算法原理

    从上面的教科书版的冒泡排序过程图中,我们可以看到教科书版本的冒泡排序并没有很好地体现冒泡的思想。我可没见过有哪个泡泡可以一下子从水的最下面冒到水面的,前面说到的教科书版本的冒泡排序可以理解成最简单的交换排序算法。下面,让我们来见识一下正宗的冒泡排序算法是怎么做的吧。


    算法实现

    private void core(int[] array) {
            
            int arrayLength = array.length;
            
            for (int i = 0; i < arrayLength; i++) {
                for (int j = arrayLength - 2; j >= i; j--) {
                    if (array[j] > array[j + 1]) {
                        ArrayUtils.swap(array, j, j + 1);
                    }
                }
            }
        }
    

    算法过程图

    如果你说这两个算法代码差不多,那就先把代码比对清楚,你会发现不同的地方还是很多的。通过上面的代码实现,我们可以很容易地画出如下过程图。(这次就感觉像是一个小气泡,在一点一点向上冒了。_

    ![这里写图片描述](https://img-blog.csdn.net/20160128110715936) 图-2 冒泡排序-标准版

    复杂度分析

    排序方法时间复杂度空间复杂度稳定性复杂性
    平均情况最坏情况最好情况
    冒泡排序(标准版)O(n2)O(n2)O(n)O(1)稳定简单

    改进版


    优化方案

    通过对上面两种冒泡排序算法的学习,我们可以看到不管是哪一种算法,都不能很好地避免对一个已经有序的数组减少比较操作(只是不用做交换处理)。
      现在,我们想到一种方法,使用一个标志位,来标识当前数组是否已经有序。如果无序,则继续冒泡排序;如果已经有序,则退出排序算法。这样就可以很好地规避掉一些不必要的比较操作。


    算法实现

    private void core(int[] array) {
            
            boolean status = true; // 记录是否发生交换信息
            int arrayLength = array.length;
            
            for (int i = 0; i < arrayLength && status; i++) {
                status = false;
                for (int j = arrayLength - 2; j >= i; j--) {
                    if (array[j] > array[j + 1]) {
                        ArrayUtils.swap(array, j, j + 1);
                        status = true;
                    }
                }
            }
        }
    

    复杂度分析

    排序方法时间复杂度空间复杂度稳定性复杂性
    平均情况最坏情况最好情况
    冒泡排序(改进版)O(n2)O(n2)O(1)O(1)稳定简单

    算法评价

    从冒泡的原理上,我们可以知道,从前向后进行循环遍历交换和从后向前进行循环遍历交换的代价和逻辑是一致的,那么我们也就可以从后向前进行冒泡排序,代码就里就不再给出了。
      在单向冒泡排序算法中,存在着一个著名的“乌龟问题2
      而在排序过程中,又主要是这个过程耗费了大量时间。关于具体的实例在下面的“双向冒泡排序”算法中体现。


    双向冒泡排序


    算法原理

    在基于冒泡排序的基础上,我们知道,无论是从前向后遍历交换,还是从后向前遍历交换,对程序的逻辑和性能的代价都是不影响的,那么我们就可以让一部分情况下从前向后遍历交换,另一部分情况从后向前遍历交换。

    ![双向冒泡排序算法](https://img-blog.csdn.net/20160120101221621) 图-3 双向冒泡排序

    算法步骤

    1. 比较相邻两个元素的大小。如果前一个元素比后一个元素大,则两元素位置交换
    2. 对数组中所有元素的组合进行第1步的比较
    3. 奇数趟时从左向右进行比较和交换
    4. 偶数趟时从右向左进行比较和交换
    5. 当从左端开始遍历的指针与从右端开始遍历的指针相遇时,排序结束

    算法实现

    代码如下:

    private void core(int[] array) {
            int arrayLength = array.length;
            
            int preIndex = 0;
            int backIndex = arrayLength - 1;
            while(preIndex < backIndex) {
                preSort(array, arrayLength, preIndex);
                preIndex++;
                
                if (preIndex >= backIndex) {
                    break;
                }
                
                backSort(array, backIndex);
                backIndex--;
            }
        }
        
        // 从前向后排序
        private void preSort(int[] array, int length, int preIndex) {
            for (int i = preIndex + 1; i < length; i++) {
                if (array[preIndex] > array[i]) {
                    ArrayUtils.swap(array, preIndex, i);
                }
            }
        }
        
        // 从后向前排序
        private void backSort(int[] array, int backIndex) {
            for (int i = backIndex - 1; i >= 0; i--) {
                if (array[i] > array[backIndex]) {
                    ArrayUtils.swap(array, i, backIndex);
                }
            }
        }
    

    复杂度分析

    排序方法时间复杂度空间复杂度稳定性复杂性
    平均情况最坏情况最好情况
    双向冒泡排序O(n2)O(n2)O(n)O(1)稳定简单

    算法评价

    如果单纯从时间复杂度上来讨论,双向冒泡排序与冒泡排序算法复杂度是一致的。不过在双向冒泡排序算法中,我们引入了一些变量,以控制程序流程,在空间复杂度上虽然都O(1),不过双向冒泡排序还是会大一些(至少有多了两个位置指针)。从代码的复杂度上,双向冒泡排序算法会大一些。
      不过在上面的冒泡排序算法中,我们了解到冒泡排序算法有一个“乌龟问题”。正是因为这个原因,我们引入了双向冒泡排序算法。这里我们可通过一个实例更加象形地了解它。
      假设我们现在有一个待排序序列**{6, 5, 4, 3, 2, 1}**。分别使用单向和双向冒泡排序对其进行排序,两种排序算法的过程如下(左图为单向冒泡,右图为双向冒泡):

    步骤单向冒泡排序双向冒泡排序
    原始状态[6, 5, 4, 3, 2, 1][6, 5, 4, 3, 2, 1]
    第 1 趟[1, 6, 5, 4, 3, 2][1, 6, 5, 4, 3, 2]
    第 2 趟[1, 2, 6, 5, 4, 3][1, 5, 4, 3, 2, 6]
    第 3 趟[1, 2, 3, 6, 5, 4][1, 2, 5, 4, 3, 6]
    第 4 趟[1, 2, 3, 4, 6, 5][1, 2, 4, 3, 5, 6]
    第 5 趟[1, 2, 3, 4, 5, 6][1, 2, 3, 4, 5, 6]

    Ref


    GitHub源码链接:


    1. 所谓交换,就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置,交换排序的特点是:将键值较大的记录向序列的尾部移动,键值较小的记录向序列的前部移动。 ↩︎

    2. 乌龟问题说的是:假设我们需要将序列A按照升序序列排序。序列中的较小的数字又大量存在于序列的尾部,这样会让小数字在向前移动得很缓慢。 ↩︎

    展开全文
  • 数组与指针&冒泡排序

    2015-10-21 22:19:48
    数组与指针&冒泡排序 #include static void bubble_sort(int *,int ); int main(int argc,char **argv) { //冒泡排序 int arr[10] = {2,8,5,34,23,1,98,31,76,45}; bubble_sort(arr,10); return 0; } ...

    数组与指针&冒泡排序

    #include <stdio.h>
    
    static void bubble_sort(int *,int );
    
    int
    main(int argc,char **argv)
    {
    	//冒泡排序
    	int arr[10] = {2,8,5,34,23,1,98,31,76,45};
    	bubble_sort(arr,10);
    	return 0;
    }
    
    static void
    bubble_sort(int *arr,int arr_lenght)
    {
    	int i,j;
    	int temp;
    	printf("old arr:");
    	for(i=0;i<arr_lenght;++i)
    	{
    		printf("%d ",*(arr+i));
    	}
    	printf("\n");
    	for(i=0;i<arr_lenght;++i)
    	{
    		for(j=i+1;j<arr_lenght;++j)
    		{
    			if(*(arr+i)<*(arr+j))
    			{
    				temp=*(arr+i);
    				*(arr+i)=*(arr+j);
    				*(arr+j)=temp;
    			}
    		}
    	}
    	printf("new arr:");
    	for(i=0;i<arr_lenght;++i)
    	{
    		printf("%d ",*(arr+i));
    	}
    	printf("\n");
    	return ;
    }


    展开全文
  • 利用这函数的这个功能和函数指针的特点,可以实现对排序函数的排序规则的参数化。 下面是实现思路及代码 通常,排序函数的基本功能是实现数据按关键字递增或递减排序,所以可以封装两个功能函数: //元素增规则 bool...

    函数是通常被封装成处理数据的功能模块,而函数指针使得函数可以在函数之间高效地进行传递。利用这函数的这个功能和函数指针的特点,可以实现对排序函数的排序规则的参数化。

    下面是实现思路及代码

    通常,排序函数的基本功能是实现数据按关键字递增或递减排序,所以可以封装两个功能函数:

    //元素增规则
    bool less_than(int a, int b)
    {
        return (a < b);
    }
    //元素递减规则
    bool greater_than(int a, int b)
    {
        return (a > b);
    }
    

    参数化排序函数的排序规则:

    //冒泡排序用到的思想:比较、区间划分、增量
    void bubble_sort(int *arr, int n, bool (*fp) (int, int))
    {
        int i, j;
        bool exchange;
        for (i = 0; i < n-1; i++)
        {
            exchange = false;
            for (j = n-1; j > i; j--)
                if (fp(*(arr+j), *(arr+j-1)))
                {
                    swap(arr, j, j-1);
                    exchange = true;
                }
            if (!exchange)
                return ;
        }
    }
    

    ps:以上是改进版的排序算法——如果一趟排序后没有进行元素交换,则说明元素已正序,排序结束。

    有了以上的函数定义,就可以在需要元素递增排序时,传less_than函数的指针,在需要元素递减排序时,传greater_than函数的指针,消除了对修改函数源码的琐碎。

    时间复杂度分析:排序趟数与问题规模n有关,而每一趟的比较次数又与无序区的规模有关,很显然平均时间复杂度为 O ( n 2 ) O(n^2) O(n2),exchange的判断功能对函数在某些情况下的性能会有所提高,但一般认为不影响平均时间复杂度

    空间复杂度分析:算法所用的临时变量与问题规模无关,即是一个就地排序算法,所以空间复杂度为 O ( 1 ) O(1) O(1)

    展开全文
  • 冒泡排序 选择排序 折半查找 折半插入 指针的介绍
  • 满意答案ha1419882013.05....改为scanf("%d",ptr);因为ptr本身就是指针,*ptr是内容,不对;scanf函数的第二个参数应该是指针(也可以是地址)2.第一个for循环,就是在scanf的那个循环体完后加上ptr=&num[0];如果...
  • 快速排序&冒泡排序

    2017-11-29 13:14:11
    【图文】1.冒泡排序 2.快速排序 (1)左右指针法 (2)挖坑法 (3)前后指针法 3快速排序优化 (1)小区间优化 (2)三数取中法
  • 09交换排序算法---冒泡排序和快速排序

    千次阅读 多人点赞 2021-08-09 21:28:38
    文章目录一、冒泡排序1.1.时间空间复杂度分析二、快速排序2.1.快排的递归实现2.1.1.挖坑法2.1.2.左右指针法2.1.3.前后指针法2.2.快排的非递归实现2.2.1.挖坑法2.2.2.左右指针法2.2.3.前后指针法2.2.4.用栈实现非递归...
  • 冒泡排序、选择排序、插入排序、快速排序、希尔排序
  • 各位码友身软件开发工程师,算法中的排序可谓是重重之重,那么今天小码哥就给大家带来两种交换排序,简单算法中的冒泡排序,和号称排序算法中的王者快速排序,是不是很期待呀大笑大笑,话不多说,码代码啦!...
  • C语言实现冒泡排序

    2019-07-30 15:44:28
      很久已经没有弄过和...我这边实现了冒泡排序算法,代码如下: void printfArray(int A[],int n){ for (int i = 0; i < n; i++) { printf("%d\n",A[i]); } } void swapA(int A[], int i, int j)...
  • //用指向指针指针的方法对n个整数排序输出 #include<stdio.h> #include<string.h> #define n 10 void sort(int *p) { int **q; int i,j; //int temp[10]; int t; q=&p; for(i=0;i<9;i...
  • 冒泡排序 冒泡排序:BubbleSort

    千次阅读 2009-10-22 08:41:00
    编辑词条 冒泡排序 冒泡排序:BubbleSort 基本概念 冒泡排序的基本概念是:依次比较相邻的两个数,将小数放在前面,大数放在后面。即首先比较第1个和第2个数,将小数放前,大数放后。然后比较第2个数和第3个数,...
  • 冒泡排序与选择排序

    2018-03-19 17:59:22
    介绍冒泡排序与选择排序,以及用不同方法实现冒泡排序与选择排序。
  • 排序算法(一):插入排序、冒泡排序、合并排序、选择排序
  • 冒泡排序的实现

    2016-01-27 13:24:42
    程序名称:冒泡排序算法实现 程序功能: */ #include /* 函数名称:冒泡排序 参数说明: begin是待排序列的起始地址,end是待排序列最后一个元素的下一地址。 即end刚好且已经越界。compare函数指针。指定排序...
  • 冒泡排序是一种交换排序,基本思想是: 两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止 一、初级版 首先是代码和上下界的确定 初级版的思路是: 让每一个关键字,都和它后面的每一个...
  • #include using namespace std;...//别问我什么要写链表的冒泡排序。 struct Node { int data; Node *next; Node(int d = int()) :data(d), next(NULL){} }; class List { public: List(int a[], int n)
  • *************************** // 函数名称:mp_sort_xd// 函数功能:使用冒泡方法对数据进行排序--使用指针的操作 // 入口参数:排序数据的首地址 数据长度// 出口参数:无 // 返 回 值:无 //*********************...
  • 简单排序算法(冒泡排序、选择排序、插入排序) 一、冒泡排序 1、介绍:  冒泡排序和选择排序的思想是蛮力法,冒泡,顾名思义,每次选择后面一个元素(最大或者最小)冒上来,从而得到一个有序的序列。比如对于序列...
  • MIPS实现冒泡排序

    千次阅读 2017-09-02 15:46:27
    编程的入门级知识:循环、冒泡排序、内存和堆栈的概念 MIPS语法:程序基本结构 汇编语言:不同寄存器作用、数据存储、系统调用 编辑器:最低级的记事本就够了,保存.asm文件即可 PCSpim模拟器:用于运行代码 MIPS...
  • 一、冒泡排序 二、快速排序 三、小结 一、冒泡排序 冒泡排序是各种教材中 经常提到的一种排序 方法,基本思想就是: ① 从数组的头部开始,比较相邻两个数,如果第1个数比第2个数大,就交换他们两个。也就是...
  • 交换排序(冒泡排序+快速排序)、归并排序、基数排序、拓扑排序 二维数组指针指针数组
  • 双向循环链表的冒泡排序

    千次阅读 2017-11-28 21:15:58
    以内核链表例,进行冒泡排序
  • 详解单链表冒泡排序

    2020-05-11 23:36:49
    C语言,对单链表进行冒泡排序
  • 冒泡排序2种算法

    2017-03-21 23:16:34
    /***************************************************************************** FileName : sort.c Function : C语言冒泡排序 Author : mike Email : hxtiou@163.com Version : V1.0 Date : 2019-07-12...
  • MIPS汇编:冒泡排序

    万次阅读 多人点赞 2017-04-01 14:13:35
    推荐入门教程:【十分钟教会你汇编】MIPS编程入门我是先写出C++冒泡排序的代码,然后再将之手动转为汇编代码。以下是冒泡排序的汇编代码:################################################ # # include # using ...
  • 使用冒泡排序作为排序核心,模仿Qsort函数,对不同类型数组进行排序。
  • 初识冒泡排序 排序算法常常作为学习算法的入门实践,而冒泡排序又是其中最简单的一种,我们今天的主题就是冒泡排序。它的基本思想就像鱼吐泡泡一样简单。 想象有一条鱼在数组的最底端,每一轮,它就吐个泡泡,泡泡会...
  • 什么会叫做冒泡排序呢?这是由于它的算法思想就类似于鱼儿在河里吐泡泡的场景,例如升序排列一列数,它会两两相邻的数据进行比较,如果前者大于后者就交换,重复此番工作直到交换到最后两个数据,第一趟冒泡排序...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 18,343
精华内容 7,337
关键字:

把冒泡排序改为指针