排序算法
所谓的排序算法就是将一串记录，依照递增或递加的顺序排列起来。
通常提到的一共有十种排序：冒泡、抉择、插入、疾速、归并、堆、希尔、计数、桶、基数
- 比拟类排序：通过比拟来决定元素间的绝对秩序，通常其工夫复杂度不能冲破
O(nlogn)，因而又称为非线性工夫比拟类排序。 - 非比拟类排序：不通过比拟元素间的绝对秩序，能够冲破基于比拟排序的工夫上限，以线性工夫运行，因而又称为线性工夫非比拟类排序。
工夫复杂度：
| 排序办法 | 工夫复杂度(均匀) | 工夫复杂度(最坏) | 工夫复杂度(最好) | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n^2^) | O(n^2^) | O(n) | O(1) | 稳固 |
| 抉择排序 | O(n^2^) | O(n^2^) | O(n^2^) | O(1) | 不稳固 |
| 插入排序 | O(n^2^) | O(n^2^) | O(n) | O(1) | 稳固 |
| 疾速排序 | O(nlogn) | O(n^2^) | O(nlogn) | O(nlogn) | 不稳固 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳固 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳固 |
| 希尔排序 | O(n^1.3^) | O(n^2^) | O(n) | O(1) | 稳固 |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(n+k) | 稳固 |
| 桶排序 | O(n+k) | O(n^2^) | O(n) | O(n+k) | 稳固 |
| 基数排序 | O(n*k) | O(n*k) | O(n*k) | O(n+k) | 稳固 |
稳定性：如果 a =b，并且 a 在 b 的后面，排序后 a 肯定在 b 的后面，那么称算法是稳固的，如果不肯定在后面，那么称算法是不稳固的。
冒泡排序
冒泡排序 (Bubble Sort) 是一种简略直观的排序算法。它反复地拜访要排序的数列，一次比拟两个元素，如果程序谬误就调换程序。走访数列的工作是反复地进行领导没有再须要元素替换，也就是说该数列曾经排序实现。因为越小的元素会通过替换缓缓地达到顶端，就像泡泡一样会上浮，所以称为冒泡排序。
1、算法步骤
1、比拟相邻的元素，如果第一个比第二个大，就替换它们。
2、对每一对相邻元素做同样的工作，从开始第一对到结尾的最初一对，这步做完后，开端元素是最大的元素。
3、针对所有的元素反复以上步骤，除了最初一个元素
4、反复步骤1~3，直到没有任意一对元素须要比拟。
2、动画演示
3、状况
最好状况：数列是正序，只须要遍历一遍，工夫复杂度最好为 O(n)。
最坏状况：数列是倒序，每一对都须要进行比拟，工夫复杂度最坏为 O(n^2^)。
工夫复杂度均匀为 O(n^2^)，空间复杂度为 O(1)，是稳固排序。
4、Golang 实现
func bubbleSort(arr []int) {n := len(arr)
for i := 0; i < n-1; i++ {
for j := i + 1; j < n; j++ {if arr[i] > arr[j] {arr[i], arr[j] = arr[j], arr[i]
}
}
}
}抉择排序
抉择排序 (Selection Sort) 是一种简略直观的排序算法。它的工作原理是：首先在序列中找到最小元素，放在序列的首位，而后再从剩下的序列中寻找最小元素，放到已排序序列的开端。
1、算法步骤
1、首先在未排序序列中找到最小元素，寄存到排序序列的起始地位
2、再从残余未排序序列中持续寻找最小元素，寄存到排序序列的开端
3、反复第 2 步，直到所有元素排序结束。
2、动画演示
3、状况
工夫复杂度为 O(n^2^)，因为无论如何都须要遍历序列找到最小值，所以最好和最坏都是 O(n^2^)。
空间复杂度为 O(n^2^)，是不稳固排序。
4、Golang 实现
func selectionSort(arr []int) {for i := 0; i < len(arr); i++ {
min := i
for j := i + 1; j < len(arr); j++ {if arr[j] < arr[min] {min = j}
}
arr[min], arr[i] = arr[i], arr[min]
}
}插入排序
插入排序 (Insertion Sort) 是一种简略直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列由后向前扫描，找到相应地位并插入。
1、算法步骤
1、把第一个元素看成一个有序序列，把第二个元素到最初一个元素看成一个未排序序列。
2、从头扫描，将扫描到的每个元素插入有序序列的适当地位。
2、动画演示
3、状况
最坏状况：每一个待插入的元素都须要插入到序列首位，即原序列是倒序序列，工夫复杂度为 O(n^2^)。
最好状况：每一个待插入的元素都须要插入到序列末位，即原序列是正序序列，工夫复杂度为 O(n)。
工夫复杂度均匀为 O(n^2^)，空间复杂度为 O(1) 是稳固排序。
4、Golang 实现
func insertionSort(arr []int) {for i := 1; i < len(arr); i++ {current := arr[i]
preIndex := i - 1
for ; preIndex >= 0 && current < arr[preIndex]; preIndex-- {arr[preIndex+1] = arr[preIndex]
}
arr[preIndex+1] = current
}
}疾速排序
疾速排序 (Quick Sort) 是通过一趟排序将待排记录分隔成独立的两局部，其中一部分的关键字比另一部分的关键字小，则可别离对这两局部记录持续进行排序，直到整个序列有序。
1、算法步骤
1、从序列中挑出一个元素，作为基准。
2、重新排列数列，所有元素比基准小的放在基准后面，所有元素比基准大的放在基准前面。
3、递归地把小于基准元素的子序列和大于基准元素的子序列排序。
2、动画演示
3、状况
工夫复杂度均匀为 O(nlogn)，空间复杂度为 O(nlogn)，是不稳固排序。
4、Golang 实现
归并排序
归并排序 (Merge Sort) 是建设在归并操作上的一种无效排序算法，采纳了分而治之的思维。
1、算法步骤
1、把长度为 n 的序列分为两个长度为 n / 2 的子序列。
2、对这两个子序列别离采纳归并排序。
3、将两个排序好的子序列合并成一个最终的排序序列。
2、动画演示
3、状况
工夫复杂度为 O(nlogn)，空间复杂度为 O(n)，是稳固排序办法。
4、Golang 实现
func mergeSort(nums []int, start,end int) {
if start < end {mid := (start+end)/2
mergeSort(nums,start,mid) // 右边排序
mergeSort(nums,mid+1,end) // 左边排序
merge(nums,start,mid,end) // 合并数组
}
}
func merge(nums []int, start, mid, end int) {
i,j := start,mid+1
ret := []int{}
for i <= mid && j <= end {if nums[i] <= nums[j] {ret = append(ret, nums[i])
i++
} else {ret = append(ret, nums[j])
j++
}
}
ret = append(ret, nums[i:mid+1]...)
ret = append(ret, nums[j:end+1]...)
for k, v := range ret {nums[start+k] = v
}
}堆排序
堆排序 (Heap Sort) 是指利用堆这种数据结构所设计的一种排序算法。堆是一种近似于齐全二叉树的构造，并同时满足沉积的性质：子节点的键值或索引总小于 (或大于) 父节点。
大根堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
小根堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
1、算法步骤
1、将待排序列构建成一个堆 H[0……n-1]，依据 (升序降序) 抉择大根堆或小跟堆。
2、把堆顶和堆尾调换。
3、把堆的尺寸放大 1，并调用 shift_down(0)，目标是把新的数组顶端数据调整到相应地位；
4、反复步骤 2，直到堆的尺寸为 1。
2、动画演示
3、状况
工夫复杂度均匀为 O(nlogn)，空间复杂度 O(1)，是不稳固排序。
4、Golang 实现
func heapSort(arr []int) []int {arrLen := len(arr)
buildMaxHeap(arr, arrLen)
for i := arrLen - 1; i >= 0; i-- {swap(arr, 0, i)
arrLen -= 1
heapify(arr, 0, arrLen)
}
return arr
}
func buildMaxHeap(arr []int, arrLen int) {
for i := arrLen / 2; i >= 0; i-- {heapify(arr, i, arrLen)
}
}
func heapify(arr []int, i, arrLen int) {
left := 2*i + 1
right := 2*i + 2
largest := i
if left < arrLen && arr[left] > arr[largest] {largest = left}
if right < arrLen && arr[right] > arr[largest] {largest = right}
if largest != i {swap(arr, i, largest)
heapify(arr, largest, arrLen)
}
}
func swap(arr []int, i, j int) {arr[i], arr[j] = arr[j], arr[i]
}希尔排序
希尔排序是插入排序的改良版本，与插入排序不同之处在于，它会优先比拟间隔较远的元素，又称 放大增量排序。
根本思维是：先将整个待排序的序列宰割成若干个子序列别离进行插入排序，待整个序列“根本有序”时，在顺次进行插入排序。
1、算法步骤
1、抉择一个增量序列 t1,t2, ……, tk，其中 ti > tj，tk=1;
2、按增量序列个数 k，对序列进行 k 趟排序
3、每趟排序，依据对应的增量 ti，将待排序宰割成若干长度为 m 的子序列，别离对各子表进行间接插入排序。当增量因子为 1 时，整个序列作为一个表来解决，表长度即为整个序列的长度。
2、动画演示
3、Golang 实现
func shellSort(arr []int) {n := len(arr)
for step := n / 2; step >= 1; step /= 2 {
for i := step; i < n; i += step {
for j := i - step; j >= 0; j -= step {if arr[j] > arr[j+step] {arr[j], arr[j+step] = arr[j+step], arr[j]
continue
}
break
}
}
}
}计数排序
计数排序 (Counting Sort) 不是基于比拟的排序算法，其外围在于将输出的数据值转化为键存储在额定开拓的数组空间中。作为一种线性工夫复杂度的排序，计数排序要求输出的数据必须是有确定范畴的整数。
1、算法步骤
1、找出原数组中元素最大值，记为 max。
2、创立一个新数组 count，其长度是 max+1，其元素默认为 0。
3、遍历原数组中的元素，以原数组中的元素作为 count 数组的索引，以原数组中呈现的元素次数作为 count 数组的元素值。
4、创立后果数组 result，起始索引 index。
5、遍历 count 数组，找出其中元素值大于 0 的元素，将其对应的索引作为元素值填充到 result 数组中去，每解决一次，count 中的该元素值减 1，直到该元素值不大于 0，顺次解决 count 中剩下的元素。
6、返回后果数组 result。
2、动画演示
3、状况
工夫复杂度为 O(n+k)，空间复杂度为 O(n+k)，是稳固排序。
4、Golang 实现
func countingSort(arr []int, maxVal int) {
n := maxVal+1
nums := make([]int,n)
var sortedIndex int
for i := 0; i < len(arr); i++ {nums[arr[i]]++
}
for i := 0; i < n; i++ {for nums[i] > 0 {arr[sortedIndex] = i
sortedIndex++
nums[i]--
}
}
}桶排序
桶排序 (Bucket Sort) 是计数排序的升级版，利用函数的映射关系，高效与否的关键在于映射函数的确定。假如输出数据遵从均匀分布，将数据分到无限数量的桶里，每个桶再别离排序（有可能再应用别的排序算法或是以递归形式持续应用桶排序进行排）。
1、算法步骤
1、设置一个定量的数组当做空桶。
2、遍历数据，并且把数据一个个放入到对应的桶中。
3、对每个不是空桶进行排序。
4、从不是空桶里把排好序的数据拼接起来。
2、动画演示
3、状况
最好状况：当输出的数据平均调配到每个桶中，工夫复杂度为 O(n)。
最坏状况：输出的数据被调配到同一个桶中，工夫复杂度 O(n^2^)。
工夫复杂度均匀为 O(n+k)，空间复杂度为 O(n+k)，是稳固排序算法。
4、Golang 实现
func quickSort(nums []int, start, end int) []int {
if start < end {
i, j := start, end
key := nums[(start+end)/2]
for i <= j {for nums[i] < key {i++}
for nums[j] > key {j--}
if i <= j {nums[i], nums[j] = nums[j], nums[i]
i++
j--
}
}
if start < j {nums = quickSort(nums, start, j)
}
if end > i {nums = quickSort(nums, i, end)
}
}
return nums
}
func bucketSort(nums []int, bucketNum int) []int {bucket := [][]int{}
for i := 0; i < bucketNum; i++ {tmp := make([]int, 1)
bucket = append(bucket, tmp)
}
// 将数据调配到桶中
for i := 0; i < len(nums); i++ {bucket[nums[i]/bucketNum] = append(bucket[nums[i]/bucketNum], nums[i])
}
// 循环所有的桶进行排序
index := 0
for i := 0; i < bucketNum; i++ {if len(bucket[i]) > 1 {
// 对每个桶外部进行排序, 应用快排
bucket[i] = quickSort(bucket[i], 0, len(bucket[i])-1)
for j := 1; j < len(bucket[i]); j++ {
// 去掉一开始的 tmp
nums[index] = bucket[i][j]
index++
}
}
}
return nums
}基数排序
基数排序 (Radix Sort) 的原理是依照整数位数切割成不同的数字，而后按每个位数别离比拟。
而后咱们发现，计数排序、桶排序、基数排序都用到了桶的概念。
- 计数排序：每个桶只存单一键值
- 基数排序：依据键值的每位数字来调配桶
- 桶排序：每个桶存储肯定范畴的数值
1、算法步骤
1、获得数组中的最大数，并获得位数
2、arr 为原始数组，从最低位开始取个位组成 radix 数组
3、对 radix 进行计数排序
2、动画演示
3、状况
工夫复杂度为 O(n*k)，空间复杂度为 O(n+k)，是稳固排序算法。
4、Golang 实现
func RadixSort(arr[] int) []int{if len(arr)<2{return arr}
maxl:=MaxLen(arr)
return RadixCore(arr,0,maxl)
}
func RadixCore(arr []int,digit,maxl int) []int{
if digit>=maxl{return arr}
radix:=10
count:=make([]int,radix)
bucket:=make([]int,len(arr))
for i:=0;i<len(arr);i++{count[GetDigit(arr[i],digit)]++
}
for i:=1;i<radix;i++{count[i]+=count[i-1]
}
for i:=len(arr)-1;i>=0;i--{d:=GetDigit(arr[i],digit)
bucket[count[d]-1]=arr[i]
count[d]--
}
return RadixCore(bucket,digit+1,maxl)
}
func GetDigit(x,d int) int{a:=[]int{1,10,100,1000,10000,100000,1000000}
return (x/a[d])%10
}
func MaxLen(arr []int) int{
var maxl,curl int
for i:=0;i<len(arr);i++{curl=len(strconv.Itoa(arr[i]))
if curl>maxl{maxl=curl}
}
return maxl
}