Golang实现基本排序算法

jopen 7年前

排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。

冒泡排序

func BubbleSort(vector []int) {      fmt.Println("BubbleSort")      fmt.Println(vector)      for i := 0; i < len(vector); i++ {          tag := true // 为了剪枝          // 每一趟将最大的数冒泡          for j := 0; j < len(vector)-i-1; j++ {              if vector[j] > vector[j+1] { /*vector[j] < vector[j+1]*/                  temp := vector[j]                  vector[j] = vector[j+1]                  vector[j+1] = temp                  tag = false              }          }          if tag {              break //0~len(vector)-i没有发生交换说明已经有序          }          fmt.Println(vector)      }  }

插入排序

func InsertSort(vector []int) {      fmt.Println("InsertSort")      fmt.Println(vector)      for i := 1; i < len(vector); i++ {          // 每一趟不满足条件就选择i为哨兵保存,将哨兵插入0~i-1有序序列(0~i-1始终是有序的)          if vector[i] < vector[i-1] { /*vector[i] > vector[i-1]*/              temp := vector[i]              //后移直到找到哨兵合适的位置              j := i - 1              for ; j >= 0 && vector[j] > temp; j-- { /*vector[j] < temp*/                  vector[j+1] = vector[j]              }              //插入位置前后都是有序的,最后也是有序的              vector[j+1] = temp          }          fmt.Println(vector)      }  }

选择排序

func SelectSort(vector []int) {      fmt.Println("SelectSort")      fmt.Println(vector)      for i := 0; i < len(vector); i++ {          // 选择最小的元素          k := i          for j := i + 1; j < len(vector); j++ {              if vector[k] > vector[j] {                  k = j              }          }          // 交换          if k != i {              temp := vector[i]              vector[i] = vector[k]              vector[k] = temp          }          fmt.Println(vector)      }  }

二元选择排序

func BinarySelectSort(vector []int) {      fmt.Println("SelectSort")      fmt.Println(vector)      n := len(vector)      for i := 0; i < n/2; i++ {          // 选择最小的元素和最大元素          k := i          t := n - i - 1          for j := i + 1; j <= n-i-1; j++ {              if vector[k] > vector[j] {                  k = j              }              if vector[t] < vector[j] {                  t = j              }          }          // 交换          if k != i {              temp := vector[i]              vector[i] = vector[k]              vector[k] = temp          }          if t != n-i-1 {              temp := vector[n-i-1]              vector[n-i-1] = vector[t]              vector[t] = temp          }          fmt.Println(vector)      }  }

快速排序

简单的说快速排序就是挖坑填数然后分治,公认效率最好,这个必须会

func QuickSort(vector []int, low, hight int) {   fmt.Println(vector)   if low < hight {    i := low    j := hight    temp := vector[low] // 开始挖坑填数    for i < j {     for i < j && vector[j] >= temp {      j--     }     vector[i] = vector[j]     for i < j && vector[i] <= temp {      i++     }     vector[j] = vector[i]    }    vector[i] = temp    QuickSort(vector, low, i-1) // 分治    QuickSort(vector, i+1, hight)   }  }

常见问题,已知序列WAUSTHKO,将第一个数作W为基数,问:

1,第一趟后的序列是多少?假设递归同时进行

1),OAUSTHKW

2),KAHOTSUW

3),HAKOSTUW

4),AHKOSTUW

2,排序过程中那些数会被作为选基数?

以上标记的都是:W,O,K、T,H

3,基数的选择直接影响到效率,同时排序末尾显然有效率问题,可以用其他算法替换。

来自:http://my.oschina.net/xlplbo/blog/343768