Go实现冒泡排序

栏目: Go · 发布时间: 5年前

内容简介:排序:排序是将一组数据,按照一定的顺序进行排列的过程。排序分类:内部排序:指将需要处理的所有数据都加载到内存存储器中进行排序。包括(交换式排序法、选择式排序法和插入式排序法)。

排序:排序是将一组数据,按照一定的顺序进行排列的过程。

排序分类:

内部排序:指将需要处理的所有数据都加载到内存存储器中进行排序。包括(交换式排序法、选择式排序法和插入式 排序 法)。

外部排序法: 数据量过大,无法全部加载到内存中,需要借助外部存储进行排序,包括(合并排序法和直接合并排序法)。

冒泡排序: (Bubble Sorting)基本思想是通过对待排序序列从后向前(从下标较大的元素开始)以此比较相邻元素的排序码,若发现逆序则交换,使排序码较小的元素逐渐从后补移向前部(从下标较大的单元移向单位较小的单元),就像水底的气泡一样逐渐向上冒。

Go实现冒泡排序

因为排序的过程中,各元素不断的接近自己的位置,如果一趟比较下来没有进行过交换,就说明序列有序,因此要在排序过程中设置一个标志flag判断元素是否进行过交换,从而减少不必要的比较(优化)。

冒泡排序的思路分析:

Go实现冒泡排序 第一次排序

package main

import "fmt"
//分析冒泡排序

var arr [5]int = [5]int{24,69,80,57,13}
func main()  {
   fmt.Println("排序前",arr)
   tmp := 0 //定义临时变量
   for  i := 0 ;i< 4; i++{
      if arr[i] > arr[1] {
         tmp = arr[i]
         arr[i] = arr[i+1]
         arr[i+1] = tmp
      }
   }
   fmt.Println("第一次排序后",arr)

}

Go实现冒泡排序

上面的判断是直接写进main()函数中,维护不太方便考虑将其单独抽出定义一个函数BubbleSort()将数组传入里面

package main

import "fmt"
//分析冒泡排序
func  BubbleSort(arr *[5]int){
   fmt.Println("排序前",(*arr))
   tmp := 0 //定义临时变量
   for  i := 0 ;i< 4; i++{
      if arr[i] > arr[1] {
         tmp = arr[i]
         arr[i] = arr[i+1]
         arr[i+1] = tmp
      }
   }
   fmt.Println("第一次排序后",(*arr))

}

var arr2 [5]int = [5]int{24,69,80,57,13}
func main()  {
   BubbleSort(&arr2)  //传入数组的地址

}

Go实现冒泡排序

使用函数方式的编程会使得代码美观,同时方便维护。

第二次排序

package main

import "fmt"
//分析冒泡排序
func  BubbleSort(arr *[5]int){
   fmt.Println("排序前",(*arr))
   tmp := 0 //定义临时变量
   for  i := 0 ;i< 4; i++{
      if arr[i] > arr[i+1] {
         tmp = arr[i]
         arr[i] = arr[i+1]
         arr[i+1] = tmp
      }
      fmt.Println("第一次排序后",(*arr))
   }

   for  i := 0 ;i< 3; i++{
      if arr[i] > arr[i+1] {
         tmp = arr[i]
         arr[i] = arr[i+1]
         arr[i+1] = tmp

      }
      fmt.Println("第二次排序后",(*arr))
   }


}

var arr2 [5]int = [5]int{24,69,80,57,13}
func main()  {
   BubbleSort(&arr2)  //传入数组的地址

}


//结果
排序前 [24 69 80 57 13]
第一次排序后 [24 69 80 57 13]
第一次排序后 [24 69 80 57 13]
第一次排序后 [24 69 57 80 13]
第一次排序后 [24 69 57 13 80]
第二次排序后 [24 69 57 13 80]
第二次排序后 [24 57 69 13 80]
第二次排序后 [24 57 13 69 80]

第三次比较

package main

import "fmt"
//分析冒泡排序
func  BubbleSort(arr *[5]int){
   fmt.Println("排序前",(*arr))
   tmp := 0 //定义临时变量
   for  i := 0 ;i< 4; i++{
      if arr[i] > arr[i+1] {
         tmp = arr[i]
         arr[i] = arr[i+1]
         arr[i+1] = tmp
      }
      fmt.Println("第一次排序后",(*arr))
   }

   for  i := 0 ;i< 3; i++{
      if arr[i] > arr[i+1] {
         tmp = arr[i]
         arr[i] = arr[i+1]
         arr[i+1] = tmp

      }
      fmt.Println("第二次排序后",(*arr))
   }
   for  i := 0 ;i< 2; i++{
      if arr[i] > arr[i+1] {
         tmp = arr[i]
         arr[i] = arr[i+1]
         arr[i+1] = tmp

      }
      fmt.Println("第三次排序后",(*arr))
   }


}

