算法排序之选择、插入、冒泡、归并排序

选择排序法

• 复杂度：n²

func SelectionSort(arr []int) {
   for i := 0; i < len(arr); i++ {
      var max = i
      for j := i + 1; j < len(arr); j++ {
         if arr[j] > arr[max] {
            max = j
         }
      }                     
      arr[i], arr[max] = arr[max], arr[i]
   }
   fmt.Println(arr)
}

插入排序法

原理是将 arr[i] 插入到数组前面合适的位置
和选择排序相比特性是，程序会提前终止内循环即对于极端情况(如有序数组)则复杂度为 n，而选择排序始终是 n²
对于近乎有序数组(银行处理业务)，插入排序法是更好的选择(和归并排序和快排相比)

func InsertionSort(arr []int) {
	for i := 1; i < len(arr); i++ {
		for j := i; j-1 >= 0; j-- {
			if arr[j-1] > arr[j] { //不用记录i的下标，因为比较的两个数始终是相邻的，用j-1表示即可
				arr[j], arr[j-1] = arr[j-1], arr[j]
			} else {
				break
			}
		}
	}
}

优化

func InsertionSort2(arr []int) {
   for i := 1; i < len(arr); i++ {
      //内循环优化
      for j := i; j-1 >= 0 && arr[j-1] > arr[j]; j-- {
       arr[j], arr[j-1] = arr[j-1], arr[j]
      }
   }
}

再优化

func InsertionSort2(arr []int) {
   for i := 1; i < len(arr); i++ {
      //交换元素优化为赋值元素 交换可看成是三次赋值
      var j int
      num := arr[i]
      for j = i; j-1 >= 0 && arr[j-1] > num; j-- { 
         arr[j] = arr[j-1] //每次覆盖前j前面的数字已经全部有序，只是将j插入到前面有序数组相应的位置，所以才能直接用前一个数覆盖后一个数，当遇到不能覆盖的位置时，此时再将之前保留的num放在该位置上
      }
      arr[j]=num
   }
}

冒泡排序法

func BubbleSort(arr []int) {
   for i := 0; i < len(arr)-1; i++ {
      for j := 0; j < len(arr)-i-1; j++ {
         if arr[j] > arr[j+1] {
            arr[j], arr[j+1] = arr[j+1], arr[j]
         }
      }
   }
}

优化

每次记录是否进行了冒泡操作，没有进行冒泡时说明该数组已有序

func BubbleSort2(arr []int) {
   for i := 0; i < len(arr)-1; i++ {
      isSwapped := false
      for j := 0; j < len(arr)-i-1; j++ {
         if arr[j] > arr[j+1] {
            arr[j], arr[j+1] = arr[j+1], arr[j]
            isSwapped = true
         }
      }
      if !isSwapped { //如果这一轮数组没有进行交换，说明整个数组已经有序
         break
      }
   }
}

再优化

因为i不仅表示循环的轮数，还表示数组已排好序的 i 位数

记录每次进行交换的下标

func BubbleSort3(arr []int) {
   for i := 0; i < len(arr)-1; {
      lastSwappedIndex := 0
      for j := 0; j < len(arr)-i-1; j++ {
         if arr[j] > arr[j+1] {
            arr[j], arr[j+1] = arr[j+1], arr[j]
            lastSwappedIndex = j + 1 //最后一个交换的下标
         }
      }
      i = len(arr) - lastSwappedIndex //i不仅表达的是多少轮，也表示数组最后i位以排好序
      //有了最后交换的下标，表示之后没有进行交换过，表示下标之后的已有序
   }
}

归并排序法

看复杂度就看递归树的层数

• 其复杂度是nlogn

• 采用的是分治思想

func sort(arr []int, l, r int) {
   if l >= r {
      return
   }
   mid := l+(r-l) / 2 //因为
   // l+r如果超出了32位则会有bug
   sort(arr, l, mid)
   sort(arr, mid+1, r)
   merge(arr, l, mid, r)
}

