常用排序算法总结

基础类：

public abstract class Sorter<E extends Comparable<E>> {
    public abstract void sort(E[] array, int from, int len);

    public final void sort(E[] array) {
        sort(array, 0, array.length);
    }

    protected final void swap(E[] array, int from, int to) {
        E tmp = array[from];
        array[from] = array[to];
        array[to] = tmp;
    }
}

------------------------------------------------------------------------------------------------------------------------------------------

一、插入排序[稳定]

· 这里说的是直接插入排序，该算法在数据规模小的时候十分高效；
· 基本思想：将n个元素的数列分为已有序和无序两个部分。每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较,找出插入位置,将该元素插入到有序数列的合适位置中；
· 算法步骤：
    1、从有序数列{a1}和无序数列{a2,a3,…,an}开始进行排序；
    2、处理第i个元素时(i=2,3,…,n),数列{a1,a2,…,ai-1}是已有序的,而数列{ai,ai+1,…,an}是无序的。用ai与ai-1、ai-2,…,a1进行比较,找出合适的位置将ai插入；
    3、重复2，共进行n-1的插入处理，数列全部有序。

· 代码：

public class InsertSorter<E extends Comparable<E>> extends Sorter<E> {
    public void sort(E[] array, int from, int len) {
        int j;
        E tmp;
        for (int i = from + 1; i < from + len; i++) {
            tmp = array[i];
            j = i;
            for (; j > from; j--) {
                if (tmp.compareTo(array[j - 1]) < 0) {
                    array[j] = array[j - 1];
                } else break;
            }
            array[j] = tmp;
        }
    }
}

------------------------------------------------------------------------------------------------------------------------------------------

二、冒泡排序[稳定]

· 基本思想：通过两两比较待排序元素，若为逆序（递增或递减）则进行交换，将待排序元素从左至右比较一遍称为一趟“冒泡”。每趟冒泡都将待排序列中的最大关键字交换到最后（或最前）位置。直到全部元素有序为止；
· 算法步骤[正序排列]：
    1、将关键字按纵向排列，然后自下而上地对每两个相邻的关键字进行比较，若为逆序(即kj-1>kj)，则将两个记录交换位置，这样的操作反复进行，直至全部记录都比较、交换完为止。一趟冒泡处理，就将关键字最小的记录安排在第一记录的位置上；
    2、对后n-1个记录重复同样操作，再将次小关键字记录安排在第二个记录的位置上；
    3、重复上述过程直至没有记录需要交换为止。

· 代码：

public class BubbleSorter<E extends Comparable<E>> extends Sorter<E> {
    public void sort(E[] array, int from, int len) {
        for (int i = from; i < from + len; i++) {
            for (int j = from + len - 1; j > i; j--) {
                if (array[j].compareTo(array[j - 1]) < 0) {
                    swap(array, j - 1, j);
                }
            }
        }
    }
}

------------------------------------------------------------------------------------------------------------------------------------------

三、归并排序[稳定]

· 基本思想：将两个（或两个以上）有序表合并成一个新的有序表：即把待排序序列分为若干个子序列，每个子序列是有序的，然后再把有序子序列合并为整体有序序列；将已有序的子序列合并，得到完全有序的序列：即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并；
· 算法步骤[正序排列]：
    1、把待排序的n个记录看作是长度为1的有序序列。将相邻子序列两两归并为长度为2的有序序列；
    2、把得到的n/2个长度为2的有序子序列再归并为长度为 2*2 的有序序列；
    3、按2的方式，重复对相邻有序子序列进行归并操作，直到成为一个有序序列为止。

· 代码：

public class MergeSorter<E extends Comparable<E>> extends Sorter<E> {

    public void sort(E[] array, int from, int len) {
        if (len <= 1) return;
        E[] temporary = (E[]) Array.newInstance(array[0].getClass(), len);
        merge_sort(array, from, from + len - 1, temporary);

    }

    private void merge_sort(E[] array, int from, int to, E[] temporary) {
        if (to <= from) {
            return;
        }
        int middle = (from + to) / 2;
        merge_sort(array, from, middle, temporary);
        merge_sort(array, middle + 1, to, temporary);
        merge(array, from, to, middle, temporary);
    }

    private void merge(E[] array, int from, int to, int middle, E[] temporary) {
        int k = 0, leftIndex = 0, rightIndex = to - from;
        System.arraycopy(array, from, temporary, 0, middle - from + 1);
        for (int i = 0; i < to - middle; i++) {
            temporary[to - from - i] = array[middle + i + 1];
        }
        while (k < to - from + 1) {
            if (temporary[leftIndex].compareTo(temporary[rightIndex]) < 0) {
                array[k + from] = temporary[leftIndex++];
            } else {
                array[k + from] = temporary[rightIndex--];
            }
            k++;
        }
    }
}