算法-排序详解

前言

比较排序

选择排序

插入排序

冒泡排序

归并排序

快速排序

非比较类排序

计数排序

桶排序

基数排序

排序的稳定性

排序算法的题目

前言

计算机的工作之一就是对数据的处理，处理数据有一个常见的操作就是对数据排序，比如新闻系统总是按时间把最新的新闻推荐给我们，比如说以前我们讲到的二分查找，他也是基于数据的有序性。在这里我将详细讲解排序算法，下面是对排序算法的总结。

比较排序

选择排序

每次循环都从未排序数据中找到最小值，放到已排序序列的末尾，时间复杂度是O(N2)

func search(num []int) []int {
  len_num := len(num)
  copy_nums := make([]int, len_num)
  copy(copy_nums, num)
  for i := 0; i < len_num; i++ {
    minindex := i
    for j := i + 1; j < len_num; j++ {
      if copy_nums[minindex] > copy_nums[j] {
        minindex = j
      }
    }
    copy_nums[i], copy_nums[minindex] = copy_nums[minindex], copy_nums[i]
  }
  return copy_nums
}

插入排序

从前到后依次考虑每个未排序数据，在已排序序列中找到合适位置插入. 时间复杂度是O(N2)

func search(num []int) []int {
    len_num := len(num)
    copy_nums := make([]int, len_num)
    copy(copy_nums, num)
    for i := 1; i < len_num; i++ {
       for j := i; j > 0; j-- {
          if copy_nums[j] < copy_nums[j-1] {
             copy_nums[j], copy_nums[j-1] = copy_nums[j-1], copy_nums[j]
          }
       }
    }
    return copy_nums
}

我们在来看一个优化版本，这个不是最优的，每次发现满足条件的，都会进行一次交换。那我们能不能想到，找到最终满足条件的在交换了，那么我们就有一个优化版本。

func search(num []int) []int {
  len_num := len(num)
  copy_nums := make([]int, len_num)
  copy(copy_nums, num)
  for i := 1; i < len_num; i++ {
    temp := copy_nums[i]
    var j int
    for j = i; j > 0 && copy_nums[j-1] > temp; j-- {
      copy_nums[j] = copy_nums[j-1]
    }
    copy_nums[j] = temp

  }
  return copy_nums
}

这个效率高些，不用频繁的交换，选择排序在某些情况下，比如说数据近似有序以及数据规模小的情况下，甚至比快排还要高效。

冒泡排序

不断循环扫描，每次查看相邻的元素, 时间复杂度是O(N2)

func search(num []int) []int {
  len_num := len(num)
  copy_nums := make([]int, len_num)
  copy(copy_nums, num)
  for i := 0; i < len_num; i++ {
    for j := 0; j < len_num-1; j++ {
      if copy_nums[j] > copy_nums[j+1] {
        copy_nums[j], copy_nums[j+1] = copy_nums[j+1], copy_nums[j]
      }
    }

  }
  return copy_nums
}

以上三种排序时间复杂度都是O(N2)，选择排序是每次选择最小的一个，冒泡排序外层表示循环次数，两个数据的比较

归并排序

归并排序是一种基于分治的算法，时间复杂度是O(NlogN)，也就分成两部分，分开排序，再合并, 时间复杂度是O(nlogn)

func search(num []int, l, r int) {
  if l >= r {
    return
  }
  mid := (l + r) >> 1
  search(num, l, mid)
  search(num, mid+1, r)
  merge_sort(num, l, mid, r)
}

func merge_sort(num []int, l, mid, r int) {
  temp := []int{}
  //这个是分治的数组然后去比较，然后替换原始数据，就替换完成了
  for i := l; i <= r; i++ {
    temp = append(temp, num[i])
  }
  i, j := l, mid+1
  for k := l; k <= r; k++ {
    if i > mid {
      num[k] = temp[j-l]
      j++
    } else if j > r {
      num[k] = temp[i-l]
      i++
    } else if temp[i-l] >= temp[j-l] {
      num[k] = temp[j-l]
      j++
    } else if temp[i-l] < temp[j-l] {
      num[k] = temp[i-l]
      i++
    }
  }

}

func main() {
  num := []int{}
  for i := 0; i < 10; i++ {
    num = append(num, rand.Intn(30))
  }
  search(num, 0, len(num)-1)
  fmt.Println(num)
}

快速排序

在这里我将写的是三路快排，也就是说左边部分是比基准数据小，中间部分是和基准数据一样大，右边部分是比基准数据大。那么中间部分就不用排序了，左右两边在分别排序，这样也就减少了，数据比较规模. 时间复杂度是O(nlogn)

func quickSort(num []int, l, r int) {
  if l >= r {
    return
  }
  v := num[l]
  lt := l     //[l,lt)
  gt := r + 1 // [gt,r]
  //中间与v相等的数据是 [lt,gt),这部分数据是不用比较
  i := l + 1
  for i < gt {
    if v > num[i] {
      num[lt+1], num[i] = num[i], num[lt+1]
      i++
      lt++
    } else if v < num[i] {
      num[gt-1], num[i] = num[i], num[gt-1]
      gt--
    } else {
      i++
    }
  }
  num[lt], num[l] = num[l], num[lt]
  quickSort(num, l, lt-1)
  quickSort(num, gt, r)
}

