数据结构与算法之十大经典排序_数据结构十大经典算法

数据结构与算法系列文章

数据结构与算法之哈希表

数据结构与算法之跳跃表

数据结构与算法之十大经典排序

数据结构与算法之十大经典排序

本文主要介绍一下算法中最基础的排序问题，尽可能按照从入门到深入的顺序介绍，也就是博主自身学习的顺序，注意本文均在升序且有些排序仅满足非负整数的情况下进行讨论。
综述十大排序如下：

算法分类

以上所列出的算法大致分为两类
比较类算法：这种算法主要是比较元素间的相对大小次序来进行排序的，由于其时间复杂度较高，因此也称为非线性时间比较类排序。如选择排序、冒泡排序、插入排序等等
非比较算法：与比较类算法相反，不通过比较而通过其他手段如计数排序、桶排序、基数排序，由于其时间复杂度可以达到线性时间，因此也称为线性时间比较类排序。

算法分析的相关概念

时间复杂度：对排序数据的总的操作次数。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量。
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。

选择排序

概念

选择排序，每次排序将未排序元素中最小的元素与已排序序列下一位置的元素交换，直到不再有未排序元素。

算法描述

为方便与算法实现对应，此处设定一个序列R[1,2,……,n]，则需要进行n-1次扫描排序即可完全排序结束。

1. 初始，整个序列R[1,2,……,n]处于无序状态.
2. 第i(i=1,……,n-1)趟扫描元素进行排序时，选择R[i+1,……,n]中最小的元素与处于第i位置的元素进行交换
3. 当i=n-1结束扫描元素排序后，排序结束。

算法分析

1. 时间复杂度
   序列的每个位置都会进行一次扫描用时O(n)，并且在每个位置又会对每个元素都会进行一次扫描用时O(n)，因此总时间复杂度为O(n2)
2. 稳定性分析
   选择排序较为稳定，就在于每次排序之后，排好序的位置不再变动，也就是在后出现与排好序中元素a相同的元素b只会插在序列之后，即b元素依然在a元素之后。

动图

代码实现（Java+Go）

Java版本

public class SelectSort {
	public static void selectSort(int[] nums){
		int i,j,minIndex,tmp;
		for(i=0;i<nums.length-1;i++){
			minIndex = i;
			for(j=i+1;j<nums.length;j++) {
				if(nums[minIndex]>nums[j]){
					minIndex = j;
				}
			}
			if(minIndex!=i) {
				tmp = nums[minIndex];
				nums[minIndex] = nums[i];
				nums[i] = tmp;
			}
		}
	}
	
	public static void show(int[] nums) {
		for(int i =0;i<nums.length;i++) {
			System.out.printf("%d ", nums[i]);
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] nums = {4,12,13,4,3,42,33,1,43,44};
		System.out.println("排序前：");
		show(nums);
		selectSort(nums);
		System.out.println("排序后：");
		show(nums);
	}
}
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

Go版本

package main
import "fmt"

func show(nums []int){
	for _,num:=range nums{
		fmt.Printf("%d ",num)
	}
	fmt.Println()
}

func selectSort(nums[]int)[]int{

	for i:=0;i<len(nums)-1;i++{
		minIndex := i
		for j:=i+1;j<len(nums);j++{
			if nums[minIndex] > nums[j]{
				minIndex = j
			}
		}
		if minIndex!=i{
			tmp:=nums[i]
			nums[i] = nums[minIndex]
			nums[minIndex] = tmp
		}

	}
	return nums
}

func main(){
	nums :=[]int{4,12,13,4,3,42,33,1,43,44}
	fmt.Println("排序前：")
	show(nums)
	numsSorted := selectSort(nums)
	fmt.Println("排序后：")
	show(numsSorted)
}
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

冒泡排序

概念

冒泡排序，比较相邻两个元素之间的大小，并调整相应大小顺序，始终保持两个元素较大在后，较小在前，直至所有元素的顺序都不再改变。

算法描述

1. 初始状态下，整个序列R[1,2,……,n]处于无序状态.
2. 第i(i=1,……,n-1)趟扫描元素进行排序时，比较R[1,……,n-i]中第j(j=1,……,n-i)个位置与j+1位置处的元素大小，并调整顺序。（优化：当某一次扫描后没有发生任何一次位置交换则认为排序结束）
3. 当i=n-1结束扫描元素排序后，排序结束。

