学习Go语言第二周，本周任务尝试实现七大经典排序算法以及分析算法复杂度、优劣及应用场景等，七大经典算法分别为冒泡排序，插入排序，选择排序，希尔排序，归并排序，快速排序，堆排序。
冒泡排序
- 思路
正如“冒泡”二字，我的理解是重复依次比较相邻的两个数，大的数放在后面，小的数放在前面，一直重复到没有任何一对数字需要交换位置为止。就像冒泡一样，大的数不断浮上来。
- 伪代码
do
swapped = false
for i = 1 to indexOfLastUnsortedElement-1
if leftElement > rightElement
swap(leftElement, rightElement)
swapped = true; swapCounter++
while swapped
- Go实现
func Bubble_Sort(arr []int) {
swapped := true
len := len(arr)
for swapped {
swapped = false
for i := 0; i < len-1; i++ {
if arr[i] > arr[i+1] {
arr[i], arr[i+1] = arr[i+1], arr[i]
swapped = true
}
}
}
}
选择排序
- 思路
先假设第一个元素为最小值，然后与剩余的 len-1 个元素依次进行比较，标记最小数的位置，如果有更小的数，则在进行下一轮遍历比较之前交换位置。
- 伪代码
repeat (numOfElements - 1) times
set the first unsorted element as the minimum
for each of the unsorted elements
if element < currentMinimum
set element as new minimum
swap minimum with first unsorted position
- Go实现
func Selection_Sort(arr []int) {
len := len(arr)
for i := 0; i < len-1; i++ {
min := i
for j := i+1; j < len; j++ {
if arr[j] < arr[min] {
min = j
}
}
arr[min], arr[i] = arr[i], arr[min]
}
}
插入排序
思路
这个排序感觉和选择排序的思路有点相似的。首先1个长度的数组肯定是有序的，假设数组的长度为n，第一位是有序的，然后从第二位开始在已排序序列中从后向前扫描，找到相应位置并插入。伪代码
mark first element as sorted
for each unsorted element X
'extract' the element X
for j = lastSortedIndex down to 0
if current element j > X
move sorted element to the right by 1
break loop and insert X here
- Go实现
func Insertion_Sort(arr []int) {
len := len(arr)
for i := 0; i < len; i++ {
selected := arr[i]
for j := i-1; j >= 0; j-- {
if arr[j] > selected {
arr[j], arr[j+1] = arr[j+1], arr[j]
} else {
arr[j+1] = selected
break
}
}
}
}
归并排序
- 思路
归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。先考虑合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。再考虑递归分解，基本思路是将数组分解成left和right，如果这两个数组内部数据是有序的，那么就可以用上面合并数组的方法将这两个数组合并排序。如何让这两个数组内部是有序的？可以再二分，直至分解出的小组只含有一个元素时为止，此时认为该小组内部已有序。然后合并排序相邻二个小组即可。（摘抄）
- 伪代码
split each element into partitions of size 1
recursively merge adjancent partitions
for i = leftPartStartIndex to rightPartLastIndex inclusive
if leftPartHeadValue <= rightPartHeadValue
copy leftPartHeadValue
else: copy rightPartHeadValue; Increase InvIdx
copy elements back to original array
- Go实现
func Merge_Sort(arr []int) []int{
if len(arr) <= 1 {
return arr
}
var middle int = len(arr)/2
left := Merge_Sort(arr[:middle])
right := Merge_Sort(arr[middle:])
return merge(left, right)
}
func merge(a, b []int) []int {
alen, blen := len(a), len(b)
var z []int = make([]int, alen + blen)
k := 0//数组切片z的下标
i, j := 0, 0//a、b起始下标均未0
for i < alen && j < blen {
if a[i] < b[j] {
z[k] = a[i]
i++
} else {
z[k] = b[j]
j++
}
k++
}
for i != alen {
z[k] = a[i]
k++
i++
}
for j != blen {
z[k] = b[j]
k++
j++
}
return z
}
快速排序
- 思路
快速排序可能是当前应用最广泛的排序算法。快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n)算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。快速排序引人注目的特点包括它是原地排序（只需要一个很小的辅助栈）。
该方法的基本思想是：1．先从数列中取出一个数作为基准数。2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。3．再对左右区间重复第二步，直到各区间只有一个数。
- 伪代码
for each (unsorted) partition
set first element as pivot
storeIndex = pivotIndex + 1
for i = pivotIndex + 1 to rightmostIndex
if element[i] < element[pivot]
swap(i, storeIndex); storeIndex++
swap(pivot, storeIndex - 1)
- Go实现
func Quick_Sort(arr []int) {
sort(arr, 0, len(arr)-1)
}
func sort(arr []int, left int, right int) {
if right <= left {
return
}
p := partition(arr, left, right)//快速排序切分
sort(arr, left, p-1)
sort(arr, p+1, right)
}
func partition(arr []int, left int, right int) int {
pivot := arr[left]
i, j := left, right+1
for true {
for i++; arr[i] < pivot; i++ {
if i==right {
break
}
}
for j--; pivot < arr[j]; j-- {
if j==left {
break
}
}
if i>=j {
break
}
arr[i], arr[j] = arr[j], arr[i]
}
arr[left], arr[j] = arr[j], arr[left]
return j
}
希尔排序
- 思路
希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。希尔排序是基于插入排序的以下两点性质而提出改进方法的：1. 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率2. 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
- Go实现
func Shell_Sort(arr []int) {
N := len(arr)
var gap int = N/2 //初始步长
for gap > 0 {
for i := gap; i < N; i++ { //每一列进行插入排序 , 从gap 到 n-1
temp := arr[i]
j := i
for j>=gap && arr[j-gap]>temp { //插入排序
arr[j] = arr[j-gap]
j = j-gap
}
arr[j] = temp
}
gap = gap/2 //重新设置步长
}
}
堆排序
堆排序是一种选择排序，其时间复杂度为O(nlogn)
- 堆的定义
n个元素的序列{k1，k2，…,kn}当且仅当满足下列关系之一时，称之为堆。 情形1：ki <= k2i 且ki <= k2i+1 （最小化堆或小顶堆） 情形2：ki >= k2i 且ki >= k2i+1 （最大化堆或大顶堆） 其中i=1,2,…,n/2向下取整;
若将和此序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。
例如，下列两个序列为堆，对应的完全二叉树如图：
若在输出堆顶的最小值之后，使得剩余n-1个元素的序列重又建成一个堆，则得到n个元素的次小值。如此反复执行，便能得到一个有序序列，这个过程称之为堆排序。堆排序（Heap Sort）只需要一个记录元素大小的辅助空间（供交换用），每个待排序的记录仅占有一个存储空间。
- 堆的存储
一般用数组来表示堆，若根结点存在序号0处， i结点的父结点下标就为(i-1)/2。i结点的左右子结点下标分别为2i+1和2i+2。（注：如果根结点是从1开始，则左右孩子结点分别是2i和2i+1。）如第0个结点左右子结点下标分别为1和2。如最大化堆如下：左图为其存储结构，右图为其逻辑结构。
- 堆的排序实现
- 构造最大堆（Build_Max_Heap）：若数组下标范围为0~n，考虑到单独一个元素是大根堆，则从下标n/2开始的元素均为大根堆。于是只要从n/2-1开始，向前依次构造大根堆，这样就能保证，构造到某个节点时，它的左右子树都已经是大根堆。2. 堆排序（HeapSort）：由于堆是用数组模拟的。得到一个大根堆后，数组内部并不是有序的。因此需要将堆化数组有序化。思想是移除根节点，并做最大堆调整的递归运算。第一次将heap[0]与heap[n-1]交换，再对heap[0...n-2]做最大堆调整。第二次将heap[0]与heap[n-2]交换，再对heap[0...n-3]做最大堆调整。重复该操作直至heap[0]和heap[1]交换。由于每次都是将最大的数并入到后面的有序区间，故操作完后整个数组就是有序的了。3. 最大堆调整（Max_Heapify）：该方法是提供给上述两个过程调用的。目的是将堆的末端子节点作调整，使得子节点永远小于父节点 。
- Go实现
func Heap_Sort(arr []int) {
N := len(arr)
var first int = N/2 //最后一个非叶子节点
for start := first; start > -1; start-- { //构造大根堆
max_heapify(arr, start, N-1)
}
for end := N-1; end > 0; end-- { //堆排，将大根堆转换成有序数组
arr[end],arr[0] = arr[0],arr[end]
max_heapify(arr, 0, end-1)
}
}
func max_heapify(arr []int, start int, end int) {
root := start
for true {
child := root*2 + 1 //调整节点的子节点
if child > end {
break
}
if child + 1 <= end && arr[child] < arr[child+1] {
child = child + 1 //取较大的子节点
}
if arr[root] < arr[child] {
arr[root], arr[child] = arr[child], arr[root] //较大的子节点成为父节点
root = child
} else {
break
}
}
}
七种经典排序算法指标对比
参考资料
可视化排序动态图](https://visualgo.net/en/sorting))
经典排序算法总结与实现 (Python实现)
堆排序 Heap Sort
算法(中文版•第4版)