非比较类排序

计数排序

计数排序要求输入的数据必须是有确定范围的整数。将输入的数据作为key 存储在额外的数组中，然后依次把计数大于1的填充会原数组

时间复杂度是O(N+M) ,N 为元素个数，M为数值范围

桶排序

桶排序假设输入数据服从均衡分布，将数据分到有限的数据的桶里，应先根据数据的规模确定桶的数量，在把数据放到桶里比如可以通过取模的方式，每个桶先分别排序，把排好序的桶的数据合并在排序

时间复杂度O(N) ~ O(N^2)

基数排序

基数排序把数据切割成一位位数字（0-9），从低位到高位对每一位分别进行计数排序

时间复杂度是O(NK),k 为数字位数

排序的稳定性

什么是排序算法的稳定性呢，如果排序前后它们的相对次序一定保持不变，就称排序算法是稳定的否则就称排序算法是不稳定的

稳定的排序算法：插入、冒泡、归并、计数、桶

不稳定的排序：选择、希尔、快速、堆排序

如果大家想检测自己的排序算法是否正确可以看leadcode 912

排序算法的题目

leadcode 1122

给你两个数组，arr1 和 arr2，arr2 中的元素各不相同，arr2 中的每个元素都出现在 arr1 中。

对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

示例 1：

输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]

比较排序时间复杂度是O(nlogn)

func relativeSortArray(arr1 []int, arr2 []int) []int {
  arr2_map := map[int]int{}
  for i, v := range arr2 {
    arr2_map[v] = i
  }
  sort.Slice(arr1, func(i, j int) bool {
    n1, n2 := 0,0
    var ok bool
    if n1, ok = arr2_map[arr1[i]]; !ok {
      n1 = len(arr2)
    }
    if n2,ok = arr2_map[arr1[j]];!ok{
      n2 = len(arr2)
    }
    return n1 < n2 || (n1 == n2 && arr1[i] < arr1[j])

  })
  return arr1
}

除了这种方法，还可以用计数排序，方法也非常简单，arr1 统计每个数据的个数，然后根据arr2 在 arr1 中找到相应的数据，然后在arr1把计数>0 的数据依次找出来。这种排序算法是O(N)。这个要根据数据规模

func relativeSortArray(arr1 []int, arr2 []int) []int {
  arr1_map := map[int]int{}
  for _, v := range arr1 {
    arr1_map[v]++
  }
  ans := []int{}
  for _, v := range arr2 {
    for arr1_map[v] > 0 {
      ans = append(ans, v)
      arr1_map[v]--

    }
  }
  for i:=0;i<10001;i++{
    for arr1_map[i] > 0 {
      ans = append(ans, i)
      arr1_map[i]--

    } 
  }

  return ans
}

Leadcode 56

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

这是比较排序的算法，记录上一个left，right ，我们的变量是start,end,如果本次的left小于end 那么就要想叫，取right 最大值，这是这个算法的思想，还是比较简单的

func merge(intervals [][]int) [][]int {
  sort.Slice(intervals, func(i, j int) bool {
    return intervals[i][0] < intervals[j][0] || (intervals[i][0] == intervals[j][0] && intervals[i][1] < intervals[j][1])
  })
  ans := [][]int{}
  start, end := -1, -1
  for _, v := range intervals {
    left, right := v[0], v[1]
    if left <= end {
      end = max(right, end)
    } else {
      if end != -1 {
        ans = append(ans, []int{start, end})
      }
      start = left
      end = right
    }
  }
  ans = append(ans, []int{start, end})
  return ans
}

func max(i, j int) int {
  if i >= j {
    return i
  }
  return j
}

还可以用差分思想，就是把区间的变化变成一个个事件，思想是这样的

把每个区间 [l,r] 看作一次+1 的覆盖，进一步转化为 “l处+1”、“r+1处-1” 两个事件，把这个事件排序，扫描，用一个计数变量覆盖次数，0 变1 、1 变0 时找到了合并后的区间端点

func merge(intervals [][]int) [][]int {
  event := [][]int{}
  for _, v := range intervals {
    event = append(event, []int{v[0], 1})
    event = append(event, []int{v[1] + 1, -1})
  }
  sort.Slice(event, func(i, j int) bool {
    return event[i][0] < event[j][0] || (event[i][0] == event[j][0] && event[i][1] < event[j][1])
  })
  fmt.Println(event)
  ans := [][]int{}
  conver := 0
  start := 0
  for _, v := range event {
    if conver == 0 {
      start = v[0]
    }
    conver += v[1]
    if conver == 0 {
      ans = append(ans, []int{start, v[0] - 1})
    }
  }
  return ans
}