算法与数据结构—排序

插入排序，冒泡排序，堆排序，哈希排序，快速排序，外排序，选择排序

最常用的：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。

排序算法的衡量指标：时间复杂度，空间复杂度，稳定性

  1. 会分析最好情况、最坏情况、平均情况时间复杂度
    • 时间复杂度的系数、常数 、低阶。在对同一阶时间复杂度的排序算法性能对比的时候，我们就要把系数、常数、低阶也考虑进来。
  2. 比较次数和交换（或移动）次数
  3. 排序算法的内存消耗
    • 原地排序：指空间复杂度是 O(1) 的排序算法
  4. 排序算法的稳定性：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

冒泡排序

从头开始遍历，前面的比后面相邻的大，就交换。第一次冒泡出最大的，依次进行。 提前退出标志：当某次遍历没有数据交换时，说明已经有序了，可以退出。问：

  1. 冒泡排序是原地排序算法吗？ 答：只涉及相邻数据的交换操作，只需要常量级的临时空间，空间复杂度为 O(1)，是一个原地排序算法。
  2. 冒泡排序是稳定的排序算法吗？ 答：只有前面比后面大才交换，是稳定排序
  3. 时间复杂度? 最好：无需交换，遍历1次就好O(n)；最坏时刚好倒数，要进行n次遍历 O(n^2)。
// 冒泡排序，从前往后依次比较相邻的，后面的大就交换（大的往后移）。
// 提前退出条件，当某次遍历没有交换时，结束（说明都满足后面比前面的大了）。
func Bubble2(in []int) (out []int) {
	length := len(in)
	for i := 0; i < length; i++ {
		exit := true
		for j := 0; j < length - i - 1; j++ {
			if in[j + 1] < in[j] {
				in[j], in[j + 1] = in[j + 1], in[j]
				exit = false
			}
		}
		if exit == true {
			break
		}
	}
	out = in
	return
}

有序度

有序元素对：如果 i < j, 且a[i] <= a[j],则为有序，反之无序；一组数组中有序元素对的个数，即为有序度。 完全有序的数组的有序度叫作满有序度.即 n*(n-1)/2 满有序度 = 有序度 + 逆序度 排序的过程就是一种增加有序度，减少逆序度的过程，最后达到满有序度.

插入排序

把一组数据，插入一个有序集合中。 数组前面作为有序区，后面的数据与前面的进行比较，大则往后搬，直到找到合适的位置。 原地排序， 稳定排序，时间复杂度O(n^2)

//插入排序
public static void insertSort(int[] a) {
	int i,j, n, tmp;
	n = a.length;
	for (i = 1; i < n; i++) {
		tmp = a[i];
		for (j = i - 1; j >= 0; j--) {
			if (a[j] > tmp) {
				//把比大的数据往后搬
				a[j + 1] = a[j];
			} else {
				break;
			}
			//数据插入有序区
			a[j] = tmp;
		}
	}
}

选择排序

类似插入排序，分为前面已排序区和后面未排序区；每次从后面未排序选出最小的元素放入已排序区的末尾。 原地排序， 不是稳定排序，时间复杂度O(n^2)

// 选择排序，a表示数组，n表示数组大小
 public static void selectSort(int[] a, int n) {
   if (n <= 1) return;
   for (int i = 0; i < n - 1; ++i) {
     // 查找未排序区最小值
     int minIndex = i;
     for (int j = i + 1; j < n; ++j) {
       if (a[j] < a[minIndex]) {
         minIndex = j;
       }
     }
     //找出未排序区最小的，并且和未排序区第一个交换位置，实现扩大已排序区的范围
     //因为这步造成了，选择排序不稳定。如果要维持稳定性，就需要往后搬移数据。而不是交换位置。
     int tmp = a[i];
     a[i] = a[minIndex];
     a[minIndex] = tmp;
   }
 }

归并排序（Merge Sort）

我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，递归分解成更小的分组，再将排好序的两部分合并在一起。

归并排序很稳定，与原数组有序度无关，时间总是o(nlogn), 但是缺点是，不是原地排序，需要额外的空间。空间复杂度O(n), 注：空间复杂不是像时间那样把所有的加起来。过程中最大的即为O(n),