//归并排序法
func merge(arr []int, l, mid, r int) {
   temp:=make([]int,r-l+1)
   copy(temp, arr[l:r+1])
   i := l
   j := mid + 1

   //每轮循环为arr[k]赋值
   for k := l; k <= r; k++ {
      if i > mid { //如果i越界了则说明给定界限的数组前一半以前排完了，则直接将后一半剩下的数依次放入
         arr[k] = temp[j-l] //因为temp是给定界限的数组，有l的偏移量
         j++
         continue
      } else if j > r {
         arr[k] = temp[i-l]
         i++
         continue
      }
      if temp[i-l] <= temp[j-l] { //前半部分和后半部分进行比较，谁小就先放谁
         arr[k] = temp[i-l]
         i++
      } else {
         arr[k] = temp[j-l]
         j++
      }
   }
}

优化

//归并排序法的优化
func MergeSort2(arr []int) {
   temp := make([]int, len(arr)) //进行内存优化，只开一次空间，防止每次merge时的开辟空间
   copy(temp, arr)
   sort2(arr, 0, len(arr)-1, temp)
}

func sort2(arr []int, l, r int, temp []int) {
   if r-l < 15 {
      insertionSort(arr, l, r) //选择使用插入排序法，因为对于小规模的排序，插入排序法的常数小，反而耗时更少
      return
   }
   mid := l + (r-l)/2 //因为
   // l+r如果超出了32位则会有bug
   sort2(arr, l, mid, temp)
   sort2(arr, mid+1, r, temp)

   if arr[mid] > arr[mid+1] { //如果左数组的最大都比有数组最小还要小，则不需要进行并归
      merge2(arr, l, mid, r, temp)
   }
}

//归并排序法
func merge2(arr []int, l, mid, r int, temp []int) {
   copy(temp[l:r+1], arr[l:r+1])
   i := l
   j := mid + 1

   //每轮循环为arr[k]赋值
   for k := l; k <= r; k++ {
      if i > mid { //如果i越界了则说明给定界限的数组前一半以前排完了，则直接将后一半剩下的数依次放入
         arr[k] = temp[j] //此时，temp也是从l开始取，则不需要偏移量
         j++
         continue
      } else if j > r {
         arr[k] = temp[i]
         i++
         continue
      }
      if temp[i] <= temp[j] {
         arr[k] = temp[i]
         i++
      } else {
         arr[k] = temp[j]
         j++
      }
   }
}

//如果是有序数组，则merge不会执行则在递归树中，每一个叶子结点复杂度都是1，则总的复杂度为n+2/n+4/n+.... 其复杂度为n
func insertionSort(arr []int, l, r int) {
   for i := l; i <= r; i++ {
      var j int
      num := arr[i]
      for j = i; j-1 >= l && arr[j-1] > num; j-- {
         arr[j] = arr[j-1]
      }
      arr[j] = num
   }
}

​

leetcode 剑指offer51 求逆序数对个数

var Res int
func reversePairs(nums []int) int {
   Res = 0
   temp := make([]int, len(nums))
   sortLeetcode(nums, 0, len(nums)-1, temp)
   return Res
}

func sortLeetcode(arr []int, l, r int, temp []int) {
   if l >= r {
      return
   }
   mid := l + (r-l)/2
   sortLeetcode(arr, l, mid, temp)
   sortLeetcode(arr, mid+1, r, temp)
   mergeLeetcode(arr, l, mid, r, temp)
}

func mergeLeetcode(arr []int, l, mid, r int, temp []int) {
   copy(temp[l:r+1], arr[l:r+1])
   i := l
   j := mid + 1

   for k := l; k <= r; k++ {
      if i > mid {
         arr[k] = temp[j]
         j++
         continue
      } else if j > r {
         arr[k] = temp[i]
         i++
         continue
      }
      if temp[i] <= temp[j] {
         arr[k] = temp[i]
         i++
      } else {
         arr[k] = temp[j]
         Res+=mid-i+1 //在这里如果右数组j的值比i小，则说明从i到mid的数都比j大
         j++
      }
   }
}