算法分析

1. 时间复杂度
   对序列进行n-1次扫描用时O(n)，并且在每个位置又会对剩下的每个位置进行一次扫描用时O(n)，因此总时间复杂度为O(n2)
2. 稳定性
   冒泡排序的稳定性体现在每次扫描排序后排好序的元素位置不在变动。

动图

代码实现（Java+Go）

Java版本

public class BubbleSort {
	public static void bubbleSort(int[] nums){
		int i,j,tmp;
		boolean exchange = false;//用于判断是否有位置交换
		for(i=0;i<nums.length-1;i++){
			exchange = false;
			for(j=1;j<nums.length-i;j++) {
				if(nums[j-1]>nums[j]){
					tmp = nums[j-1];
					nums[j-1] = nums[j];
					nums[j] = tmp;
					exchange =true;
				}
			}
			if(!exchange) {//本次扫描未发生位置交换则说明排序结束
				return;
			}
		}
	}
	
	public static void show(int[] nums) {
		for(int i =0;i<nums.length;i++) {
			System.out.printf("%d ", nums[i]);
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] nums = {9,5,6,7,2,8,3,4,1};
		System.out.println("排序前：");
		show(nums);
		bubbleSort(nums);
		System.out.println("排序后：");
		show(nums);
	}
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

Go版本

package main

import "fmt"

func show(nums []int){
	for _,num:=range nums{
		fmt.Printf("%d ",num)
	}
	fmt.Println()
}

func bubbleSort(nums[]int)[]int{
	for i:=0;i<len(nums)-1;i++{
		exchange:=false//用于判断此次扫描是否有位置交换
		for j:=1;j<len(nums)-i;j++ {
			if nums[j-1] > nums[j]{
				nums[j],nums[j-1]=nums[j-1],nums[j]
				exchange=true
			}
		}
		if !exchange{//本次扫描未发生位置交换则说明排序结束
			return nums
		}
	}
	return nums
}

func main(){
	nums :=[]int{9,5,6,7,2,8,3,4,1}
	fmt.Println("排序前：")
	show(nums)
	numsSorted := bubbleSort(nums)
	fmt.Println("排序后：")
	show(numsSorted)
}
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

插入排序

概念

插入排序，即选取一个元素与排列在其前面的元素进行逐一比较，大于则交换，直至遇到比元素本身小的元素插入其后。

算法描述

1. 初始状态下，整个序列R[1,2,……,n]处于无序状态，默认第一个位置已经排好
2. 取第i(i=2,……,n)个位置的元素，将其与R[1,……,i-1]中元素逐一比较大小，并调整顺序，直至遇到小于或者等于自身的元素，插入其后。
   3.当最后一个元素比较完毕，则排序结束。

算法分析

1. 时间复杂度
   对序列进行n-1次扫描用时O(n)，并且在每个位置又会对在其之前的位置进行一次扫描用时O(i)(因为i最后会成为n-1)，因此总时间复杂度为O(n2)
2. 稳定性
   插入排序的稳定性体现在每次比较大小排序时相同元素在序列中的位置关系不改变。

动图

代码实现（Java+Go）

Java版本

public class InsertSort {
	public static void insertSort(int[] nums){
		int i,j,tmp;
		for(i=1;i<nums.length;i++){
			for(j=i;j>0;j--) {
				if(nums[j-1]>nums[j]){
					tmp = nums[j-1];
					nums[j-1] = nums[j];
					nums[j] = tmp;
				}else {
					break;
				}
			}
		}
	}
	
	public static void show(int[] nums) {
		for(int i =0;i<nums.length;i++) {
			System.out.printf("%d ", nums[i]);
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] nums = {9,7,8,2,5,1,3,6,4};
		System.out.println("排序前：");
		show(nums);
		insertSort(nums);
		System.out.println("排序后：");
		show(nums);
	}
}
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

Go版本

package main

import "fmt"

func show(nums []int){
	for _,num:=range nums{
		fmt.Printf("%d ",num)
	}
	fmt.Println()
}

func insertSort(nums[]int)[]int{
	for i:=1;i<len(nums);i++{
		for j:=i;j>0;j--{
			if nums[j-1]>nums[j]{
				nums[j-1],nums[j] = nums[j],nums[j-1]
			}else{
				break
			}
		}
	}
	return nums
}

func main(){
	nums :=[]int{9,7,8,2,5,1,3,6,4}
	fmt.Println("排序前：")
	show(nums)
	numsSorted := insertSort(nums)
	fmt.Println("排序后：")
	show(numsSorted)
}
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

归并排序

概念

归并排序用到的算法思想是分而治之也就是分治法（Divide and Conquer），此处安利一波我原来的MIT课程博客MIT算法导论第一课——插入排序与归并排序c++实现。归并排序即将序列一分为二成两个子序列，然后再对子序列一分为二，当达到不能再分的条件后，对序列进行排序再合并操作，一直合并到与原序列等长度的序列。

算法描述

1. 初始状态下，整个序列R[1,2,……,n]处于无序状态
2. 将序列持续一分为二，最终分成数组大小为1的若干数组
3. 当最后一个元素比较完毕，则排序结束。

算法分析

1. 时间复杂度
   该算法对序列不停地进行二分再合并，合并时对已排好序的子序列进行比较用时O(n)，而二分这一操作进行了O(lgn)，因此总时间复杂度为O(nlgn)
2. 稳定性
   归并排序的稳定性同样不改变相同元素的位置关系。

动图

代码实现（Java+Go）

Java版本

import java.util.Arrays;

public class MergeSort {
	public  static int[] merge(int[]left,int[]right){
		int index=0,l=0,r=0,min=0;
		int length=left.length+right.length;
		int[] tmp = new int[length];
		for(;index<length;){
			if(l<left.length&&r<right.length){
				if(left[l]<=right[r]){
					min = left[l];
					l++;
				}else{
					min = right[r];
					r++;
				}
				tmp[index] = min;
				index++;
			}
			
			if(l==left.length&&r<right.length){
				for(;r<right.length;r++){
					tmp[index] = right[r];
					index++;
				}
			}
			
			if(r==right.length&&l<left.length){
				for(;l<left.length;l++){
				tmp[index] = left[l];
				index++;
				}
			}
		}
		return tmp;
	}
	
	public static int[] mergeSort(int[] arr){
		if(arr.length<=1)return arr;
		int mid = arr.length/2;
		int[] left = Arrays.copyOfRange(arr, 0,mid);
		int[] right = Arrays.copyOfRange(arr, mid,arr.length);
		return merge(mergeSort(left),mergeSort(right));
	}
	
	public static void show(int[] nums) {
		for(int i =0;i<nums.length;i++) {
			System.out.printf("%d ", nums[i]);
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] nums = {5,6,3,1,8,7,2,4};
		System.out.println("排序前：");
		show(nums);
		int[] numsSorted = mergeSort(nums);
		System.out.println("排序后：");
		show(numsSorted);
	}
}

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

Go版本

package main

import "fmt"

func show(nums []int){
	for _,num:=range nums{
		fmt.Printf("%d ",num)
	}
	fmt.Println()
}

func merge(left []int,right []int)[]int{、、合并
	index,l,r,min,length:=0,0,0,0,len(left)+len(right)
	tmp := make([]int,length)
	for index<length{
		if l<len(left)&&r<len(right) {
			if left[l]<=right[r]{
				min = left[l]
				l++
			}else{
				min = right[r]
				r++
			}
			tmp[index] = min
			index++
		}
		if l==len(left)&&r<len(right) {
			for;r<len(right);r++{
				tmp[index] = right[r]
				index++
			}
		}

		if r==len(right)&&l<len(left){
			for;l<len(left);l++{
			tmp[index] = left[l]
			index++
			}
		}
	}
	return tmp
}

func mergeSort(nums []int)[]int{
	if len(nums)<=1{
		return nums
	}
	mid:=(int)(len(nums)/2)
	left := nums[0:mid]
	right:= nums[mid:len(nums)]

	return merge(mergeSort(left),mergeSort(right))//分而治之
}

func main(){
	nums :=[]int{5,6,3,1,8,7,2,4}
	fmt.Println("排序前：")
	show(nums)
	numsSorted := mergeSort(nums)
	fmt.Println("排序后：")
	show(numsSorted)
}

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

快速排序

概念

快速排序是较为常见的排序方法，俗称快排，与归并排序类似，用到的算法思想也是分治法（Divide and Conquer），基于序列中一个数，将序列一分为二：大于该数的放在该数的右侧，否则放在左侧，然后再对左右两侧子序列进行相同操作——基于序列中一个数，将序列一分为二……直到序列中只剩下一个数字。

算法描述

1. 初始状态下，整个序列R[1,2,……,n]处于无序状态
2. 取一个数（一般取序列的第一个数）将序列一分为二：大于该数的放在该数的右侧，否则放在左侧，并获得新序列该数的位置。
3. 基于该数当前位置，对左右两边子序列重复2操作，直到序列中只有一个数，排序完成。

算法分析

1. 时间复杂度
   对序列进行二分操作进行了O(lgn)，并且z在序列中又以一个数为基准与其他数比较用时O(n)，因此总时间复杂度为O(nlgn)
2. 稳定性
   快速排序是不稳定的，本文规则小于等于当前值均放在左侧。

动图

代码实现（Java+Go）

Java版本

public class QuickSort {
	public static void quickSort(int[]arr,int start,int end) {
		if(start<end) {
			int index = getIndex(arr,start,end);
			quickSort(arr,start,index-1);
			quickSort(arr,index+1,end);
		}
	}
	
	public static int getIndex(int[]arr,int start,int end) {
		int tmp = arr[start];
		while(start<end){
			while(start<end && tmp<=arr[end]) end--;
			arr[start] = arr[end];
			while(start<end && tmp>=arr[start]) start++;
			arr[end] = arr[start];
		}
		arr[start] = tmp;
		return start;
	}
	
	public static void main(String[] args) {
		int[] a = {3,44,38,5,47,15,36,36,27,2,46,4,19,50,48};
		System.out.print("排序前数组a：\n");
		for(int i:a) {
			System.out.print(i);
			System.out.print(" ");
		}
		quickSort(a,0,a.length-1);
		System.out.print("\n排序后数组a：\n");
		for(int i:a) {
			System.out.print(i);
			System.out.print(" ");
		}
	}
}
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

Go版本

package main

import "fmt"

func show(nums []int){
	for _,num:=range nums{
		fmt.Printf("%d ",num)
	}
	fmt.Println()
}

func getIndex(nums []int,start int,end int)(int,[]int){
	tmp:= nums[start]
	for start<end{
		for start<end&&tmp<=nums[end] {
			end--
		}
		nums[start] = nums[end]
		for start<end&&tmp>=nums[start]{
			start++
		}
		nums[end] = nums[start]
	}
	nums[start] = tmp
	return start,nums
}

func quickSort(nums []int,start int,end int)[]int{
	if(start<end){
		index,nums:= getIndex(nums,start,end)
		nums = quickSort(nums,0,index-1)
		nums = quickSort(nums,index+1,end)
	}
	return nums
}

func main(){
	nums :=[]int{3,44,38,5,47,15,36,36,27,2,46,4,19,50,48}
	fmt.Println("排序前：")
	show(nums)
	quickSort(nums,0,len(nums)-1)
	fmt.Println("排序后：")
	show(nums)
}
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

堆排序

概念

堆排序，用到堆的数据结构(与完全二叉树近似)，此数据结构以后会继续介绍，今天了解堆的特点如下即可：

• 大顶堆：每个结点的值都大于或等于其左右孩子结点的值
• 小顶堆：每个结点的值都小于或等于其左右孩子结点的值
  转换成数组表示则：
• i的子节点下标为 2*i + 1 和 2 * i + 2。
• i的父节点下标为 (i-1)/2。
• 大顶堆: array[i]>=array[2i+1] && rray[i]>=array[2i+2]
• 小顶堆: array[i]<=arr[2i+1] && array[i]<=array[2i+2]
• 对于序列长度为n，则大于n/2的元素一定没有子节点
  本文采用升序操作，则使用大顶堆。
  排序则是构建大顶堆，每次拿出来根节点（根节点最大），然后把剩下的元素再构建一次大顶堆一直到最后一个元素。因此，每次从堆中取出的数字为最大数。

算法描述

1. 初始状态下，整个序列R[1,2,……,n]处于无序状态，构建大顶堆作为初始堆
2. 取出根节点（堆顶元素）与最后一个元素交换，交换必然破坏堆的特性，需要对剩下的元素进行重构大顶堆。
3. 重复操作2直到剩余元素只剩一个，此时排序结束。

算法分析

1. 时间复杂度
   排序主要是两个过程，一个是生成初始堆，用时O(n)；一个是交换过程中堆的重建，交换操作进行了n-1次，而重建堆则log(n-1)、log(n-2)、…… 1因此总耗时O(nlgn)
2. 稳定性
   堆排序是不稳定的，生成堆的过程无法保证两个相等的值的顺序。

动图

代码实现（Java+Go）

Java版本

public class HeapSort {
    // 堆排序
    public static int[] heapSort(int[] nums) {
    	int n = nums.length;
    	int i,tmp;
    	//构建大顶堆
    	for(i=(n-2)/2;i>=0;i--) {//从只有一层子节点的父节点开始往树的根节点进行下沉操作
    		downAdjust(nums,i,n-1);
    	}
    	//进行堆排序
    	for(i=n-1;i>=1;i--){
    		tmp = nums[i];
    		nums[i] = nums[0];
    		nums[0] = tmp;
    		downAdjust(nums,0,i-1);
    	}
    	return nums;
    }

