冒泡排序的三种实现方法

冒泡排序是非常容易理解和实现，以从小到大排序举例：

设数组长度为N。

1．比较相邻的前后二个数据，如果前面数据大于后面的数据，就将二个数据交换。

2．这样对数组的第0个数据到N-1个数据进行一次遍历后，最大的一个数据就“沉”到数组第N-1个位置。

3．N=N-1，如果N不为0就重复前面二步，否则排序完成。

按照定义很容易写出代码：


代码如下:

//冒泡排序1
void BubbleSort1(int a[], int n)
{
       int i, j;
       for (i = 0; i < n; i++)
              for (j = 1; j < n - i; j++)
                     if (a[j - 1] > a[j])
                            Swap(a[j - 1], a[j]);
}

下面对其进行优化，设置一个标志，如果这一趟发生了交换，则为true，否则为false。明显如果有一趟没有发生交换，说明排序已经完成。


代码如下:

//冒泡排序2
void BubbleSort2(int a[], int n)
{
       int j, k;
       bool flag;

k = n;
       flag = true;
       while (flag)
       {
              flag = false;
              for (j = 1; j < k; j++)
                     if (a[j - 1] > a[j])
                     {
                            Swap(a[j - 1], a[j]);
                            flag = true;
                     }
              k--;
       }
}

再做进一步的优化。如果有100个数的数组，仅前面10个无序，后面90个都已排好序且都大于前面10个数字，那么在第一趟遍历后，最后发生交换的位置必定小于10，且这个位置之后的数据必定已经有序了，记录下这位置，第二次只要从数组头部遍历到这个位置就可以了。


代码如下:

//冒泡排序3
void BubbleSort3(int a[], int n)
{
 int j, k;
 int flag;

flag = n;
 while (flag > 0)
 {
  k = flag;
  flag = 0;
  for (j = 1; j < k; j++)
   if (a[j - 1] > a[j])
   {
    Swap(a[j - 1], a[j]);
    flag = j;
   }
 }
}

冒泡排序毕竟是一种效率低下的排序方法，在数据规模很小时，可以采用。数据规模比较大时，最好用其它排序方法。

赞 (0)

相关推荐

  • 用c语言实现冒泡排序,选择排序,快速排序

    代码如下所示: 复制代码 代码如下: /* * 冒泡排序 */void BubbleSort(int arr[], int n){ int temp; for (int i = 0; i < n - 1; i++) {  for (int j = i + 1; j < n; j++)  {   if (arr[i] > arr[j])   {    temp = arr[i];    arr[i] = arr[j];    arr[j] = temp;   }  } }}/* * 选择排

  • c语言冒泡排序法代码

    总在写 总在错, 面试也还忘记 学习就是这么个过程, 温故才知新, 望自己谨记 忘记不要紧 复习就好 //排序是有很多种方法的 ,完成从小到大的排列 复制代码 代码如下: #include <stdio.h>void sort(int *a,int len){int i=0; int j; int t;    for(i=0;i<len;i++)    {        for(j=0;j<len-i-1;j++)        {            if(a[j]>a[

  • c# 冒泡排序算法(Bubble Sort) 附实例代码

    c# 冒泡排序算法(Bubble Sort) 附实例代码

    冒泡排序(Bubble Sort) 冒泡排序算法的运作如下: 1.比较相邻的元素.如果第一个比第二个大,就交换他们两个.2.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.在这一点,最后的元素应该会是最大的数.3.针对所有的元素重复以上的步骤,除了最后一个.4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较. 平均时间复杂度 复制代码 代码如下: /// <summary> /// 冒泡排序 /// </summary> /// <param

  • PHP 冒泡排序 二分查找 顺序查找 二维数组排序算法函数的详解

    数据结构很重要,算法+数据结构+文档=程序使用PHP描述冒泡排序算法,对象可以是一个数组 复制代码 代码如下: //冒泡排序(数组排序)function bubble_sort($array) {$count = count($array);if ($count <= 0)return false;for($i=0; $i<$count; $i++){for($j=$count-1; $j>$i; $j–){if ($array[$j] < $array[$j-1]){$tmp =

  • java冒泡排序算法代码

    复制代码 代码如下: /** * 原理: * 进行n次循环,每次循环从后往前对相邻两个元素进行比较,小的往前,大的往后 *  * 时间复杂度: * 平均情况:O(n^2) * 最好情况:O(n) * 最坏情况:O(n^2) * * 稳定性:稳定 **/public class 冒泡排序 { public int[] bubbleSort(int[] a, int n) {        for (int i = 0; i < n; i++) {            int flag = 0; 

  • 基于php冒泡排序算法的深入理解

    交换排序的基本思想:两两比较待排序的数据,如果发生逆序,则交换之,直到全部数据都排好序为止.•冒泡排序的基本思想:1.从后往前,扫描所有的数据,如果相邻的两个数发生逆序,则互换.--第1趟冒泡2.从后往前,扫描最后一个到第2个数据,如果相邻的两个数发生逆序,则互换.--第2趟冒泡3.如此依次进行,直到进行n-1趟冒泡,或者在某趟冒泡中,没有逆序的情况即可提前结束. 复制代码 代码如下: <script>var arr = [15,8,7,9,10,0]; var _len = arr.leng

  • python冒泡排序算法的实现代码

    1.算法描述:(1)共循环 n-1 次(2)每次循环中,如果 前面的数大于后面的数,就交换(3)设置一个标签,如果上次没有交换,就说明这个是已经好了的. 2.python冒泡排序代码 复制代码 代码如下: #!/usr/bin/python# -*- coding: utf-8 -*- def bubble(l):    flag = True    for i in range(len(l)-1, 0, -1):        if flag:             flag = False

  • 深入Java冒泡排序与选择排序的区别详解

    冒泡排序它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.代码如下: 复制代码 代码如下: public class nums {     public static void main(String[] args){         int []nums = {5,4,3,2,1};         for(int i = 0; i < nums.length; i++){        

  • 冒泡排序的三种实现方法

    冒泡排序是非常容易理解和实现,以从小到大排序举例: 设数组长度为N. 1．比较相邻的前后二个数据,如果前面数据大于后面的数据,就将二个数据交换. 2．这样对数组的第0个数据到N-1个数据进行一次遍历后,最大的一个数据就"沉"到数组第N-1个位置. 3．N=N-1,如果N不为0就重复前面二步,否则排序完成. 按照定义很容易写出代码: 复制代码 代码如下: //冒泡排序1void BubbleSort1(int a[], int n){       int i, j;       for

  • JS面向对象（3）之Object类，静态属性，闭包，私有属性， call和apply的使用，继承的三种实现方法

    1.Object类 在JS中,Object是所有类的基类,使用Object类来创建自定义对象时,可以无需定义构造函数(constructor,prototype,hasOwnProperty(property)) var per = new Object(); per.name = 'zhangsan'; per.age = ; alert(per.name + per.age); 我们想在程序中得到一个对象变量,只要能存储大量数据即可,这个时候,我们可以考虑使用Object类.Object类避

  • C语言中函数指针的三种使用方法总结

     C语言中函数指针的三种使用方法总结 在这里分享一下自己的心得,希望和大家一起分享技术,如果有什么不足,还请大家指正.写出这篇目的,就是希望大家一起成长,我也相信技术之间没有高低,只有互补,只有分享,才能使彼此更加成长. 定义方式:int (*p)(int x, int y); 实现代码: #include <stdio.h> int sum(int x, int y){ return x + y; } int reduce(int x, int y){ return x - y; } int

  • ajax 三种实现方法实例代码

    ajax即异步的javascript and xml, 本文章向码农们介绍ajax的三种实现方法(prototype实现,jquery实现,XMLHttpRequest实现) 本文主要是比较三种实现Ajax的方式,为以后的学习开个头. 准备: 1.  prototype.js 2.  jquery1.3.2.min.js 3.  json2.js 后台处理程序(Servlet),访问路径servlet/testAjax: Java代码 package ajax.servlet; import j

  • spring与mybatis三种整合方法

    1.采用MapperScannerConfigurer,它将会查找类路径下的映射器并自动将它们创建成MapperFactoryBean. spring-mybatis.xml: <?xml version="1.0" encoding="UTF-8"?> <beans xmlns="http://www.springframework.org/schema/beans" xmlns:xsi="http://www.w3

  • JavaScript定义函数的三种实现方法

    JavaScript定义函数的三种实现方法 [1]正常方法 function print(msg){ document.write(msg); } 对函数进行调用的几种方式: 函数名(传递给函数的参数1,传递给函数的参数2,-.) 变量 = 函数名(传递给函数的参数1,传递给函数的参数2,-.) 对于有返回值的函数调用,也可以在程序中直接使用返回的结果,例如:alert("sum=" + square(2,3)); 不指定任何函数值的函数,返回undefined. [2]构造函数方法 

  • java 多线程的三种构建方法

    java  多线程的三种构建方法 继承Thread类创建线程类 public class Thread extends Object implements Runnable 定义Thread类的子类,并重写其run()方法 创建Thread子类的实例,即创建了线程对象 调用线程对象的start()方法启动线程 public class FirstThread extends Thread { public void run(){ for(int i=0;i<100;i++){ /* * Thre

  • jquery关于事件冒泡和事件委托的技巧及阻止与允许事件冒泡的三种实现方法

    首先,大家都知道,jQuery事件触发时有2种机制,一种是事件委托,另一种是事件冒泡(IE情况暂时不考虑).拿click事件做例子,先附上一段代码: html: <body> <div id="box"> <p id="btn">我是按钮</p> </div> </body> style: .hid{ display:none; } script: $('#box').click(functio

  • java中关于Map的三种遍历方法详解

    map的三种遍历方法!集合的一个很重要的操作---遍历,学习了三种遍历方法,三种方法各有优缺点~~ 复制代码 代码如下: /* * To change this template, choose Tools | Templates * and open the template in the editor. */package cn.tsp2c.liubao;import java.util.Collection;import java.util.HashMap;import java.util

  • C#使用DataSet Datatable更新数据库的三种实现方法

    本文以实例形式讲述了使用DataSet Datatable更新数据库的三种实现方法,包括CommandBuilder 方法.DataAdapter 更新数据源以及使用sql语句更新.分享给大家供大家参考之用.具体方法如下: 一.自动生成命令的条件 CommandBuilder 方法 a)动态指定 SelectCommand 属性 b)利用 CommandBuilder 对象自动生成 DataAdapter 的 DeleteCommand.InsertCommand 和 UpdateCommand

随机推荐