选择排序：O(n^2) 不稳定

a={5,2,8,4,9,1}

第一趟i=0：最小1,1和5交换：1,   2,8,4,9,5

第二趟i=1：最小2,                  1,2,   8,4,9,5

第三趟i=2：最小4,4和8交换：1,2,4,     8,9,5

第四趟i=3：最小5,5和8交换：1,2,4,5,    9,8

第五趟i=4：最小8,8和9交换：1,2,4,5,8,   9

public static void selectSort(int[] a){for (int i = 0; i < a.length; i++) {int k=i;for (int j = k; j < a.length; j++) {if(a[k]>a[j]){k=j;}}if(i!=k){int temp = a[i];a[i]=a[k];a[k]=temp;}}}

堆排序：o(nlogn) 不稳定

 

冒泡排序：O(n)~O(n^2) 稳定

public static void bubbleSort(int[] a){        for (int i = 0; i < a.length; i++) {            for (int j = 0; j < a.length-i-1; j++) {                if(a[j]>a[j+1]){                    int temp=a[j];                    a[j]=a[j+1];                    a[j+1]=temp;                }            }        }    }

 

快速排序：O(nlogn) 不稳定

比如：对R={37, 40, 38, 42, 461, 5, 7, 9, 12}进行一趟快速排序的过程如下(注:下面描述的内容中元素下表从 0 开始)：

开始选取基准 base = 37，初始位置下表 low = 0 ， high = 8  ， 从high=8，开始如果R[8] < base ,  将high位置中的内容写入到R[low]中, 将high位置空出来, low = low +1 ;

从low开始探测，由于low=1 ， R[low] > base ,所以将R[low]写入到R[high] , high = high -1 ;

检测到low < high ,所以第一趟快速排序仍需继续:

此时low=1，high=7，因为 R[high] < base ,所以将 R[high] 写入到到R[low]中,low = low + 1;

从low开始探测,low = 2 , R[low] >base ,所以讲R[low]写入到R[high]，high=high-1;

继续检测到 low 小于high

此时low=2，high=6，同理R[high] < base ,将R[high] 写入到R[low]中，low=low+1;

从low继续探测,low = 3 , high=6 , R[low] > base , 将R[low]写入到R[high]中，high = high-1;

继续探测到low小于high

此时low=3，high=5，同理R[high] < base,将R[high]写入到R[low]中，low = low +1；

从low继续探测，low = 4，high=5，由于R[low] > base , 将R[low]写入到R[high]中，high = high -1 ;

此时探测到low == high == 4 ；该位置即是base所在的位置，将base写入到该位置中.

然后再对子序列Rs1 = {12,9,7,5} 和 Rs2={461,42,38,40}做一趟快速排序，直到Rsi中只有一个元素，或没有元素。

private static boolean isEmpty(int[] n) {        return n == null || n.length == 0;    }    // ///    /**     * 快速排序算法思想——挖坑填数方法：     *      * @param n 待排序的数组     */    public static void quickSort(int[] n) {        if (isEmpty(n))            return;        quickSort(n, 0, n.length - 1);    }    public static void quickSort(int[] n, int l, int h) {        if (isEmpty(n))            return;        if (l < h) {            int pivot = partion(n, l, h);            quickSort(n, l, pivot - 1);            quickSort(n, pivot + 1, h);        }    }    private static int partion(int[] n, int start, int end) {        int tmp = n[start];        while (start < end) {            while (n[end] >= tmp && start < end)                end--;            if (start < end) {                n[start++] = n[end];            }            while (n[start] < tmp && start < end)                start++;            if (start < end) {                n[end--] = n[start];            }        }        n[start] = tmp;        return start;    }