精华内容
下载资源
问答
  • 冒泡排序的for循环

    千次阅读 2018-05-23 16:45:40
    最近打算找找实习岗位,当然算法这样的基本功可不能松懈,首先上手就是人尽皆知的冒泡算法,看了好多的冒泡算法感觉每人写的for循环都不一样(当然中心思想还是一样的), 清楚算法思想固然重要,但是搞清楚for循...

    最近打算找找实习岗位,当然算法这样的基本功可不能松懈,首先上手就是人尽皆知的冒泡算法,看了好多的冒泡算法感觉每个人写的for循环都不一样(当然中心思想还是一样的), 清楚算法思想固然重要,但是搞清楚for循坏同时也是十分必要的,所以查看了网上的资源之后再次总结几种for循坏的方式,方便以后自己查看学习:

    第一种:

     for(i=0;i<n;i++){
            for(j=0;j<n-i-1;j++)
                    //j和j+1项比较
        } 

    第二种:

    for(i=1;i<n;i++){
            for(j=0;j<n-i;j++)
                    //j和j+1项比较
        } 

    第三种:

    for (int i = 1; i < n; i++)   {  
         for (int j = n - 1; j >= i; j--)  
            //  j-1和j项比较 
        }  

    展开全文
  • 冒泡排序的双重循环理解

    千次阅读 2019-10-06 21:06:25
    冒泡排序的双重循环理解 ...

    冒泡排序的双重循环理解

    主要说一下冒泡排序的一些关键地方的个人理解,比如算法思想,两个循环的作用意义,中间循环变量范围的确定等。

    原理:比较两个相邻的元素,将值大的元素交换至右端。
    

    思路:依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后。重复第一趟步骤,直至全部排序完成。
    第一趟比较完成后,最后一个数一定是数组中最大的一个数,所以第二趟比较的时候最后一个数不参与比较;

    第二趟比较完成后,倒数第二个数也一定是数组中第二大的数,所以第三趟比较的时候最后两个数不参与比较;

    依次类推,每一趟比较次数-1;
    ……

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    举例说明:要排序数组:int[] arr={6,3,8,2,9,1};

    第一趟排序:

    第一次排序:6和3比较,6大于3,交换位置: 3 6 8 2 9 1

    第二次排序:6和8比较,6小于8,不交换位置:3 6 8 2 9 1

    第三次排序:8和2比较,8大于2,交换位置: 3 6 2 8 9 1

    第四次排序:8和9比较,8小于9,不交换位置:3 6 2 8 9 1

    第五次排序:9和1比较:9大于1,交换位置: 3 6 2 8 1 9

    第一趟总共进行了5次比较, 排序结果: 3 6 2 8 1 9


    第二趟排序:

    第一次排序:3和6比较,3小于6,不交换位置:3 6 2 8 1 9

    第二次排序:6和2比较,6大于2,交换位置: 3 2 6 8 1 9

    第三次排序:6和8比较,6大于8,不交换位置:3 2 6 8 1 9

    第四次排序:8和1比较,8大于1,交换位置: 3 2 6 1 8 9

    第二趟总共进行了4次比较, 排序结果: 3 2 6 1 8 9


    第三趟排序:

    第一次排序:3和2比较,3大于2,交换位置: 2 3 6 1 8 9

    第二次排序:3和6比较,3小于6,不交换位置:2 3 6 1 8 9

    第三次排序:6和1比较,6大于1,交换位置: 2 3 1 6 8 9

    第二趟总共进行了3次比较, 排序结果: 2 3 1 6 8 9


    第四趟排序:

    第一次排序:2和3比较,2小于3,不交换位置:2 3 1 6 8 9

    第二次排序:3和1比较,3大于1,交换位置: 2 1 3 6 8 9

    第二趟总共进行了2次比较, 排序结果: 2 1 3 6 8 9


    第五趟排序:

    第一次排序:2和1比较,2大于1,交换位置: 1 2 3 6 8 9

    第二趟总共进行了1次比较, 排序结果: 1 2 3 6 8 9


    最终结果:1 2 3 6 8 9


    由此可见:N个数字要排序完成,总共进行N-1趟排序,每i趟的排序次数为(N-i)次,所以可以用双重循环语句,外层控制循环多少趟,内层控制每一趟的循环次数,即

    for(i=0;i<n-1;i++)

    for(j=0;j<n-i-1;j++) //n是数组长度,即元素个数

    外层循环的作用是:

    提取出目前未排序数组中最大的数,放置于已排数据的左边。也就是说我们第一次外层循环,是把最大数的位置交换到数组的最右边,第二次外层循环是把次大数交换到数组的次右边,依次类推。

    内层循环的作用是:

    实现我们想要的大数下沉的过程。每次比较的是相邻两个数据,所以一个数组的长度为n,我们只需要做 n-1 次相邻的比较,就可以实现大数下沉,而 之前循环已经沉淀的大数并不需要再进行 排序了。

    很清楚的看到N个数字要排序完成,总共进行N-1趟排序

    为什么外层循环判断条件是i<n-1呢?

    n 个数字总共需要 n-1 趟排序,外层循环 i 从0到 n-1 正好是 n-1 次。

    为什么内层循环判断条件是j<n-i-1呢?

    这要从冒泡排序原理说起:冒泡排序每循环排序一次,就把最大的一个数排在了最右边(默认升序排),每一次排序都是在上一次排序的基础上再排序,(比如)第2次排序之后,i已经成2了,第三次排序是要在第二次的基础上在进行排序,而第二次排序后就已经把两个最大的数已经放到最后了,所以第三次排序就不需要在去比他俩,就得把这个“2“减掉,只需要循环n-i次(此时的i是2);为什么-i之后还要-1呢? 这是因为在内层循环的判断中是把当前值和后面一个值做比较的。如果不减1,则当循环到最后一个值的时候,再取下一个值就取不到,就需要额外的操作,或者抛出数组下标越界的异常。

    其实内层的 j<n-i-1 这个范围的确定 让人纠结,它主要有两种理解方式

    1 就是标准解释 上述的防止数组下标越界,比如n[] = {5, 22, 7, 42, 23},个数n=5,i现为2,n-i=3,i为2即进行第3趟,两个数已经确定好,只需要比较前三个数了,而这只需要比较2次,即n-i(为2)-1=2。如果不减一,这里就是n-i(为2)= 3比三次,这显然是错的。就是正常是:

    if n(0)>n(1)
    if n(1)>(2)  这是正确的
    
     
    • 1
    • 2

    不正确时,5-2=3 j从0到3 得比3次:

    if n(0)>n(1)
    if n(1)>(2) 
    if n(2)>(3) 这就比错了  这都把 确定好的倒数第二大的数再给比较,这就是错了。就成乐下表越界了。
    
     
    • 1
    • 2
    • 3

    2 每趟的比较中,都是n-1次,每趟中都是比总共这次要比的数的个数减一次,再加上要把i这已经确定的数的个数减去,即就是 j-i-1。实际上这也是n-i,n把来的i减去,剩下的待排序的数共有多少个,他们的个数再减去一就是他们这些剩下的数需要比较的次数了,这个跟网上说的数组是从下标0开始,没啥关系,下标从0或1开始,影响的是内层循环的比较,是0,就直接引用,是1,就得n[i-1]。至于说的这个从0开始的说法,则它根本上也是想说防止下标越界。

    至于算法优化什么的,暂时不考虑,这里只简单说明了算法中几个关键的点。
    个人学习感悟,如有错误,还请指正。

    附一些讲冒泡比较好的说的文章:
    https://blog.csdn.net/kelinfeng16/article/details/84034386
    https://www.cnblogs.com/shen-hua/p/5422676.html

    展开全文
  • 冒泡排序

    千次阅读 多人点赞 2021-02-16 12:41:58
    第一轮笔试出的算法题是冒泡排序,全场只有一半的学生写了出来。 你可能会疑问冒泡怎么简单,怎么可能,哈哈,别急,冒泡排序虽然是最简单的算法,但是如果现在让屏幕前的你写,能立马写出来的在下面评论!所以往往...

    在这里插入图片描述
    在这里插入图片描述

    1. 前言

    轮子哥曾经在知乎里讲过这么一个事,当年他毕业的时候,有一个公司(微软)来上海招聘。第一轮笔试出的算法题是冒泡排序,全场只有一半的学生写了出来。

    你可能会疑问冒泡怎么简单,怎么可能,哈哈,别急,冒泡排序虽然是最简单的算法,但是如果现在让屏幕前的你写,能立马写出来的在下面评论!所以往往看似越简单的东西,越是能考查我们的基本功。这篇文章,就让小编带你学习一下冒泡排序吧。


    2. 冒泡算法

    这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。

    冒泡排序的算法复杂度为n^2,如果不了解什么是算法复杂度,可以先看一下这篇:算法复杂度

    现在通过一个动态图,让我们看一下冒泡排序的工作过程:在这里插入图片描述

    这个动态图演示了一个无序数组使用冒泡排序转变为一个从大到小的有序数组,让我们来观察一下,到第一个变黄的元素3,这期间经历了什么,我们暂且把这个数组称为A,A[0]和A[1]比较,A[0]里面的元素(值)小于A[1],交换元素,交换完之后,A[1]与A[2]两个相邻的两个元素比较,左边又小于右边,交换元素,交换完之后,A[2]与A[3]两个相邻的两个元素比较,左边是12,右边是3,左边比右边大,不交换元素,之后接着进行A[3]和A[4]的对比等等。。。

    好了,那现在我问你,到第一个变黄的元素3,这期间经历了几次比较?千万不要告诉我是6次,是5次,记住了!隔壁老王家8岁的孩子都知道5个手指之间有四个空隙,是两两比较,不要搞错喽,小编怕你被文字搞糊涂了,熬夜给你做了图,这下图文应该明白吧。

    在这里插入图片描述

    所以第一次循环应该是5次,并且最后的元素应该会是最小的元素,要记住哦。之后就是重复上述的步骤,只不过把最后一个排除,因为上文提到过,最后一个元素应该会是最小的数,所以之后的循环次数依次为:4次,3次,2次。到这里,我们的无序数组就会经过冒泡排序变成了有序数组。


    3. 冒泡排序算法的原理总结

    [1] 比较相邻的元素。如果第一个比第二个小,就交换他们两个。

    [2] 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。

    [3] 针对所有的元素重复以上的步骤,除了最后一个。

    [4] 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。


    4. 代码

    int array[] = {7,10,12,3,9,5};
        for (int i = 0; i < 6; i++) 
        {
              for (int j = 0; j < 6 - i - 1; j++) 
              {
                    if (array[j] < array[j + 1]) 
                    {
                          int tamp = array[j];
                          array[j] = array[j + 1];
                          array[j + 1] = tamp;
                    }
              }
        }    
    

    要说的就是注意第二层循环的条件,千万不要写错喽!


    展开全文
  • 冒泡排序算法

    万次阅读 多人点赞 2018-07-19 22:31:43
    什么是冒泡排序呢?...而冒泡排序之所以叫冒泡排序,正是因为这种排序算法的每一元素都可以向小气泡一样,根据自身大小,一点一点向着数组的一侧移动。具体如何移动呢?我们来看一下例子:  有...

    什么是冒泡排序呢?冒泡排序的英语名是Bubble Sort,是一种最基础的交换排序。

         大家一定都喝过汽水吧,汽水中常常有许多小小的气泡,往上飘,这是因为组成小气泡的二氧化碳比水要轻,所以小气泡才会一点一点的向上浮。而冒泡排序之所以叫冒泡排序,正是因为这种排序算法的每一个元素都可以向小气泡一样,根据自身大小,一点一点向着数组的一侧移动。具体如何移动呢?我们来看一下例子:

        有8个数组组成一个无序数列:5,8,6,3,9,2,1,7,希望从大到小排序。按照冒泡排序的思想,我们要把相邻的元素两两进行比较,根据大小交换元素的位置,过程如下:

    第一轮排序:

    1、首先让5和8进行交换,发现5比8小,因此元素位置不变。

    2、接下来让8和6比较,发现8比6大,所以要交换8和6的位置。3、

     3、继续让8和3比较,发现8比3要大,所以8和3 交换位置。

     4、继续让8和9进行比较,发现8比9小,不用交换

     5、9和2进行比较,发现9比2大,进行交换

    6、继续让9和1进行比较,发现9比1大,所以交换9和1的位置。

    7、最后,让9和7交换位置

    这样一来,元素9作为数列的最大元素,就已经排序好了。

     下面我们来进行第二轮排序:

    1、首先让5和6比较,发现5比6小,位置不变

    2、接下来让6和3比较,发现6比3大,交换位置

    3、接下来让6和8比较,6比8小,位置不变

    4、8和2比较。8比2大,交换位置

    5、接下来让8和1比较,8比1大,因此交换位置

    6、继续让8和7比较,发现8比7大,交换位置

    第二轮的状态为:

    第三轮的状态为:

    第四轮的状态为:

    第五轮的状态为:

    第六轮的状态:

    第七轮状态为:(已经有序了)

    第八轮的状态为:

    到此为止,所有的元素欧式有序的了,这就是冒泡排序的整体思路。

    原始的冒泡排序是稳定的,由于该排序算法的每一轮都要遍历一遍所有的元素,轮转的次数和元素数量相当,所以时间复杂度为O(N^2)。

    方法一:

    #include<stdio.h>
    #include<stdlib.h>
    
    void BubbleSort(int a[], int len)
    {
    	int i, j, temp;
    	for (j = 0; j < len - 1; j++)
    	{
    		for (i = 0; i < len - 1 - j; i++)
    		if (a[i] > a[i + 1])
    		{
    			temp = a[i];
    			a[i] = a[i + 1];
    			a[i + 1] = temp;
    		}
    	}
    }
    
    int main()
    {
    	int arr[] = { 5, 8, 6, 3, 9, 2, 1, 7 };
    	int len = sizeof(arr) / sizeof(arr[0]);
    	int i = 0;
    	printf("排序前:");
    	for (i = 0; i < len; i++)
    	{
    		printf("%d ", arr[i]);
    	}
    	printf("\n");
    
    	BubbleSort(arr, len);
    	printf("排序后:");
    	for (i = 0; i < len; i++)
    	{
    		printf("%d ", arr[i]);
    	}
    	printf("\n");
    	system("pause");
    	return 0;
    }

        这个代码很简单,使用双循环的方式进行排序。外部的循环控制所有回合,内部循环代表每一轮的冒泡处理,先进行元素比较,再进行元素交换。那么这个代码该怎么进行优化呢??我们现在来回顾一下之前的描述细节,仍然以 5,8,6,3,9,2,1,7 为例,当排序伏安法分别执行到第六、第七、第八轮的时候,数列的状态其实已经变为有序的了。

    第六轮状态:

    第七轮状态:

    第八轮状态: 

        在这种情况下,我们就不必要对这几次在重新进行排序,这样就会减少执行的次数,因此,我们可以进行一个优化,就是设置一个flags,如果已经排序了那么设置为0;如果不是有序的,那么设置为1。现在我们来看看优化后的代码。

    #include<stdio.h>
    #include<stdlib.h>
    
    void BubbleSort(int a[], int len)
    {
    	int i, j, temp;
    	int flags = 0;
    	for (j = 0; j < len - 1; j++)
    	{
    		for (i = 0; i < len - 1 - j; i++)
    		{
    			if (a[i] > a[i + 1])
    			{
    				temp = a[i];
    				a[i] = a[i + 1];
    				a[i + 1] = temp;
    				flags = 1;//不是有序的,flags设置为1;
    			}
    		}
    		if (flags == 0)
    			return;
    	}
    }
    
    int main()
    {
    	int arr[] = { 5, 8, 6, 3, 9, 2, 1, 7 };
    	int len = sizeof(arr) / sizeof(arr[0]);
    	int i = 0;
    	printf("排序前:");
    	for (i = 0; i < len; i++)
    	{
    		printf("%d ", arr[i]);
    	}
    	printf("\n");
    
    	BubbleSort(arr, len);
    	printf("排序后:");
    	for (i = 0; i < len; i++)
    	{
    		printf("%d ", arr[i]);
    	}
    	printf("\n");
    	system("pause");
    	return 0;
    }

         这一个版本的代码只是做了一个小小的改动,利用fags做标记。如果在本轮排序中,元素有交换,则说明数列无序,如果没有交换,则说明数列已然有序,直接返回。

    展开全文
  • SQL没有for循环,没有数组概念。 SQL可以用关键字order by排序。 declare @str varchar(500), @Count int, @i int, @j int, @num1 int, @num2 int, @temp int --接收一串字符 SET @str='98 108 102 91...
  • 最近在面试,发现有些杯具,算法这方面平时写得少,面试的时候就很可能写错,这里放几个备查吧。首先是冒泡排序,虽然是简单的东西,但是还是写一写。这个是基本类型int的数组版的:public static void sort(int[] ...
  • 冒泡排序 冒泡排序(Bubble Sort),是一种较简单的排序算法。 冒泡排序算法的原理如下: 比较相邻的元素。如果第一比第二大,就...循环次数优化:当冒泡排序进行外层循环时,内层循环中交换值语句不会再执.
  • 冒泡排序
  • 说到底冒泡排序就是对for循环与if判断的检测,也是一必须掌握的知识点。 无非就是将一数组进行从小到大的排序,a.length是获取数组的长度, 如下图: public class MaoPaoPaiXu { public static void main...
  • 双向循环链表的冒泡排序

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

    2021-01-08 17:00:40
    冒泡排序 1. 什么是冒泡排序? 计算机语言基础算法的一种。 把数组里面的数字按照规律排好序。 2. 算法描述: 比较相邻的两数,如果第一数比第二数大,则两数交换位置 ; 对之后的相邻元素进行同样的工作,从...
  • JS双重for循环实现冒泡排序

    千次阅读 2018-09-15 20:33:48
    由于冒泡排序需要用到交换变量,所以需要掌握交换变量的原理 假设,左手里拿了一苹果,右手里拿了一橘子,想要苹果和橘子调换位置,要怎么做?可见,需要先腾出一只手。 例如: 1、先把左手苹果放到桌子上  ...
  • 冒泡算法的原理是比较相邻的元素,如果第一比第二大(正序),就交换他们两的位置,然后继续往下找,每次找出最大或最小的那个值放在顶端两层循环的实现方式: 1:双层for循环嵌套; 2.判断条件如果满足,交换...
  • 单链表冒泡排序与数组冒泡排序

    千次阅读 2017-06-25 17:15:30
    冒泡排序冒泡排序是最基本也是最简单的一种排序,但是复杂度高不适合...下面的链表基于这种定义:http://blog.csdn.net/dawn_after_dark/article/details/73610674形式一冒泡排序其实有好种变形,原始的思想就是每一
  • 冒泡排序种实现

    2017-12-03 11:41:36
    原理冒泡排序算法的基本思想为:假如待排序线性表的长度为 n,要使其从小到大排序,从前往后两两比较相邻元素的关键字,若第i+1元素比第i小,则交换它们,直到遍历整个线性表。每趟交换以后最后一元素一定是...
  • 冒泡排序 看名字就很熟悉很形象,接触到的第一次排序算法就是冒泡算法 冒泡排序法算法描述 依次比较相邻二数据,如果前面数据大于后面的数据就将二数据交换。 对长度为N的组数,从第0遍历到第N-1,此时最大的...
  • 排序2-冒泡排序

    2019-03-10 17:25:49
    本篇文章介绍冒泡排序及其优化方式与改进算法,从最简单的冒泡排序开始,不断地升级算法处理方式,介绍包括「鸡尾酒排序」、「梳排序」相关的实现与原理。 经典冒泡排序 其基本原理在之前的文章里面已经说过,就是...
  • 冒泡排序算法应该算是每个开发者入门必学的基础算法,它逻辑清晰简单,代码实现也并不复杂,这里用自己...冒泡排序既然是一个排序算法,那么它就一定是有一个循环排序的过程,其实它的原理很简单,就是两层for循环嵌...
  • 第一种 public class BubbleSort { public static void main(String[] args) { //冒泡排序 从大到小 int [] arr = {1,32,141,23,141,23342,232,43,2}; int n = arr.length; int t = -1;
  • 排序算法有很多,包括插入排序,冒泡排序,堆排序,归并排序,选择排序,计数排序,基数排序,桶排序,快速排序等。 插入排序,堆排序,选择排序,归并排序,快速排序,冒泡排序都是比较排序,它们通过对数组中的...
  • 单链表排序之冒泡排序

    万次阅读 多人点赞 2016-06-07 12:26:42
    ***单链表排序之冒泡排序*** /* 前段时间刚学会种排序方法,最近学习了单链表,就用来试试,本篇链表的排序方法讲述的是 单链表的冒泡排序;(注意:请仔细看准节点结构体的包装和头指针的包装再阅读以下代码...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 36,477
精华内容 14,590
关键字:

冒泡排序需要几个循环