33

Go实现冒泡排序

 5 years ago
source link: https://studygolang.com/articles/18778?amp%3Butm_medium=referral
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

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

排序分类：

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

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

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

Z3Q3qiA.gif

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

冒泡排序的思路分析：

yYNfUjV.png!web 第一次排序 

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)

}

FbyEZrr.png!web

上面的判断是直接写进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)  //传入数组的地址

}

2qYNzeq.png!web

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

第二次排序

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]

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


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK