一、归并排序

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

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

归并排序过程图解

归并排序降序golang语言实现

 // 归并排序降序
// golang 语言实现
func mergeSort(r []int) []int {
length := len(r)
if length <= 1 {
return r
}
num := length / 2
left := mergeSort(r[:num])
right := mergeSort(r[num:])
return merge(left, right)
}

func merge(left, right []int) (result []int) {
l, r := 0, 0
for 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） 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

快速排序过程图解

快速排序降序第一种写法golang语言实现

快速排序降序第二种写法golang语言实现

快速排序降序第三种写法golang语言实现

 
// 第一种写法
func quickSort(values []int, left, right int) {
temp := values[left]
p := left
i, j := left, right

for 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] = temp
if 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], 1
head, tail := 0, len(values)-1
for 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] = mid
Quick2Sort(values[:head])
Quick2Sort(values[head+1:])
}

// 第三种写法
func Quick3Sort(a []int, left int, right int) {

if left >= right {
return
}

explodeIndex := left

for 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)

}
  

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

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

下一节：

上一节：