基础算法

[itcuihao]

冒泡排序

• 它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换。

• 算法的平均时间复杂度为O(n^2)。

• 但是若在某趟排序中未发现气泡位置的交换，则说明待排序的无序区中所有气泡均满足轻者在上，重者在下的原则，即为正序。则冒泡排序过程可在此趟扫描后就终止，基于这种考虑，提出了第一种改进的算法。

func bubblesort(items []int) {
	var (
		n      = len(items)
		sorted = false
	)
	for !sorted {
		swapped := false
		for i := 0; i < n-1; i++ {
			if items[i] > items[i+1] {
				items[i+1], items[i] = items[i], items[i+1]
				swapped = true
			}
		}
		if !swapped {
			sorted = true
		}
		n = n - 1
	}
}

快速排序

• 快速排序是一种排序算法，对包含n个数的输入数组，平均时间为O（nlgn），最坏情况是O（n^2）。

• 快速排序时基于分治模式处理的，在数据集之中，选择一个元素作为”基准”（pivot），所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。这个操作称为分区
  (partition) 操作，分区操作结束后，基准元素所处的位置就是最终排序后它的位置。对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

• 快排的局限性：快排是一个效率很高的排序算法，但是对于长度很小的序列，快排效率低；pivot选择不当，将导致树的不平衡，这样导致快排的时间复杂度为o(n^2)；当数组中有大量重复的元素，快排效率将非常之低；改进方法可以参考java.util.DualPivotQuicksort：小数组使用插入排序、双枢轴（快速三向切分）、划分策略优化（五取样划分）。

func quicksort(a []int) []int {
	if len(a) < 2 {
		return a
	}
	left, right := 0, len(a)-1
	// 基准元素
	pivot := rand.Int() % len(a)
	// 如果基准不再数组末尾，则把基准移到末尾
	if pivot != len(a) {
		a[pivot], a[right] = a[right], a[pivot]
	}

	// 然后从左到右（除了最后的基准元素），循环移动小于等于基准元素的元素到数组的开头，每次移动 left 自增 1，表示下一个小于基准元素将要移动到的位置。
	for i, _ := range a {
		if a[i] < a[right] {
			a[left], a[i] = a[i], a[left]
			left++
		}
	}

	// 循环结束后 left 所代表的的位置就是基准元素的所有摆放的位置。所以最后将基准元素所在位置（这里是 right）与 left 所代表的的位置的元素交换位置。
	a[left], a[right] = a[right], a[left]

	quicksort(a[:left])
	quicksort(a[left+1:])

	return a
}