        //小元素下沉操作
    public static void downAdjust(int[] nums, int parentIndex, int n) {
        //临时保存要下沉的元素
        int temp = nums[parentIndex];
        //左子节点的位置
        int childIndex = 2 * parentIndex + 1;
        while (childIndex <= n) {
            // 如果右子节点比左子节点大，则与右子节点交换
            if(childIndex + 1 <= n && nums[childIndex] < nums[childIndex + 1])
            	childIndex++;
            if (nums[childIndex] <= temp ) break;//该子节点符合大顶堆特点
            //注意由于我们是从高度为1的节点进行堆排序的，所以不用担心节点子节点的子节点不符合堆特点
            // 父节点进行下沉
            nums[parentIndex] = nums[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * parentIndex + 1;
        }
        nums[parentIndex] = temp;
    }
    
	public static void main(String[] args) {
		int[] a = {91,60,96,13,35,65,81,46,13,10,30,20,31,77,81,22};
		System.out.print("排序前数组a：\n");
		for(int i:a) {
			System.out.print(i);
			System.out.print(" ");	
		}
		a=heapSort(a);
		System.out.print("\n排序后数组a：\n");
		for(int i:a) {
			System.out.print(i);
			System.out.print(" ");
		}
	}
}
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
46
47
48
49
50
51
52
53
54

Go版本

package main

import "fmt"

func show(nums []int){
	for _,num:=range nums{
		fmt.Printf("%d ",num)
	}
	fmt.Println()
}

func downAdjust(nums []int,parentIndex int,end int)[]int{
	//临时保存调整前的根节点
	tmp := nums[parentIndex]
	//左边子节点在数组中位置
	childIndex := 2*parentIndex + 1
	for childIndex<=end {
		//如果右边子节点比左边子节点大，则右边子节点
		if(childIndex+1<=end && nums[childIndex]<nums[childIndex+1]){
			childIndex++//右边子节点在数组中位置childIndex+1
		}
		if(nums[childIndex]<=tmp){
			break
		}//如果子节点比父节点小或者相等则构建无误
		//父节点被子节点代替，子节点上浮
		nums[parentIndex],parentIndex = nums[childIndex],childIndex
		childIndex = 2*parentIndex + 1//寻找孩子节点孩子
	}
	nums[parentIndex] = tmp//父节点下沉

	return nums
}

func heapSort(nums []int)[]int{
	length :=len(nums)
	for i:=(length-2)/2;i>=0;i--{//构建最大堆
		nums = downAdjust(nums,i,length-1)
	}
	//每取一次根节点进行一次重新构建大顶堆
	for i:=length-1;i>0;i--{
		nums[i],nums[0] = nums[0],nums[i]
		downAdjust(nums,0,i-1)
	}
	return nums
}

func main(){
	nums :=[]int{91,60,96,13,35,65,81,46,13,10,30,20,31,77,81,22}
	fmt.Println("排序前：")
	show(nums)
	heapSort(nums)
	fmt.Println("排序后：")
	show(nums)
}

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
46
47
48
49
50
51
52
53
54
55

计数排序

概念

计数排序就是消耗空间来代替时间的排序方法，这样就能在线性时间内排序完成。前提是已知数据的大小范围。

算法描述

1. 初始状态下，整个序列R[1,2,……,n]处于无序状态，且大小在[a,a+k]范围内
2. 生成一个a+k大小的数组，遍历序列，数字出现一次则数组相应下标计数加1
3. 序列遍历结束后，反向遍历数组，将有计数的数组下标按照计数个数放入序列中

算法分析

1. 时间复杂度
   遍历序列用时O(n)，遍历数组用时O(k)，总共耗时O(n+k)
2. 稳定性
   计数排序是稳定的，相同数的顺序没有改变。

动图

代码实现（Java+Go）

Java版本

public class CountSort {
	public static int[] countSort(int[] nums){
		if(nums.length<2) return nums;
		
		//计算最大最小值，确定数据范围
		int max = Integer.MIN_VALUE;
		int min = Integer.MAX_VALUE;
		int len = nums.length;
		int i,j=0;
		for(i=0;i<nums.length;i++){
			max = max>nums[i]?max:nums[i];
			min = min<nums[i]?min:nums[i];
		}
		int[] count_box = new int[max+1];
		for(int num:nums) {
			count_box[num]++;
		}
		
		for(i=min;i<max+1;) {
			while(count_box[i]!=0) {
				nums[j++] = i;
				count_box[i]--;
			}
			i++;
		}
		return nums;
	}
	
	public static void show(int[] nums) {
		for(int i =0;i<nums.length;i++) {
			System.out.printf("%d ", nums[i]);
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] nums = {2,3,8,7,1,2,2,2,7,3,9,8,2,1,4,2,6,9,2};
		System.out.println("排序前：");
		show(nums);
		int[] numsSorted = countSort(nums);
		System.out.println("排序后：");
		show(numsSorted);
	}
}

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
46

Go版本

package main

import "fmt"

func show(nums []int){
	for _,num:=range nums{
		fmt.Printf("%d ",num)
	}
	fmt.Println()
}

func countSort(nums []int)[]int{
	if(len(nums)<2) {
		return nums
	}
	i,j :=0,0
	//先找出最大值，计算其最大位数
	max :=nums[0]
	min :=nums[0]
	for _,num :=range nums{
		if max<num{
			max = num
		}
		if min>num{
			min = num
		}
	}
	countBox := make([]int,max+1)

	//计数
	for _,num :=range nums{
		countBox[num]++
	}
	for i=min;i<max+1;{
		for countBox[i]!=0{
			nums[j]=i
			j++
			countBox[i]--
		}
		i++
	}
	return nums
}

func main(){
	nums :=[]int{2,3,8,7,1,2,2,2,7,3,9,8,2,1,4,2,6,9,2}
	fmt.Println("排序前：")
	show(nums)
	nums = countSort(nums)
	fmt.Println("排序后：")
	show(nums)
}
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
46
47
48
49
50
51
52

桶排序

概念

计数排序的优化版本，用有限数量的桶存放数据（存放规则由自定义函数来确定），对每个桶进行排序。
每个桶中的数包含在一个范围，桶排序是对数据进行了区域划分，然后对每个区域内的数据进行排序，然后依次输出。

算法描述

1. 初始状态下，整个序列R[1,2,……,n]处于无序状态，且大小在[a,a+k]范围内
2. 设置桶的数量为bucketNum，则数据可以划分为[0,bucketNum]、[bucketNum,2bucketNum-1]、……、[n(bucketNum-1)/bucketNum,n]，数组中数据分别分配到相应桶中
3. 再对每个非空桶中的元素进行排序
4. 所有的非空桶依次合并即得到排序好的数据

算法分析

1. 时间复杂度
   遍历序列用时O(n)，因此桶排序耗时主要取决于每个桶排序用时O(k)，总共耗时O(n+k)
2. 稳定性
   桶排序是稳定的，相同数的顺序没有改变。

动图

代码实现（Java+Go）

Java版本

import java.util.*;
public class BucketSort {
	
	public static int[] bucketSort(int[] nums,int bucketNum){
		if(nums.length<2) return nums;
		
		//计算最大最小值，确定数据范围
		int max = Integer.MIN_VALUE;
		int min = Integer.MAX_VALUE;
		int len = nums.length;
		int i,j=0;
		for(i=0;i<nums.length;i++){
			max = max>nums[i]?max:nums[i];
			min = min<nums[i]?min:nums[i];
		}
        ArrayList<LinkedList<Integer>> bucketList = new ArrayList<>(bucketNum);
        //初始化桶
        for (i = 0; i < bucketNum; i++) {
            bucketList.add(new LinkedList<Integer>());
        }
        //遍历原数组，将每个元素放入桶中
        for (i = 0; i < len; i++) {
            bucketList.get((nums[i])/bucketNum).add(nums[i]);
        }
        //对桶内的元素进行排序，采用库里自带排序
        for (i = 0; i < bucketNum; i++) {
            Collections.sort(bucketList.get(i));
        }
        //把每个桶排序好的数据进行合并汇总放回原数组
        for (i = 0; i < bucketNum; i++) {
            for (int num: bucketList.get(i)) {
            	nums[j++] = num；
            }
        }
		return nums;
	}
	
	public static void show(int[] nums) {
		for(int i =0;i<nums.length;i++) {
			System.out.printf("%d ", nums[i]);
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] nums = {2,3,8,7,1,2,2,2,7,3,9,8,2,1,4,2,6,9,2};
		System.out.println("排序前：");
		show(nums);
		int[] numsSorted = bucketSort(nums,10);
		System.out.println("排序后：");
		show(numsSorted);
	}
}
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
46
47
48
49
50
51
52
53
54
55

Go版本

package main

import "fmt"

func show(nums []int){
	for _,num:=range nums{
		fmt.Printf("%d ",num)
	}
	fmt.Println()
}

func getIndex(nums []int,start int,end int)(int,[]int){
	tmp:= nums[start]
	for ;start<end;{
		for;start<end&&tmp<=nums[end];{
			end--
		}
		nums[start] = nums[end]
		for;start<end&&tmp>=nums[start];{
			start++
		}
		nums[end] = nums[start]
	}
	nums[start] = tmp
	return start,nums
}

func quickSort(nums []int,start int,end int)[]int{
	if(start<end){
		index,nums:= getIndex(nums,start,end)
		nums = quickSort(nums,0,index-1)
		nums = quickSort(nums,index+1,end)
	}
	return nums


}

func bucketSort(nums []int,bucketNum int)([]int){

	var 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
}

func main(){
	nums :=[]int{50,6,3,1,8,7,2,4}
	fmt.Println("排序前：")
	show(nums)
	nums = bucketSort(nums,20)
	fmt.Println("排序后：")
	show(nums)
}
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

希尔排序

概念

希尔排序，插入排序的一种，是直接插入排序的优化形式，又称为缩小增量排序。按照一定规则分不同组，对组内元素进行直接插入排序。

算法描述

希尔排序会按照一定的增量组将数据分组，然后对每一组的元素进行直接插入排序操作。
本论文选择最为常用的也被称为希尔增量的一组序列，即{n/2,n/4,……1}，以等比为1/2逐级递减

1. 选择一个增量序列t1,t2,……，tk，逐级递减，tk=1
2. 取出增量序列所选取的k个元素，进行排序
3. 当增量为1分组排序之后，排序结束

算法分析

1. 时间复杂度
   希尔排序平均时间复杂度O(n1.3)
2. 稳定性
   希尔排序是不稳定的，分组排序时可能会改变相同值的位置关系。

动图

代码实现（Java+Go）

Java版本

public class ShellSort {
	public static int[] shellSort(int[] nums){
		if(nums.length<2) return nums;
		int delta = nums.length/2;
		int i=0,j=0,tmp=0;
		while(delta>=1) {
			for(i = delta;i<nums.length;i++){
				tmp = nums[i];
				j = i- delta;
				while(j>=0 && nums[j]>tmp){
						nums[j+delta] = nums[j];
						j-=delta;
				}
				nums[j+delta] = tmp;
			}
			delta /=2;
		}
        return nums;
	}
	
