常见排序算法分类

排序算法种类繁多。根据处理的数据规模与存储特点，可分为内部排序和外部排序：前者处理的数据规模不大，内存足以容纳；后者处理的数据规模较大，必须将数据存放于外部存储器中，每次排序的时候需要访问外存。根据输入的不同形式，分为脱机算法和在线算法：前者待排序的数据是以批处理的形式给出的；而在云计算之类的环境中，待排序的数据是实时生成的，在排序算法开始运行时，数据并未完全就绪，而是随着排序算法本身的进行而逐步给出的。另外，针对不同的体系结构，又分为串行和并行两大类排序算法。根据算法是否采用随机策略，还有确定式和随机式之分。

仅仅用执行效率和内存消耗来衡量排序算法的好坏是不够的。针对排序算法，我们还有一个重要的度量指标，稳定性。这个概念是说，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

一、冒泡排序（Bubble Sort）

1.1 算法描述

冒泡排序是比较相邻两数的大小来完成排序的。这里定义比较边界，也就是进行大小比较的边界。对于长度为n的数组，第一趟的比较边界为[0,n-1]，也就是说从a[0]开始，相邻元素两两比较大小，如果满足条件就进行交换，否则继续比较，一直到最后一个比较的元素为a[n-1]为止，此时第一趟排序完成。以升序排序为例，每趟排序完成之后，比较边界中的最大值就沉入底部，比较边界就向前移动一个位置。所以，第二趟排序开始时，比较边界是[0,n-2]。对于长度为n的序列，最多需要n趟完成排序，所以冒泡排序就由两层循环构成，最外层循环用于控制排序的趟数，最内层循环用于比较相邻数字的大小并在本趟排序完成时更新比较边界。

1.2 代码实现

冒泡排序
 */

//冒泡排序，a是数组，n表示数组大小
func BubbleSort(a []int, n int) {
	if n <= 1 {
		return
	}
	for i := 0; i < n; i++ {
		// 提前退出标志
		flag := false
		for j := 0; j < n-i-1; j++ {
			if a[j] > a[j+1] {
				a[j], a[j+1] = a[j+1], a[j]
				//此次冒泡有数据交换
				flag = true
			}
		}
		// 如果没有交换数据，提前退出
		if !flag {
			break
		}
	}
}

二、插入排序（Insertion Sort）

2.1 算法描述

将待排序的数组划分为局部有序子数组subSorted和无序子数组subUnSorted，每次排序时从subUnSorted中挑出第一个元素，从后向前将其与subSorted各元素比较大小，按照大小插入合适的位置，插入完成后将此元素从subUnSorted中移除，重复这个过程直至subUnSorted中没有元素，总之就时从后向前，一边比较一边移动。

2.2 代码实现

func InsertionSort(a []int, n int) {
	if n <= 1 {
		return
	}
	for i := 1; i < n; i++ {
		value := a[i]
		j := i - 1
		//查找要插入的位置并移动数据
		for ; j >= 0; j-- {
			if a[j] > value {
				a[j+1] = a[j]
			} else {
				break
			}
		}
		a[j+1] = value
	}
}

三、选择排序（Selection Sort）

3.1 算法描述

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

3.2 代码实现

func SelectionSort(a []int, n int) {
	if n <= 1 {
		return
	}
	for i := 0; i < n; i++ {
		// 查找最小值
		minIndex := i
		for j := i + 1; j < n; j++ {
			if a[j] < a[minIndex] {
				minIndex = j
			}
		}
		// 交换
		a[i], a[minIndex] = a[minIndex],a[i]

	}
}

四、归并排序（Merge Sort）

4.1 算法描述

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

4.2 算法实现

func MergeSort(n []int,start,end int){
	if start >= end {
		return
	}

	mid := (start+end)/2
	MergeSort(n,start,mid)
	MergeSort(n,mid+1,end)
	Merge(n,start,mid,end)
}

func Merge(n []int,start,mid,end int){
	var temp []int
	i := start
	k := mid + 1
	j := 0

	for ;i<=mid && k<=end;j++{
		if n[i] < n[k] {
			temp = append(temp,n[i])
			i++
		}else{
			temp = append(temp,n[k])
			k++
		}
	}

	if i > mid {
		temp=append(temp,n[k:end+1]...)
	}else{
		temp = append(temp,n[i:mid+1]...)
	}

	copy(n[start:end+1],temp)
}

五、希尔排序（Shell Sort）

5.1 算法描述

希尔排序基于插入排序发展而来。希尔排序的思想基于两个原因：

1. 当数据项数量不多的时候，插入排序可以很好的完成工作。
2. 当数据项基本有序的时候，插入排序具有很高的效率。

基于以上的两个原因就有了希尔排序的步骤：

a.将待排序序列依据步长(增量)划分为若干组，对每组分别进行插入排序。初始时，step=len/2，此时的增量最大，因此每个分组内数据项个数相对较少，插入排序可以很好的完成排序工作（对应1）。

b.以上只是完成了一次排序，更新步长step=step/2,每个分组内数据项个数相对增加，不过由于已经进行了一次排序，数据项基本有序，此时插入排序具有更好的排序效率(对应2)。直至增量为1时，此时的排序就是对这个序列使用插入排序，此次排序完成就表明排序已经完成。

5.2 代码实现

func ShellSort(n []int,len int){
	step := len/2
	for ; step > 0;step=step/2 {
		for i := step; i < len;i++ {
			j := i-step
			temp := n[i]
			for j>=0 && temp < n[j] {
				n[j+step] = n[j]
				j=j-step
			}
			n[j+step] = temp
		}
	}
}

六、快速排序（Quick Sort）

6.1 算法描述

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

1. 1.在数组中，选择一个元素作为“基准”(pivot),一般选择第一个元素作为基准元素。设置两个游标i和j，初始时i指向数组首元素，j指向尾元素。
2. 从数组最右侧向前扫描，遇到小于基准值的元素停止扫描，将两者交换，然后从数组左侧开始扫描，遇到大于基准值的元素停止扫描，同样将两者交换。
3. i==j时分区完成，否则转2。

6.2 代码实现

func QuickSort(nums []int,start,end int){
	if start >= end {
		return
	}

	mid := partition(nums,start,end)
	QuickSort(nums,start,mid)
	QuickSort(nums,mid+1,end)
}

func partition(nums []int,start,end int)  int{
	temp:= nums[start]
	low := start
	height := end

	for low < height{
		for low < height && temp < nums[height] {
			height--
		}
		if low < height {
			nums[low] = nums[height]
		}

		for low < height && temp > nums[low] {
			low++
		}

		if low < height {
			nums[height] = nums[low]
		}
	}

	nums[low] = temp

	return low
}

七、堆排序（Heap Sort）

7.1 算法描述

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

• 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
• 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
• 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

7.2 代码实现

func initHead(nums []int,parent,len int){
	temp := nums[parent]
	child := 2*parent+1

	for child < len {
		if child+1 < len && nums[child] < nums[child+1] {
			child++
		}

		if child < len && nums[child] <= temp {
			break
		}

		nums[parent] = nums[child]

		parent = child
		child = child*2+1
	}

	nums[parent] = temp
}

func HeadSort(nums []int){
	for i := len(nums)/2; i>=0; i-- {
		initHead(nums,i,len(nums))
	}

	for i := len(nums)-1;i >0; i--{
		nums[0],nums[i] = nums[i],nums[0]

		initHead(nums,0,i)
	}
}