常用算法笔记 > 常用排序算法
冒泡排序和选择排序

冒泡排序和选择排序应该是最简单排序算法,下面直接上代码(从小到大排序).


冒泡排序代码-golang:

稳定性:冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,是不会再交换的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。

时间复杂度:

若文件的初始状态是正序的,一趟扫描即可完成排序。所需的关键字比较次数  和记录移动次数  均达到最小值:

   

所以,冒泡排序最好的时间复杂度  

  若初始文件是反序的,需要进行  趟排序。每趟排序要进行  次关键字的比较(1≤i≤n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值:

冒泡排序的最坏时间复杂度为  综上,因此冒泡排序总的平均时间复杂度为  

冒泡排序代码:

package main

import "fmt"

func bubble1(items []int) {
   length := len(items)
   for i := 0; i < length-1; i++ {
      flag := false
      for j := 0; j<length -1; j++ {
         if items[j] > items[j+1] {
            items[j], items[j+1] = items[j+1], items[j]
            flag = true
         }
      }
      if flag == false {
         return
      }
   }
}

/* 采用从尾部冒泡, 相比上面算法可以缩减1/2次的循环次数 */
func bubble2(items []int) {
   length := len(items)

   for i := 0; i < length-1; i++ {
      flag := false
      for j := length - 1; j > i; j-- {
         if items[j] < items[j-1] {
            items[j], items[j-1] = items[j-1], items[j]
            flag = true
         }
      }
      if flag == false {
         return 
      }
   }
}


func main() {
   items := []int{8, 2, 9, 4, 8, 1, 7, 22}
   bubble2(items)
   fmt.Println(items)
}



选择排序代码-golang.

稳定性:选择排序是一种不稳定排序:  以面数组  8, 2, 9, 4, 8, 1, 7, 22 为例. 在第一次排序过程中 8 和 1 交换位置导致原始数组第一个8移到了第二个8后面 .... 在排序完成后原本排在前面的8和后面的8先后次序颠倒了所以该算法不稳定.

package main

import "fmt"

func select_sort(items []int) {
   length := len(items)
   for i := 0; i < length-1; i++ {
      pos := i
      for j := i + 1; j < length; j++ {
         if items[j] < items[pos] {
            pos = j
         }
      }
      if pos != i {
         items[pos], items[i] = items[i], items[pos]
      }
   }
}

func main() {
   items := []int{8, 2, 9, 4, 8, 1, 7, 22}
   select_sort(items)
   fmt.Println(items)
}