var arr2 [5]int = [5]int{24,69,80,57,13}
func main()  {
   BubbleSort(&arr2)  //传入数组的地址

}

//结果
排序前 [24 69 80 57 13]
第一次排序后 [24 69 80 57 13]
第一次排序后 [24 69 80 57 13]
第一次排序后 [24 69 57 80 13]
第一次排序后 [24 69 57 13 80]
第二次排序后 [24 69 57 13 80]
第二次排序后 [24 57 69 13 80]
第二次排序后 [24 57 13 69 80]
第三次排序后 [24 57 13 69 80]
第三次排序后 [24 13 57 69 80]

第四次比较

package main

import "fmt"
//分析冒泡排序
func  BubbleSort(arr *[5]int){
   fmt.Println("排序前",(*arr))
   tmp := 0 //定义临时变量
   for  i := 0 ;i< 4; i++{
      if arr[i] > arr[i+1] {
         tmp = arr[i]
         arr[i] = arr[i+1]
         arr[i+1] = tmp
      }
      fmt.Println("第一次排序后",(*arr))
   }

   for  i := 0 ;i< 3; i++{
      if arr[i] > arr[i+1] {
         tmp = arr[i]
         arr[i] = arr[i+1]
         arr[i+1] = tmp

      }
      fmt.Println("第二次排序后",(*arr))
   }
   for  i := 0 ;i< 2; i++{
      if arr[i] > arr[i+1] {
         tmp = arr[i]
         arr[i] = arr[i+1]
         arr[i+1] = tmp

      }
      fmt.Println("第三次排序后",(*arr))
   }
   for  i := 0 ;i< 1; i++{
      if arr[i] > arr[i+1] {
         tmp = arr[i]
         arr[i] = arr[i+1]
         arr[i+1] = tmp

      }
      fmt.Println("第四次排序后",(*arr))
   }



}

var arr2 [5]int = [5]int{24,69,80,57,13}
func main()  {
   BubbleSort(&arr2)  //传入数组的地址

}


排序前 [24 69 80 57 13]
第一次排序后 [24 69 80 57 13]
第一次排序后 [24 69 80 57 13]
第一次排序后 [24 69 57 80 13]
第一次排序后 [24 69 57 13 80]
第二次排序后 [24 69 57 13 80]
第二次排序后 [24 57 69 13 80]
第二次排序后 [24 57 13 69 80]
第三次排序后 [24 57 13 69 80]
第三次排序后 [24 13 57 69 80]
第四次排序后 [13 24 57 69 80]

四次外部比较完成,我们观察得到第一次外部比较中,内部元素比较了4次,为n-1,第二次外部比较时,内部元素比较了3次,为n-2,第三次外部比较时,内部元素比较了2次,为n-3,第四次外部比较时 内部元素比较了1次,为n-4.同时发现我们上面的代码使用了四次for循环,但是结构一致,可以对其优化成嵌套时循环对其优化。

package main

import "fmt"
//分析冒泡排序
func  BubbleSort(arr *[5]int){
   fmt.Println("排序前",(*arr))
   tmp := 0 //定义临时变量
   for j :=0 ; j < len(arr)-1 ;j++{
      //多次循环遍历的时候i是越来越小,j是增大的 用len(arry)-i-j实现遍历
      for  i := 0 ;i< len(arr)-1-j; i++{
         if arr[i] > arr[i+1] {
            tmp = arr[i]
            arr[i] = arr[i+1]
            arr[i+1] = tmp
         }

      }

   }
   fmt.Println("排序后",(*arr))
}

var arr2 [5]int = [5]int{24,69,80,57,13}
func main()  {
   BubbleSort(&arr2)  //传入数组的地址

}

//结果
排序前 [24 69 80 57 13]
排序后 [13 24 57 69 80]

代码量明显减少,结构更加清晰


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

风吹江南之互联网金融

风吹江南之互联网金融

陈宇(江南愤青) / 东方出版社 / 2014-6-1 / 55元

随着中国互联网金融浪潮高涨,P2P、众筹、余额宝、微信支付等新生事物层出不穷,加之大数据等时髦概念助阵,简直是乱花渐欲迷人眼,令媒体兴奋,公众狂热。那么,互联网金融真的能“颠覆”传统金融吗?当互联网思维对撞传统金融观念,是互联网金融的一统天下,还是传统金融业的自我革新?究竟是谁动了金融业的奶酪? 本书作者早期试水创立具有互联网金融雏形的网站,后来成为互联网金融的资深投资人,基于其多年在该领域......一起来看看 《风吹江南之互联网金融》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具