最常用的排序算法：快速排序 和 归并排序。
适用于数值范围较小或均匀分布：计数排序 和 桶排序。
适合小规模数据或者部分有序的数据：冒泡排序、选择排序 和 插入排序。

以下示例以从小到大排序为例

1、冒泡排序

和相邻的数比较，比它大交换，向左移动，直到列表的末尾，返回，重复过程

时间复杂度：o(n^2)

1
2
3
4
5
6
7
8
9
10
func bubbleSort(nums []int)[]int{
  for i:=0;i<len(nums);i++{
    for j:=0;j<len(nums)-i-1;j++{
      if nums[j]>nums[j+1]{
        nums[j],nums[j+1]=nums[j+1],nums[j]
      }
    }
  }
  return nums
}

2、选择排序

在未排序数组中选择一个最小的放到已经排序数组的最后面，重复过程

时间复杂度：o(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
func choseSort(nums []int)[]int{
  for i:=0;i<len(nums);i++{
    min:=i
    for j:=i+1;j<len(nums);j++{
      if nums[j]<nums[min]{
          min=j
      }
    }
    nums[i],nums[min]=nums[min],nums[i]
  }
  return nums
}

3、插入排序

将未排序数组的第一个数和已经排序的数组元素依次比较，插入到合适的位置

时间复杂度：o(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
func insertSort(nums []int)[]int{
  for i:=1;i<len(nums);i++{
    cur:= nums[i]
    j := i - 1
    for j >= 0 && nums[j] > current {
        nums[j+1]=nums[j]
        j--
    }
    nums[j+1] = cur
  }
  return nums
}

4、快速排序

选择一个基数，大的放右边，小的放左边，然后分别对左边和右边重复这样的操作

时间复杂度：o(nlog(n))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func quickSort(nums []int)[]int{
  if len(nums)<=1{
    return nums
  }
  base:=nums[len(nums)/2]
  l,r:=0,len(nums)-1
  for l<=r{
    for l<=r&&nums[l]<base{
      l++
    }
    for l<=r&&nums[r]>base{
      r--
    }
    if l<=r{
        nums[l],nums[r]=nums[r],nums[l]
        l++
        r--
    } 
  }
  quickSort(nums[:r+1])
  quickSort(nums[l:])
  return nums
}

5、归并排序

将未排序数组划分两组，得到的两组继续递归操作，切半划分，直到划分的组不能被划分，合并两个数组，返回再合并

时间复杂度：o(nlog(n))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func mergeSort(nums []int)[]int{
  size:=len(nums)
  if size<=1{
    return nums
  }
  left:=mergeSort(nums[:size/2])
  right:=mergeSort(nums[size/2:])
  return merge(left,right)
}

func merge(str1 []int,str2 []int)[]int{
  res:=make([]int,0，len(str1)+len(str2))
  i,j:=0,0
  for i<len(str1)&&j<len(str2){
    if str1[i]<str2[j]{
      res=append(res,str1[i])
      i++
    }else{
      res=append(res,str2[j])
      j++
    }
  }
  for i<len(str1){
    res=append(res,str1[i])
    i++
  }
   for j<len(str2){
    res=append(res,str2[j])
    j++
  }
  return res
}

6、堆排序

将未排序数组构建一个完全二叉树，找到倒数第一个非叶子节点（n/2-1),与子节点比较，交换比自己大的子节点， 构建一个大根堆，每次取第一个，直到取完（大根堆可以让空间复杂度降为 o(1))

时间复杂度：o(nlog(n))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
func heapSort(nums []int)[]int{
  if len(nums)<=1{
    return nums
  }
  buidHeap(nums)
  res:=make([]int,0,len(nums))
  for len(nums)>0{
    val,newNums:=pop(nums)
    res=append(res,val)
    nums=newNums
  }
  return res
}


func buildHeap(nums []int){
   i:=len(nums)/2-1
   for i>=0{
      adjustHeap(nums,i,len(nums))
      i--
   }
}

