冒泡排序的落成,冒泡排序实现

By admin in 4858.com on 2019年3月25日

冒泡排序的周转原理(好精通):

冒泡排序(Bubble Sort),是一种计算机科学领域的较不难的排序算法。

它再一次地拜会过要排序的数列,2回相比多个成分,借使她们的一一错误就把他们沟通过来。走访数列的做事是再一次地拓展直到没有再要求交流,也正是说该数列已经排序达成。

冒泡排序的落到实处,冒泡排序完成

① 、冒泡排序简介

冒泡排序,重复地走访过要排序的数列,一遍相比较两个因素,假使他们的顺序错误就把她们交流过来。走访数列的做事是重新鸿营地产进行直到没有再需求调换,也正是说该数列已经排序完毕。

  1. 相比相邻的因素。假如第①个比第三个大,就调换他们四个。
  2. 对每一对附近成分作同样的干活,从上马首先对到最后的终极一对。那步做完后,最终的要素会是最大的数。
  3. 针对具有的要素重复以上的手续,除了最后多个。
  4. 源源不断每一遍对越来越少的元素重复上边的手续,直到没有别的一对数字需求相比较。

4858.com 1

① 、冒泡排序简介

冒泡排序,重复地拜会过要排序的数列,叁回相比较三个成分,如果她们的逐条错误就把他们调换过来。走访数列的做事是重新鸿基土地资金财产开始展览直到没有再供给沟通,约等于说该数列已经排序完结。

贰 、算法的运行

冒泡排序算法的周转如下:(从后往前)

  1. 相比较相邻的要素。假诺第四个比第三个大,就沟通他们四个。

  2. 对每一对附近元素作同样的办事,从开始首先对到结尾的末尾一对。在那或多或少,最终的成分应该会是最大的数。

  3. 针对富有的成分重复以上的步调,除了最终贰个。

  4. 冒泡排序的落成,冒泡排序实现。没完没了每一趟对越来越少的因素重复上边包车型大巴步骤,直到没有别的一对数字供给比较。4858.com 2

备考:上述讲解来自 维基百科 冒泡排序

冒泡排序进程

贰 、算法的周转

冒泡排序算法的运维如下:(从后往前)

  1. 相比较相邻的因素。如果首个比第二个大,就调换他们多个。
  2. 对每一对附近成分作同样的干活,从上马首先对到最后的结尾一对。在那或多或少,最终的要素应该会是最大的数。
  3. 针对具有的成分重复以上的手续,除了最终二个。
  4. 不断每趟对越来越少的成分重复上边包车型客车手续,直到没有其他一对数字供给相比。4858.com 3

③ 、时间复杂度

     
若文件的起来状态是正序的,一趟扫描即可形成排序。所需的机要字相比较次数和记录移动次数均达到最小值:相比较次数:
n-1 ,移动次数为0 。所以,冒泡排序最佳的时刻复杂度为O(n) 。
  若开首文件是反序的,需求开始展览趟n-1 排序。每便排序要拓展 n-i
((1≤i≤n-1))次重要字的可比,且每趟相比较都不可能不移动记录一次来达到沟通记录地点。在那种景观下,相比较和活动次数均达到最大值:比较次数n*(n-1)/2
,移动次数3n*(n-1)/2 。
冒泡排序的最坏时间复杂度为O(n*n) 。
综上,由此冒泡排序总的平均时间复杂度为O(n*n) 。

代码如下(从大到小排序):

算法原理(从后往前):

  1. 比较相邻的要素。假诺第③个比第四个大,就交流他们多少个。

2.
对每一对附近成分作同样的办事,从发轫首先对到最后的终极一对。在那或多或少,最终的成分应该会是最大的数。

  1. 针对富有的因素重复以上的手续,除了最后多个。

4.
持续每一次对越来越少的因素重复上面的手续,直到没有任何一对数字须要相比。

三 、时间复杂度

     
若文件的上马状态是正序的,一趟扫描即可形成排序。所需的重庆大学字比较次数和笔录移动次数均达到规定的标准最小值:相比次数:
n-1 ,移动次数为0 。所以,冒泡排序最佳的年月复杂度为O(n) 。
  若早先文件是反序的,须要展开趟n-1 排序。每一趟排序要进行 n-i
