[数据结构与算法]算法自学笔记：基础排序算法

在开始学习排序算法之前，需要先对排序有一些基本认知：

1 除了常见对数字，字符排序，java允许对任何Comparable对象进行比较与排序操作。Comparable是一个接口，要实现此接口需要在类里面实现compareTo方法。该方法获取另一个Comparable对象为参数，如该对象大于其返回正数，等于返回0，小于返回负数。至于比较的具体规则由开发者自定义

comparaTo实现的比较需要为一个全序关系(total order)，全序关系要满足以下性质：
1反对称性(anti-symmetry)
如果 v <= w 且 w <= v， 那么 v = w
2完全性(totality)
v >= w 或者 v <= w 或者两者同时满足（v = w） 不存在其他关系
3传递性（transitivity）
如果 v <= w, w <= x 那么 v <= x

在实现Comparable接口中要注意满足如上关系

1 几个基本操作
在这里封装几个排序基本操作为函数：交换两个元素，比较两个元素，判断数组已经排序成功，输出数组

import edu.princeton.cs.algs4.StdOut;

public class Sorting {

	public static boolean less(Comparable v, Comparable w) {
		return v.compareTo(w) < 0;
	}
	
	
	public static void exch(Comparable[] a, int i, int j) {
		Comparable temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
	
	public static void show(Comparable a[]) {
		for (int i = 0; i < a.length; i++) {
			StdOut.print(a[i] + " ");
		}
		StdOut.println();
	}
	
	
	public static boolean isSorted(Comparable[] a) {
		for (int i = 1; i < a.length; i++) {
			if (less(a[i], a[i - 1])) {
				return false;
			}
		}
		return true;
	}
	

	public static void sort(Comparable[] a) {
		// implement in children classes
	}	

上例将作为排序算法一个模板，所有后续学习的排序算法都会继承此模板

3 选择排序
太简单，这里省略

4插入排序
排序策略：从第一个元素开始，和其上一个元素比较，如果小于上一个元素则交换位置并继续比较，否则停止本轮比较，进入下一个元素

public static void sort(Comparable[] a) {
		for (int i = 1; i < a.length; i++) {
			for (int j = i; j > 0; j--) {
				if (less(a[j], a[j - 1])) {
					exch(a, j, j - 1);
				} else {
					break;	// end this comparing
				}
			}
		}
	}

插入排序在一般情况下比较操作数1/4 N2，交换操作数1/4 N2。注意插入排序的时间复杂度和初始元素顺序有关

部分有序(partially sorted)：
倒置(inversion)指在数组中数学颠倒的两对元素，如数组[1, 2, 4, 3, 6, 9, 5]中倒置元素分别为：4-3 ，5-6, 5-9。如果一个数组倒置元素数量小于c * N时，该数组部分有序
以下为几个部分有序的典例：
1 在一个有序的大数组连上一个小数组
2 数组各个元素距离最终位置不远
3 数组只有个别元素位置不正确
对于部分有序数组插入排序的速率可以快于任何其他排序算法

插入排序在所有元素排序好时为最优情况，比较操作N - 1，交换操作0.在元素倒序排序时为最糟情况，比较操作1/2 N2，交换操作1/2 N2