func adjustHeap(nums []int,i int,size int){
  maxIndex:=i
  left,right:=i*2,i*2+1
  if left<size &&nums[maxIndex]<nums[left]{
     maxIndex=left
  }
  if i*2+1<size&&nums[maxIndex]<nums[right]{
     maxIndex=right
  }
  if maxIndex!=i{
    nums[i],nums[maxIndex]=nums[maxIndex],nums[i]
    adjustHeap(nums,maxIndex,size)
  }
}

func pop(nums []int)(int,[]int) {
    top:=nums[0]
    nums[0]=nums[len(nums)-1]
    newNums:=nums[:len(nums)-1]
    adjustHeap(nums,0,len(newNums))
    return top,newNums
}

7、希尔排序

改进版的插入排序，跳着排，最后会间隔为 1 排

时间复杂度：o(n^(3/2))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func shellSort(nums []int)[]int{
   if len(nums)<=1{
     return nums
   }
   for gap:=len(nums)/2;gap>0;gap/=2{
     for i:=gap;i<len(nums);i++{
         cur:=nums[i]
         j:=i
         for j>=gap&&nums[j-gap]>cur{
           nums[j]=nums[j-gap]
           j-=gap 
         }
         nums[j]=cur
     }
   }
   return nums
}

8、桶排序

分桶→桶内排序→合并，每个桶都有范围限制，将数据分到对应的桶中，对每个桶中的数据分别排序，然后合并每个桶的数据

时间复杂度：o(n*k)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
func bucketSort(nums []int)[]int{
   if len(nums)<=1{
     return nums
   }
   // 找到数组中最大和最小的
   minNum,maxNum:=nums[0],nums[0]
   for i:=0;i<len(nums);i++{
     if nums[i]<minNum{
       minNum=nums[i]
     }
     if nums[i]>maxNum{
       maxNum=nums[i] 
     }
   }
   bucketNum:=len(nums)
   bucketSize:=(maxNum-minNum)/bucketNum
   buckets:=make([][]int,bucketNum)
   //将数据放到桶中
   for i:=0;i<len(nums);i++{
     index:=(nums[i]-minNum)/bucketSize
     if index==bucketNum{
       index=bucketNum-1
     }
     buckets[index]=append(buckets[index],nums[i])
   }
   //排序每个桶并合并
   res:=make([]int,0,len(nums))
   for i:=0;i<bucketNum;i++{
     sort.Ints(bucket[i])
     res=append(res,bucket[i]...)
   }
   return res
}

9、基数排序

跟桶排序很像，先根据个位的数字排序，然后根据十位，依次递推，直到该数组最大数的最高位

时间复杂度：O(n*k)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func radixSort(nums []int){
  if len(nums)<=1{
     return nums
  }
  maxNum:=nums[0]
  for i:=0;i<len(nums);i++{
    if nums[i]>maxNum {
       maxNum=nums[i]
    }
  }
  maxDigit := int(math.log10(float64(maxNum))) + 1
  for i:=0;i<maxDigit;i++{
    bucket:=make([][]int,10)
    for j:=0;j<len(nums);j++{
       // 获取指定位的数字
       digit := (nums[j] / int(math.Pow10(i))) % 10
       bucket[digit]=append(bucket[digit],nums[j])
    }
    nums=nil
    for j:=0;j<10;j++{
      nums=append(nums,bucket[j]...)
    }
  }
  return nums
}

10、计数排序

统计待排数组中每个元素的个数，然后对其进行合并

时间复杂度：O(n + k)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func countingSort(nums []int)[]int{
  if len(nums)<=1{
    return nums
  }
  // 找到数组中最大和最小的
  minNum,maxNum:=nums[0],nums[0]
  for i:=0;i<len(nums);i++{
    if nums[i]<minNum{
      minNum=nums[i]
    }
    if nums[i]>maxNum{
      maxNum=nums[i] 
    }
  }
  counts:=make([]int,maxNum-minNum+1)
  for i:=0;i<len(nums);i++{
    counts[nums[i]-minNum]++
  }
  res:=make([]int,0,len(nums))
  for i:=0;i<len(counts);i++{
    for count[i]>0{
      res=append(res,i+minNum)
      count[i]-- 
    }
  }
  return res
}