分治算法

把一个任务分解成多个小任务执行，再合并起来。治算法一般都是用递归来实现的。

递归时间复杂度分析(以归并排序为例)

假设设对 n 个元素进行归并排序需要的时间是 T(n)，那分解成两个子数组排序的时间都是 T(n/2)。merge() 函数合并两个有序子数组的时间复杂度是 O(n)。
T(1) = C；   n=1 时，只需要常量级的执行时间，所以表示为常数 C。
T(n) = 2*T(n/2) + n； n>1

T(n) = 2*T(n/2) + n
     = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
     = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
     = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
     ......
     = 2^k * T(n/2^k) + k * n   # 终止条件
     ......

分家k次，到最后，有T(n/2^k)=T(1)， => n/2^k=1， k=logn, =>  T(n)=C·logn + nlogn

// 归并排序
// 分致思想
// 把一个数组拆成最小粒度，就相当于每个数一组，每组内都是有序的，
// 然后把分组，两两合并成有序分组不断合并，最终合成一个有序的数组，类似二叉树一样，
func Merge(startIdx, endIdx int, in []int) {
	//fmt.Println(startIdx, endIdx)
	if startIdx >= endIdx {
		return
	}
	midIdx := (startIdx + endIdx)/2

	Merge(startIdx, midIdx, in)
	Merge(midIdx + 1, endIdx, in)

	merge(startIdx, midIdx, endIdx, in)
}

// 合并相邻的数组区间，并且区间内的数组是有序的
func merge(startIdx,  midIdx, endIdx int, in []int) {
	tmp := make([]int, 0, endIdx - startIdx + 1)

	//依次找出两个区间较小的数放入 tmp
	i, j := startIdx, midIdx + 1
	for ;i <= midIdx && j <= endIdx; {
		if in[i] <= in[j] {
			tmp = append(tmp, in[i])
			i++
		} else {
			tmp = append(tmp, in[j])
			j++
		}
	}

	if i <= midIdx {
		//for i <= midIdx {
		//	tmp = append(tmp, in[i])
		//	i++
		//}
		tmp = append(tmp, in[i:midIdx+1]...)
	}
	if j <= endIdx {
		//for j <= endIdx {
		//	tmp = append(tmp, in[j])
		//	j++
		//}
		tmp = append(tmp, in[j:endIdx+1]...)
	}

	//把数据复制会原数组
	for i := 0; i < len(tmp); i++ {
		in[startIdx+i] = tmp[i]
	}
}

快速排序

如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，中间是 pivot，位置确定。再左右分区重复如此。 原地排序，涉及数据搬移.

快排时间分析(自己思路)

理想状态，每个临界点正好把数组分成相等的两部分，(为了避免额外的内存消耗，也为了避免数据搬移，通过数据交换实现，牺牲稳定性) , 每次只需遍历每个区间的值n/2即可, 每次分解下一层就确定一个数据的位置。一共logn层。每层n次遍历。的nlogn; 最差时，数组逆序，二叉树退化为线性，每次遍历n，一共n层。n^2

归并&&快排

  1. 归并时从下到上，先排序子区间，再一次合并到上一级；而快排相反，先上一级有序，再处理子问题。
  2. 归并更稳定，但是不是原地排序消耗内存太大。而快排空间复杂度是O(1)

比较次数，交换次数 是否需要额外内存空间 减少数组数据的搬移，可能需交换代替，交换可能导致排序不稳定 是否能维持排序稳定性

// 快速排序，
// 原地排序，有数据交换不是稳定排序
// 时间复杂度 O(nlogn)

func QuickSort(left, right int, in []int) {
	if left >= right {
		return
	}
	n := partition(left, right, in)
	QuickSort(left, n - 1, in)
	QuickSort(n + 1, right, in)
}

// 确定临界值 pivot 的位置，即左边小于 pivot，右边大于 pivot
func partition(left, right int, in []int) int {
	n := left
	pivot := in[right]  // 以最右边为参考

	//遍历区间，把小于临界值pivot的都搬到左边
	for i := left; i < right; i++ {
		if in[i] < pivot {
			in[i], in[n] = in[n], in[i]
			n++
		}
	}

	// 把临界值方到对应的位置，从而实现 左边比临界值小，右边比临界值大(等)， 这样临界值定位置就固定了
	in[n], in[right] = in[right], in[n]
	return n
}