	public static void show(int[] nums) {
		for(int i =0;i<nums.length;i++) {
			System.out.printf("%d ", nums[i]);
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] nums = {50,70,60,2};
		System.out.println("排序前：");
		show(nums);
		int[] numsSorted = shellSort(nums);
		System.out.println("排序后：");
		show(numsSorted);
	}
}
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

Go版本

package main

import "fmt"

func show(nums []int){
	for _,num:=range nums{
		fmt.Printf("%d ",num)
	}
	fmt.Println()
}

func shellSort(nums[]int)[]int{
	delta := len(nums)/2
	for delta>=1{
		for i:=delta;i<len(nums);i++{
			tmp:=nums[i]
			j:=i-delta
			for j>=0&&nums[j]>tmp{
					nums[j+delta]= nums[j]
					j =j-delta
				}
				nums[j+delta] = tmp
			}
			delta=delta/2
		}

	return nums
	}
	
func main(){
	nums :=[]int{84,83,88,87,61,50,70,60,80,99}
	fmt.Println("排序前：")
	show(nums)
	numsSorted := shellSort(nums)
	fmt.Println("排序后：")
	show(numsSorted)
}
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

基数排序

概念

基数排序，博主理解为换算成相应进制的进制数按位比较排序，如基于2进行排序，那么所有的数换算成二进制，然后从最低位开始按位进行排序。

算法描述

1. 初始状态下，整个序列R[1,2,……,n]处于无序状态，选取其中最大的值计算在基数进制的位数
2. 从最低位开始按照小到大进行排序，用一个计数数组桶保存当前位相同的元素，并根据计数桶排序
3. 当位数到达最大值的最高位进行排序后，排序结束

算法分析

1. 时间复杂度
   如序列最大数基于基数的进制数有n个d位数，且取值范围为[0,k]，再使用计数排序比较元素的每一位，用时Θ(n+k)，基数排序总耗时为Θ(d*(n+k))。
2. 稳定性
   基数排序是稳定的，相同位数的数的顺序没有改变。

动图

代码实现（Java+Go）

Java版本

import java.util.*;
public class RadixSort {
	public static int[] radixSort(int[] nums,int radix){
		if(nums.length<2) return nums;
		
		//先算出radix进制下，本数组最多有多少位数
		int max = 0;
		int len = nums.length;
		int[] tmpNums = new int[len];
		int bucket = radix;
		int i,j,k,digits=0,tmpRadix = 1;
		for(i=0;i<nums.length;i++){
			max = max>nums[i]?max:nums[i];
		}
		while(max!=0){
			max/=radix;
			digits++;
		} 

		for(i=0;i<digits;i++) {
			int[] count_box = new int[bucket];//桶初始化
			for(j=0;j<len;j++) {//按第i位进行放入桶中
				k = (nums[j]/tmpRadix)%bucket;
				count_box[k]++;
			}
			
			for(j=1;j<bucket;j++)//计数
				count_box[j] = count_box[j-1]+count_box[j];
			
			for(j=len-1;j>=0;j--){//排序入位
				k = (nums[j]/tmpRadix)%bucket;
				tmpNums[count_box[k]-1] = nums[j];
				count_box[k]--;
			}
			
			for(j=0;j<len;j++){
				nums[j] = tmpNums[j];
			}
			tmpRadix = radix*tmpRadix;
		}
		return tmpNums;
	}
	
	public static void show(int[] nums) {
		for(int i =0;i<nums.length;i++) {
			System.out.printf("%d ", nums[i]);
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] nums = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};;
		System.out.println("排序前：");
		show(nums);
		int[] numsSorted = radixSort(nums,16);
		System.out.println("排序后：");
		show(numsSorted);
	}
}

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

Go版本

package main

import "fmt"

func show(nums []int){
	for _,num:=range nums{
		fmt.Printf("%d ",num)
	}
	fmt.Println()
}

func radixSort(nums []int,radix int)[]int{
	if(len(nums)<2) {
		return nums
	}

	i,j,k,digits:=0,0,0,0
	bucket := radix
	n := len(nums)
	tmpRadix :=1
	tmpNums := make([]int,n)
	//先找出最大值，计算其最大位数
	max :=nums[0]

	for _,num :=range nums{
		if max<num{
			max = num
		}
	}
	for max!=0{
		max /= radix
		digits++
	}
	//按位进行排序
	for i=0;i<digits;i++{
		count_box :=make([]int,bucket)
		//计数
		for j=0;j<n;j++{
			k = (nums[j]/tmpRadix)%bucket
			count_box[k]++
		}
		for j=1;j<bucket;j++{
			count_box[j] +=count_box[j-1];
		}
		for j = n - 1; j >= 0; j-- {//排序
			k = (nums[j]/tmpRadix)%bucket
			tmpNums[count_box[k]-1] = nums[j]
			count_box[k]--
		}
		for j = 0; j < n; j++ {
			nums[j] = tmpNums[j]
		}
		tmpRadix *= radix//低位转高位
	}
	return nums
}

func main(){
	nums :=[]int{3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
	fmt.Println("排序前：")
	show(nums)
	nums = radixSort(nums,16)
	fmt.Println("排序后：")
	show(nums)
}

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

结语

至此，十大经典排序的大致原理以及实现过程介绍完毕。
本文代码已上传Github：
排序算法
有兴趣朋友可以看看