《算法》之排序

排序

    把计算机全部的功能进行最终细化，归类，可以分成三种基本功能：存储、计算和通信。存储数据是为了更好的查找数据，显然，在一大堆数据里面找到我们想要的是一件很费时间的事，但若是数据是有序排列的，那将会大大节省我们的时间。

    排序就是将一组对象按照某种逻辑顺序重新排序的过程。

    排序在商业数据处理和现代科学计算中有着重要的地位，可以应用于事物处理、组合优化、天体物理学、分子动力学、语言学、基因组学、天气预报和很多其他领域。

选择排序

    选择排序，也叫冒泡排序，每一次排序遍历一次全部数据，然后把其中最小（或者最大）的元素标记出来，遍历完一次之后，把该元素放到数组前面。

    该排序算法时间复杂度为O(n²)

    public static void sort(Comparable[] a) {        int n = a.length;        for (int i = 0; i < n; i++) {            int min = i;            for (int j = i+1; j < n; j++) {                if (less(a[j], a[min])) min = j;//比较            }            exch(a, i, min);//交换        }    }
插入排序
    遍历数组，把当前数据与前面元素相比较，插入恰当的位置，形成局部有序的状态。
    算法的复杂度与数据有序程度有关，最坏的情况是O(n2)
    public static void sort(Comparable[] a) {        int n = a.length;        for (int i = 0; i < n; i++) {            for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {                exch(a, j, j-1);            }        }    }
希尔排序
    希尔排序是一种基于插入排序的快速排序，希尔排序的思想是使数组中的任意间隔为h的元素都有序。
    public static void sort(Comparable[] a) {        int n = a.length;        int h = 1;        while (h < n/3) h = 3*h + 1;         while (h >= 1) {            for (int i = h; i < n; i++) {                for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) {                    exch(a, j, j-h);                }            }            h /= 3;        }    }
归并排序
    自顶向下归并排序将一组数据不断二分，一分二，二分四，四分八，然后从最小的元素开始比较，逐渐归并。
    自顶向下归并排序的时间复杂度为O(NlgN)，空间复杂度为O(N)。
    public static void sort(Comparable[] a) {        Comparable[] aux = new Comparable[a.length];        sort(a, aux, 0, a.length-1);    }
    PRivate static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {        if (hi <= lo) return;        int mid = lo + (hi - lo) / 2;        sort(a, aux, lo, mid);        sort(a, aux, mid + 1, hi);        merge(a, aux, lo, mid, hi);    }
    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {        for (int k = lo; k <= hi; k++) {            aux[k] = a[k];         }        int i = lo, j = mid+1;        for (int k = lo; k <= hi; k++) {            if      (i > mid)              a[k] = aux[j++];            else if (j > hi)               a[k] = aux[i++];            else if (less(aux[j], aux[i])) a[k] = aux[j++];            else                           a[k] = aux[i++];        }    }    自底向上归并排序是以分治思想实现排序，将数组中的元素两两归并排序，然后翻倍，直到长度超过数组。
    自底向上归并排序时间复杂度为O(NlgN)，空间复杂度为O(N)。
    public static void sort(Comparable[] a) {        int n = a.length;        Comparable[] aux = new Comparable[n];        for (int len = 1; len < n; len *= 2) {            for (int lo = 0; lo < n-len; lo += len+len) {                int mid  = lo+len-1;                int hi = Math.min(lo+len+len-1, n-1);                merge(a, aux, lo, mid, hi);            }        }    }
    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {        for (int k = lo; k <= hi; k++) {            aux[k] = a[k];         }        int i = lo, j = mid+1;        for (int k = lo; k <= hi; k++) {            if      (i > mid)              a[k] = aux[j++];            else if (j > hi)               a[k] = aux[i++];            else if (less(aux[j], aux[i])) a[k] = aux[j++];            else                           a[k] = aux[i++];        }    }
快速排序
     快速排序是一种分治排序，它将一个数组分成两个子数组，两部分独立排序，当这两部分自然有序时，排序就完成了。用一个切分元素，切分两个数组，将小于切分元素的放前面，大于切分元素的放后面。
    时间复杂度为O(NlgN)。
    public static void sort(Comparable[] a) {        StdRandom.shuffle(a);//消除对输入的依赖        sort(a, 0, a.length - 1);    }    private static void sort(Comparable[] a, int lo, int hi) {         if (hi <= lo) return;        int j = partition(a, lo, hi);        sort(a, lo, j-1);        sort(a, j+1, hi);    }
    private static int partition(Comparable[] a, int lo, int hi) {        int i = lo;        int j = hi + 1;        Comparable v = a[lo];        while (true) {             while (less(a[++i], v))                if (i == hi) break;            while (less(v, a[--j]))                if (j == lo) break;               if (i >= j) break;            exch(a, i, j);        }        exch(a, lo, j);        return j;    }