桶排序 (Bucket sort)

有n个元素，m个桶，每个桶之间大小有序，且范围不重合。 把n个元素按大小放到不同的桶里，桶内在进行快排. 当m和n无限接近时，等于每个桶一个元素，理想情况时间O(n)

T = m * n/m * log(n/m) = nlog(n/m) => O(n)

只有一个桶时就变成了快排。此外，最好每个桶的数据数都比较均匀， 桶排序、计数排序、基数排序时间复杂度都是线性的，之所以快，它们不是基于比较的排序算法。不涉及元素之间的比较。 桶排序比较适合用在外部排序中。

计数排序

当数据的区间分布比较小时，比如100万人的年龄排行，直接把年龄当做桶bucket，把对应的年龄方进入，即可得到顺序。甚至直接统计每个桶（年龄）的人数

基数排序

基于数据的位数排序。比较对10万手机号排序。先按个位排序，再按十位排序，一次类推。权重大的放后面排。每次遍历都用桶排序，申请0到9的bucket（桶），时间复杂度O(n);经过11次遍历就有序了。总时间为O(k*n),k为待排数据长度，如果k不是很大，比如手机号11，还是能近似人为时间复杂度为O(n)

堆排序

堆 完全二叉树，用数组存储实现，父节点总是大于子节点（大顶堆）

建堆和堆调整

建堆，从n/2开始往前，进行对调整； 堆调整，父节点与子节点比较，小于大儿子则与之交换。 经过n/2次堆调整，保证了堆顶最大，第二大的一定在第二层。

复杂度分析：原地排序，空间复杂度常量阶O(1) ； 时间，建堆O(n/2)即 O(n), 排序过程中要不断进行堆调整每次O(logn)故最终时间复杂度为O(nlogn).

是稳定排序吗？不是，在排序的过程，存在将堆的最后一个节点跟堆顶节点互换的操作(把末尾当做已排序区，每次取出堆顶的数据放进去)，破坏了稳定性。

public class HeapSort {
	//堆排序
	public void sort(int[] arr, int n) {
		int k = n;
		int tmp;
		buildHeap(arr, k);//建堆
		while (k > 1) {
			tmp = arr[1];
			arr[1] = arr[k];	//把当前堆最大的与末尾的交换,末尾算作已排序区
			arr[k] = tmp;
			k--;
			heapify(arr, k, 1);
		}
		
	}
			
	//建堆
	public void buildHeap(int[] a, int n) {
		for (int i = n/2; i >= 1; i--) {
			heapify(a, n, i);
		}
	}
	
	//堆调整,当前节点与子节点比较，小于大儿子节点，则交换
	public void heapify(int[] a, int n, int i) {
		int maxPos = i;
		while (true) {
			if (2*i <= n && a[2*i] > a[i])
				maxPos = 2*i;
			if (2*i + 1 <= n && a[2*i+1] > a[maxPos])
				maxPos = 2*i + 1;
			if (i == maxPos)
				break;	//已经满足父节点大于子节点或者无子节点时退出
			swap(a, i, maxPos);
			i = maxPos;
		}
	}
	
	private void swap(int[] arr, int a, int b) {
		int tmp;
		tmp = arr[a];
		arr[a] = arr[b];
		arr[b] = tmp;
	}		
}

堆排序

建堆和堆调整，每次把最大的放到数组后面

//堆排序
public void sort(int[] arr, int n) {
	int k = n;
	int tmp;
	buildHeap(arr, k);
	while (k > 1) {
		tmp = arr[1];
		arr[1] = arr[k];	//把当前堆最大的与末尾的交换
		arr[k] = tmp;
		k--;
		heapify(arr, k, 1);
	}
}

堆应用

  • 优先级队列
  • topN
  • 利用堆求中位数 （分别一个大顶堆和小顶堆各维护一半的数据）； 对于中位数，在这组数据中，有一半的数据比他大，有一半的数据比他小
  • 定时器任务，（避免不停的轮训任务看是否到时间）

拓扑排序

见数据结构“图”

更新时间: