10种排序：
- 冒泡排序（Bubble Sort）
- 选择排序（Selection Sort）
- 插入排序（Insertion Sort）
- 希尔排序（Shell Sort）
- 快速排序（Quick Sort）
- 归并排序（Merge Sort）
- 计数排序（Counting Sort）
- 基数排序（Radix Sort）
- 堆排序（Heap Sort）
- 桶排序（Bucket Sort）
冒泡排序（Bubble Sort）
// BubbleSort
// 冒泡排序
// 时间复杂度: 平均O(N^2) 最好O(N) 最坏O(N^2)
// 空间复杂度: O(1)
// 稳定性：稳定
// 基本步骤：顾名思义，每次排序都会遍历数组找一个最大值（最小值）上升（冒泡）到右边（左边），这个最大值的位置就确定了。
// 然后对剩余未确定的部分重复冒泡操作。
func BubbleSort(arr []int){
n := len(arr)
for i:=0;i<n;i++{
for j:=0;j<n-i-1;j++{
if arr[j]>arr[j+1]{
arr[j],arr[j+1] = arr[j+1],arr[j]
}
}
}
}选择排序（Selection Sort）
// SelectionSort
// 选择排序
// https://zh.wikipedia.org/zh-cn/选择排序
// 时间复杂度: 平均O(N^2) 最好O(N^2) 最坏O(N^2)
// 空间复杂度: O(1)
// 稳定性：不稳定
// 基本步骤：
// 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
// 然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
// 以此类推，直到所有元素均排序完毕。
// 交换次数比冒泡排序较少，由于交换所需CPU时间比比较所需的CPU时间多，
// n值较小时，选择排序比冒泡排序快。
// 原地操作几乎是选择排序的唯一优点，当空间复杂度要求较高时，可以考虑选择排序；实际适用的场合非常罕见。
func SelectionSort(arr []int) {
var i,j,min int
for i=0;i<len(arr);i++{
min = i
// 找到最小值
for j = i+1;j<len(arr);j++{
if arr[min] > arr[j]{
min = j
}
}
if min != i{
arr[min],arr[i] = arr[i],arr[min]
}
}
}插入排序（Insertion Sort）
// InsertionSort
// 插入排序
// https://zh.wikipedia.org/zh-cn/插入排序
// 时间复杂度: 平均O(N^2) 最好O(N) 最坏O(N^2)
// 空间复杂度: O(1)
// 稳定性：稳定
// 对于少量元素的排序，它是一个有效的算法。
// 基本步骤：
// 插入排序：把元素分为已排序的和未排序的。每次从未排序的元素取出第一个保存到临时变量a，
// 然后在，已排序中的元素中从右往左依次把比a大的元素往后移动一个位置，最后把a填入移动后留下的空位。
func InsertionSort(arr []int){
var i,j,key int
// 首先，把数组第一个元素当作是一个已排序的数组，然后从剩余未未排序数组中的第一个元素插入到已排序数组
for i=1;i<len(arr);i++{
key = arr[i]
j = i-1
// 比key大的元素往后移动一位
// 这里采用移动法，还可以使用类似冒泡排序中的交换法
for j >= 0 && arr[j] > key{
arr[j+1] = arr[j]
j--
}
arr[j+1] = key
}
}希尔排序（Shell Sort）
// ShellSort
// 希尔排序
// 时间复杂度: 平均O(NlogN) 最好O(NlogN) 最坏O(N^2)
// 空间复杂度: O(1)
// 稳定性：不稳定
// 希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），
// 是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。
// 该方法因 D.L.Shell 于 1959 年提出而得名。
// 希尔排序中对于增量序列的选择十分重要，直接影响到希尔排序的性能。
// 选择的增量序列{n/2,(n/2)/2...1}(希尔增量)，其最坏时间复杂度为O(n2)，
// 可以对增量序列进行优化，例如Hibbard可使得最坏时间复杂度为O(n3/2)
func ShellSort(arr []int) {
n := len(arr)
// 选择增量，最简单的是按照数组长度不断除2
for gap := n/2;gap > 0;gap/=2{
// 与增量成倍数关系的元素为一组，例如增量gap=5时，分为5组：
// 下标（0，0+5,0+5+5）为一组，下标（1，1+5,1+5+5）为一组，以此类推。
// 对每个组进行插入排序
for i:=0;i<gap;i++{
// 这里可以把gap=1来进行逻辑处理，实际上就是插入排序的逻辑
for j:=i+gap;j<n;j+=gap{
key := arr[j]
k := j - gap
for k >=0 && arr[k]>key{
arr[k+gap] = arr[k]
k -= gap
}
arr[k+gap] = key
}
}
}
}快速排序（Quick Sort）
// QuickSort
// 快速排序
// https://zh.wikipedia.org/wiki/快速排序
// 时间复杂度: 平均O(NlogN) 最好O(NlogN) 最坏O(N^2)退化为冒泡排序
// 空间复杂度: O(logN)
// 稳定性：不稳定
// 基本步骤：
// 挑选基准值：从数组中挑出一个元素，称为基准（pivot），（选择策略：第一个元素/最后一个元素/中间元素/随机选择）
// 分割：重新排序数组，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基基准面
//（与基准值相等的数可以到任何一变，注意这里破坏来稳定性）。在这个分割点束之后，对基准值的排序就已经完成，
// 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。
// 递归到最底部的判断条件是数组的大小是零或一，此时该数列显然已经有序。（这里可以优化，例如：子序列长度小于7时用选择排序）
// 选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。
func QuickSortRecursive(arr []int,left ,right int) {
if left < right{
i := left
j := right
key := arr[i]
for i < j{
// 因为pivot选择在左边第一个，一定要从右边开始。
// 如果pivot不是选择在左边第一个，可以通过交换令其成为第一个。
// 然后pivot值在左边和右边反复横跳：
// 首先pivot选择数组第一个值（左边），那我要从右边（顺序从右往左）找一个比我小的值，
// 然后交换，此时pivot在右边了。然后它又要跳回左边，于是在左边（从左往右）找一个比pivot大的值，
// 然后交换，于是pivot跳到左边了，然后又要跳到右边。。。直到两边都没坑位跳了。
// 此时pivot值所在的数组下标就是i，pivot是已经排序的来，位置不会再改变
// 因此递归的时候不再包含pivot，递归拆分为(left,i-1)和(i+1,right)两部分。
for i < j && arr[j] >= key{
j--
}
// 通过上面的循环后，为何还需要判断arr[j] < key ？
// 因为可能 i==j，此时如果进行i++会导致错误。
if arr[j] < key{
arr[i],arr[j] = arr[j],arr[i]
i++
}
for i < j && arr[i] <= key{
i++
}
if arr[i] > key{
arr[i],arr[j] = arr[j],arr[i]
j--
}
}
QuickSortRecursive(arr,left,i - 1)
QuickSortRecursive(arr,i + 1,right)
}
}
// 非递归实现的快速排序
// 首先要理解递归和非递归的本质区别，递归方法调用实际上就是一个压栈的过程，
// 一般来说，栈是有大小限制的(例如2K)，递归深度过大会导致栈溢出。因此
// 递归转为非递归，就是要手动实现压栈过程。此时的“栈”是在堆上，因此不会导致栈溢出。
// 模拟压栈，就是把每次递归调用的参数压栈(left,right)
func QuickSort(arr []int, left, right int) {
// 这里简单用slice实现栈
// 最好情况下的栈大小log2(N),最坏情况要N
size := 2
l := len(arr)
for l > 0 {
size += 2 // 每次压栈有2个参数
l = l >> 1
}
stack := make([]int, 0, size)
// 入栈
stack = append(stack, left)
stack = append(stack, right)
// 模拟递归调用
for len(stack) > 0 {
// 出栈
i := stack[len(stack)-2]
j := stack[len(stack)-1]
stack = stack[0 : len(stack)-2]
pivot := Partition(arr, i, j)
if pivot-1 > i {
// 入栈
stack = append(stack, i)
stack = append(stack, pivot-1)
}
if pivot+1 < j {
stack = append(stack, pivot+1)
stack = append(stack, j)
}
}
}
func Partition(arr []int, left int, right int) int {
mid := left + (right-left)/2
i := left
j := right
pivot := arr[mid]
for i < j {
for i < j && arr[i] < pivot {
i++
}
for j > i && arr[j] > pivot {
j--
}
arr[i], arr[j] = arr[j], arr[i]
}
return i
}归并排序（Merge Sort）
// MergeSort
// 归并排序
// https://zh.wikipedia.org/wiki/归并排序
// 时间复杂度: 平均O(NlogN) 最好O(NlogN) 最坏O(NlogN)
// 空间复杂度: O(N)
// 稳定性：稳定
// 该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
// 采用分治法:
// 分割：递归地把当前序列平均分割成两半。
// 整合：在保持元素顺序的同时将上一步得到的子序列整合到一起（归并）。
// 递归法（Top-down）
// 1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
// 2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
// 3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
// 4. 重复步骤3直到某一指针到达序列尾
// 5. 将另一序列剩下的所有元素直接复制到合并序列尾
// 迭代法（Bottom-up）
// 原理如下（假设序列共有n个元素）：
// 1. 将序列每相邻两个数字进行归并操作，形成ceil(n/2)个序列，排序后每个序列包含两/一个元素
// 2. 若此时序列数不是1个则将上述序列再次归并，形成ceil(n/4)个序列，每个序列包含四/三个元素
// 3. 重复步骤2，直到所有元素排序完毕，即序列数为1
func MergeSort(arr []int){
l := len(arr)
temp := make([]int,l)
// 分段为1,2,4,8...
for seg:=1;seg < l;seg += seg{
for start:=0;start < l;start += seg*2{
mid := start + seg - 1
end := start + seg * 2 - 1
if mid >= l{
mid = l-1
}
if end >= l{
end = l-1
}
start1 := start
end1 := mid
start2 := mid + 1
end2 := end
k := start
for start1 <= end1 && start2 <= end2{
if arr[start1] < arr[start2]{
temp[k] = arr[start1]
start1++
}else{
temp[k] = arr[start2]
start2++
}
k++
}
for start1 <= end1{
temp[k] = arr[start1]
start1++
k++
}
for start2 <= end2{
temp[k] = arr[start2]
start2++
k++
}
for i:=start;i <= end;i++{
arr[i] = temp[i]
}
}
}
}
// MergeSortRecursive
// MergeSort的递归版本
func MergeSortRecursive(arr []int){
var temp = make([]int,len(arr))
DoMergeSortRecursive(arr,temp,0,len(arr)-1)
}
func DoMergeSortRecursive(arr,temp []int,start,end int){
if start >= end{
return
}
mid := start + ((end - start) >> 1)
start1 := start
end1 := mid
start2 := mid+1
end2 := end
DoMergeSortRecursive(arr,temp,start1,end1)
DoMergeSortRecursive(arr,temp,start2,end2)
// 合并
k := start
for start1 <= end1 && start2 <= end2{
if arr[start1] < arr[start2]{
temp[k] = arr[start1]
start1++
}else{
temp[k] = arr[start2]
start2++
}
k++
}
for start1 <= end1{
temp[k] = arr[start1]
start1++
k++
}
for start2 <= end2{
temp[k] = arr[start2]
start2++
k++
}
// 临时排序数据拷贝到原数组
for i:=start;i <= end;i++{
arr[i] = temp[i]
}
}计数排序（Counting Sort）
// CountingSort
// 计数排序
// https://zh.wikipedia.org/wiki/计数排序
// 时间复杂度: 平均O(N+k) 最好O(N+k) 最坏O(N+k)
// 空间复杂度: O(max) 比排序元素数量还要大
// 稳定性：稳定
// 由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），
// 这使得计数排序对于数据范围很大的数组，需要大量时间和内存。
// 计数排序一般用来配合基数排序。
// 算法步骤：
// 1. 找出待排序的数组中最大和最小的元素
// 2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
// 3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
// 4. 反向填充目标数组：将每个元素i放在新数组的第C[i]项，每放一个元素就将C[i]减一。（确保稳定性）
func CountingSort(arr []int) {
// 只能对n及以内的正整数进行排序
n := len(arr)
c := make([]int,n)
temp := make([]int,n)
// 将计数的数组初始化为0
for i:=0;i<n;i++{
c[i] = 0
}
// 直接将值当作数组下标进行计数
for i:=0;i<n;i++{
c[arr[i]]++
}
for i:=1;i<n;i++{
// 计数求和，这样c[i]就是i在arr的所处下标
c[i] = c[i] + c[i-1]
}
// 反向填充目标数组，为什么？
// 因为计数数组c保存了对应值实际的下标，如果出现多个重复的值i，则c[i]>1，我们需要对其进行减一
// 来确保重复值能够按照原来的顺序保存（排序稳定），因此下标是递减的，所以必须反向填充目标数组。
for j:=n-1;j>=0;j--{
temp[c[arr[j]] - 1] = arr[j]
c[arr[j]]--
}
for i:=0;i<n;i++{
arr[i] = temp[i]
}
}基数排序（Radix Sort）
// RadixSort
// 基数排序
// https://zh.wikipedia.org/wiki/基数排序
// 时间复杂度: 平均O(N+k) 最好O(N+k) 最坏O(N+k)
// 空间复杂度: O(max)
// 稳定性：稳定
// 基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。
// 由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
// 基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），
// LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。
// 基数排序一般要快过基于比较的排序，比如快速排序。
// 算法步骤：
// 1 找出最大的元素（或者已知），计算该数有多少个数字组成（十进制），例如789有3个数字。
func RadixSort(arr []int) {
max := 0
for _,v := range arr{
if max < v{
max = v
}
}
// 对每个位进行排序
for place := 1;max/place > 0;place *=10{
countingSortOnDigit(arr,place)
}
}
// 对基数进行计数排序，例如对个位/十位/百位/千位进行排序
// place = 1,10,100,1000,...
func countingSortOnDigit(arr []int,place int) {
if len(arr) == 0{
return
}
// 计数排序，首先找出该位上的最大数字（0-9），例如1738的个位为8，十位为3
max := (arr[0]/place)%10
for i:=1;i<len(arr);i++{
if max < ((arr[i]/place)%10){
max = (arr[i]/place)%10
}
}
// max可以确定用于计数的数组大小
// 如果最大值是8，因为下标是从0开始，因此需要9个计数，因此max+1
count := make([]int,max+1)
// 进行计数
index := 0
for i:=0;i<len(arr);i++{
index = (arr[i]/place)%10
count[index]++
}
// 将count数组求和,注意这里遍历最大值是max
for i:=1;i<=max;i++{
count[i] = count[i] + count[i-1]
}
var temp = make([]int,len(arr)+1)
// 反向填充数组
for i:=len(arr)-1;i>=0;i--{
temp[count[(arr[i]/place)%10]-1] = arr[i]
count[(arr[i]/place)%10]--
}
for i:=0;i<len(arr);i++{
arr[i] = temp[i]
}
}堆排序（Heap Sort）
// HeapSort
// 堆排序
// 注意：性能看起来很好，但要考虑硬件缓存。
// 时间复杂度: 平均O(NlogN) 最好O(NlogN) 最坏O(NlogN)
// 空间复杂度: O(1)
// 稳定性：不稳定
// 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，
// 堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。
// 将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，
// 这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
// 直观的看起来就是：从最大堆中一个一个元素出列，出列元素组成一个有序列表。
// 堆排序缺点：快速排序是顺着扫的，堆排序是跳着走的，根据局部性原理，堆排序CPU缓存命中率比快速排序低。
// 快速排序通常比基数排序更有效地使用硬件的缓存。
func HeapSort(arr []int) {
n := len(arr)
// 首先构建一个最大堆，为了构建最大堆我们需要：
// 从最底层的子树往上一层一层heapify子树直至根节点
// 最后一个非叶子节点是n/2 - 1，因此所有比n/2 - 1大的节点都是叶子节点，
// 叶子节点不需要heapify（因为他们没有子节点）
// 这使得根节点到任意叶子节点的路径上的元素使有序的。
for i:= n/2-1;i >=0;i--{
heapify(arr,i,n)
}
for i:=n-1;i>=0;i--{
arr[0],arr[i] = arr[i],arr[0]
// 这里是如何确保heapify后root节点是最大值的？
heapify(arr,0,i)
}
}
// heapify
// 调整堆，使根节点要么比所有子节点大，要么成为叶子节点。
// root 堆顶下标
// length 数组arr长度
func heapify(arr []int,root,length int) {
max := root
leftChild := root*2+1
rightChild := root*2+2
if leftChild < length && arr[max] < arr[leftChild]{
max = leftChild
}
if rightChild < length && arr[max] < arr[rightChild]{
max = rightChild
}
if max != root{
arr[max],arr[root] = arr[root],arr[max]
heapify(arr,max,length)
}
}桶排序（Bucket Sort）
// BucketSort
// 桶排序
// 时间复杂度: 平均O(N+k) 最好O(N) 最坏O(N^2)
// 空间复杂度: O(N+k)
// 稳定性：稳定 (一般桶中元素以数组或链表保存，针对桶中元素要使用稳定排序算法才能保证稳定性)
// 适合大量数据的排序，例如对10亿个32位随机整数进行排序
// 每个通可以针对性选择的桶排序或其它算法进行排序，例如快速排序
func BucketSort(arr []int) {
// 创建桶，依需要排序的数量而定
// 针对桶还可以进行优化，例如使用bit
n := len(arr)
bucketSize := 1000
var buckets = make([][]int,100)
for k ,_ := range buckets{
buckets[k] = []int{}
}
// 将每个元素分配到对应的桶中，对于不同的桶来说，是有序的，但是桶内的元素是无序的。
for i:=0;i<n;i++{
index := arr[i]/bucketSize
buckets[index] = append(buckets[index],arr[i])
}
// 对每个桶内的元素使用快速排序（当然也可以根据需要选用不同的排序算法）
j := 0
for _,v := range buckets{
QuickSort(v,0,len(v)-1)
// 整合
for _,vv := range v{
arr[j] = vv
j++
}
}
}