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 QuickSort(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--
			}
		}
		QuickSort(arr,left,i - 1)
		QuickSort(arr,i + 1,right)
	}
}

归并排序(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++
		}
	}
}