((1≤i≤n-1))次首要字的可比,且每一遍比较都必须移动记录三遍来达到沟通记录地点。在那种状态下,相比较和移动次数均达到规定的标准最大值:比较次数n*(n-1)/2
,移动次数3n*(n-1)/2 。
冒泡排序的最坏时间复杂度为O(n*n) 。
综上,因而冒泡排序总的平均时间复杂度为O(n*n) 。

四 、算法稳定性

冒泡排序正是把小的要素往前调或许把大的要素以后调。比较是邻近的多少个成分相比,调换也爆发在那多少个因素之间。所以,假诺三个要素相等,不用交流一下的;如若四个13分的成分没有相邻,那么固然通过前面包车型大巴两两置换把八个相邻起来,那时候也不会换成,所以同样成分的左右相继并没有改观,所以冒泡排序是一种祥和排序算法。

 

int[] sort = new int[13] { 1, 4, 89, 34, 56, 40, 59, 60, 39, 1, 40, 90, 48 };  // 输入一个数组
 for (int i = 0; i < sort.Length; i++)  // 循环每个元素。
            {
                for (int j = i+1; j < sort.Length; j++) // 每个元素都与它之后的元素进行一对一比较。
                {
                    if (sort[i] < sort[j])  // 当有值比sort[i]大时,就交换数值。
                    { 
                    int temp = sort[i];
                    sort[i] = sort[j];
                    sort[j] = temp;    // sort[i] 获取的是始终为最大值。
                    }
                }
            }
 for (int i = 0; i < sort.Length; i++)  // 输出
            {
                Console.Write(sort[i] + " ");
            }

算法达成:

4858.com 4

java实现

4858.com 5

4858.com,python实现


冒泡排序便是把小的要素往前调或许把大的要素今后调。相比是相邻的八个元素相比较,交换也时有发生在那多个因素之间。所以,借使四个要素相等,笔者想你是不会再俗气地把她们俩换来一下的;如若五个优良的因素没有相邻,那么尽管通过前边的两两置换把多少个相邻起来,那时候也不会换换,所以同样成分的上下相继并没有变动,所以冒泡排序是一种祥和排序算法。

4858.com 6

动态演示

肆 、算法稳定性

冒泡排序便是把小的成分往前调或许把大的因素未来调。比较是附近的多个因素相比,调换也发出在那八个要素之间。所以,假若多少个成分相等,不用沟通一下的;借使五个非凡的因素没有相邻,那么尽管通过前边的两两置换把三个相邻起来,那时候也不会换换,所以一律成分的前后相继并没有更改,所以冒泡排序是一种祥和排序算法。

 

伍 、代码落成

#include <stdio.h>
#define SIZE 8

void bubble_sort(int a[], int n);

void bubble_sort(int a[], int n)
{
    int i, j, temp;
    for (j = 0; j < n - 1; j++)
        for (i = 0; i < n - 1 - j; i++)
        {
            if(a[i] > a[i + 1])
            {
                temp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = temp;
            }
        }
}

int main()
{
    int number[SIZE] = {95, 45, 15, 78, 84, 51, 24, 12};
    int i;
    bubble_sort(number, SIZE);
    for (i = 0; i < SIZE; i++)
    {
        printf("%d", number[i]);
    }
    printf("\n");
}

 

  

⑤ 、代码完毕

#include <stdio.h>
#define SIZE 8

void bubble_sort(int a[], int n);

void bubble_sort(int a[], int n)
{
    int i, j, temp;
    for (j = 0; j < n - 1; j++)
        for (i = 0; i < n - 1 - j; i++)
        {
            if(a[i] > a[i + 1])
            {
                temp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = temp;
            }
        }
}

int main()
{
    int number[SIZE] = {95, 45, 15, 78, 84, 51, 24, 12};
    int i;
    bubble_sort(number, SIZE);
    for (i = 0; i < SIZE; i++)
    {
        printf("%d", number[i]);
    }
    printf("\n");
}

 

① 、冒泡排序简介
冒泡排序,重复地访问过要排序的数列,2回比较五个要素,若是他们的顺序错误就把…

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图
Copyright @ 2010-2019 美高梅手机版4858 版权所有