sort

排序算法

冒泡的算法

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成.

## 举例说明

arr = [24,69,80,57,13]

第一轮比较
第1次比较：24<69
第2次比较：69<80
第3次比较：80>57 --> [24,69,57,80,13] 
第4次比较：80>13 --> [24,69,57,13,80] 
第二轮比较
第1次比较：24<69
第2次比较：69>57 --> [24,57,69,13,80]
第3次比较：69>13 --> [24,57,13,69,80]
第三轮比较
第1次比较：24<57
第2次比较：57>13 --> [24,13,57,69,80]
第四轮比较
第1次比较：24>13 --> [13,24,57,69,80]

## 描述
1. 冒泡排序会经过arr.length-1轮次比较，每一轮会确认一个数字
2. 每一轮次数都会减少[4,3,2,1]
3. 当发现前面的数大于后面的数，就进行交换

源码bubble

选择排序

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

## 描述

1. 选择排序会经过arr.length-1轮次比较，每一轮会确认一个数字
2. 第i趟排序，在i+1到arr.length进行查找，找到最小的便放在i的位置上。
3. n-1次排序即可借宿

源码select

插入排序

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5

1. 插入排序会经过arr.length-1次比较，一轮排序完毕
2. 在第i次比较时,前i-1次序列已经排序完成，arr[i]<arr[i-1],借宿比较;
3. arr[i]>arr[i-1]时，arr[i] 交换 arr[i-1],在进行a[i-1]与a[i-2]
交换次数太多,优化方案
0. insertval := arr[i]//暂存arr[i]这个要插入的数据
1. 如果j=i-1;j>0 && arr[j] < insertval /*左边的数比要插入的数据小 */; j--;
2. arr[j+1]=arr[j]将arr[j]右移一位.

源码insertion

快速排序

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。

步骤为：

挑选基准值：从数列中挑出一个元素，称为“基准”（pivot），
分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成，
递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。
递归到最底部的判断条件是数列的大小是零或一，此时该数列显然已经有序。

选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。

package  main

func qsort(data []int) {
	if len(data) <= 1 {
		return
	}
	mid := data[0]
	head, tail := 0, len(data)-1
	for i := 1; i <= tail; {
		if data[i] > mid {
			data[i], data[tail] = data[tail], data[i]
			tail--
		} else {
			data[i], data[head] = data[head], data[i]
			head++
			i++
		}
	}
	qsort(data[:head])
	qsort(data[head+1:])
}

借用wiki百科的一张图

quickSort代码

mergeSort

采用分治的典型算法