golang int切片排序

一、归并排序

• 原理：如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。归并排序使用的就是分治思想。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。

• 适合大规模的数据排序(冒泡排序、插入排序、选择排序、它们的时间复杂度都是 O(n2)，比较高，适合小规模数据的排序)
• 性能分析：
  (1) 归并排序是一个稳定的排序算法。
  (2) 时间复杂度是 O(nlogn)。
  (3) 不是原地排序算法，空间复杂度是 O(n) 较高。

// 归并排序降序// golang 语言实现func mergeSort(r []int) []int {length := len(r)if length <= 1 {return r}num := length / 2left := mergeSort(r[:num])right := mergeSort(r[num:])return merge(left, right)}func merge(left, right []int) (result []int) {l, r := 0, 0for l < len(left) && r < len(right) {if left[l] < right[r] {result = append(result, left[l])l++} else {result = append(result, right[r])r++}}result = append(result, left[l:]...)result = append(result, right[r:]...)return}

二、快速排序

• 原理：
  (1)先从数列中取出一个数作为基准数。
  (2)分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
  (3)再对左右区间重复第二步，直到各区间只有一个数。
• 适合大规模的数据排序
• 性能分析：
  (1)时间复杂度也是 O(nlogn)。
  (2)快排是一种原地排序算法，空间复杂度是O(1)。

• 排序流程：快速排序算法通过多次比较和交换来实现排序，其排序流程如下：
  (1)首先设定一个分界值，通过该分界值将数组分成左右两部分。
  (2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
  (3) 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
  (4) 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

// 第一种写法func quickSort(values []int, left, right int) {temp := values[left]p := lefti, j := left, rightfor i <= j {for j >= p && values[j] >= temp {j--}if j >= p {values[p] = values[j]p = j}for i <= p && values[i] <= temp {i++}if i <= p {values[p] = values[i]p = i}}values[p] = tempif p-left > 1 {quickSort(values, left, p-1)}if right-p > 1 {quickSort(values, p+1, right)}}func QuickSort(values []int) {if len(values) <= 1 {return}quickSort(values, 0, len(values)-1)}// 第二种写法func Quick2Sort(values []int) {if len(values) <= 1 {return}mid, i := values[0], 1head, tail := 0, len(values)-1for head < tail {fmt.Println(values)if values[i] > mid {values[i], values[tail] = values[tail], values[i]tail--} else {values[i], values[head] = values[head], values[i]head++i++}}values[head] = midQuick2Sort(values[:head])Quick2Sort(values[head+1:])}// 第三种写法func Quick3Sort(a []int, left int, right int) {if left >= right {return}explodeIndex := leftfor i := left + 1; i <= right; i++ {if a[left] >= a[i] {//分割位定位++explodeIndex++a[i], a[explodeIndex] = a[explodeIndex], a[i]}}//起始位和分割位a[left], a[explodeIndex] = a[explodeIndex], a[left]Quick3Sort(a, left, explodeIndex-1)Quick3Sort(a, explodeIndex+1, right)}

三、归并排序与快速排序的区别

• 归并和快排用的都是分治思想，递推公式和递归代码也非常相似
• 归并排序，是先递归调用，再进行合并，合并的时候进行数据的交换。所以它是自下而上的排序方式。何为自下而上？就是先解决子问题，再解决父问题。
• 快速排序，是先分区，在递归调用，分区的时候进行数据的交换。所以它是自上而下的排序方式。何为自上而下？就是先解决父问题，再解决子问题。

下一节：数据结构与算法-桶排序-计数排序-基数排序-11

上一节：数据结构与算法-冒泡排序-插入排序-选择排序-9