類別	排序方法	平均情況	最好情況	最壞情況	空間復(fù)雜度	穩(wěn)定性
插入排序	插入排序					穩(wěn)定
插入排序	Shell排序					不穩(wěn)定
選擇排序	選擇排序					不穩(wěn)定
選擇排序	堆排序					不穩(wěn)定
交換排序	冒泡排序					穩(wěn)定
交換排序	快速排序					不穩(wěn)定
歸并排序	歸并排序					穩(wěn)定
基數(shù)排序	基數(shù)排序					穩(wěn)定

基數(shù)排序中r代表關(guān)鍵字的基數(shù)，d代表長度瓤鼻，n代表關(guān)鍵字的個數(shù)

package com.sort_algorithm;

import java.util.Arrays;

public class SortSummarize {

    public static void main(String[] args) {
        int[] a = { 9, 8, 7, 6, 5, 1, 3, 0, 10, -1, 99, -10 };
        int[] b = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 16 };
        // 將a的地址也就是引用給了b弛随，使b的引用發(fā)生了改變疫稿。此時打印铁坎，其實打印的是同一個地址下的數(shù)組碳抄，
        // 此時a、b都指向a的值舌稀，原來的b數(shù)組會因為沒有被引用到啊犬，被JVM的GC回收
        b = a;
        // 將b的地址也就是引用給了a，使a的引用發(fā)生了改變壁查。此時打印觉至，其實打印的是同一個地址下的數(shù)組，
        // 此時a睡腿、b都指向b的值语御，原來的a數(shù)組會因為沒有被引用到，被JVM的GC回收
        // a = b;
        print("選擇排序 ", selectSort(a));
        print("冒泡排序 ", bubbleSort(b));
        print("插入排序 ", insertSort(b));
        print("歸并排序 ", mergeSort(b));
        print("希爾排序 ", shellSort(b));
        print("堆排序 ", heapSort(b));
        print("快速排序 ", quickSort(b));
    }

    /**
     * 冒泡排序算法：每次將最小的一個數(shù)”浮“上去 最好情況O(n),即數(shù)組本身有序 最壞情況O(n^2)
     */
    public static int[] bubbleSort(int[] a) {
        a = Arrays.copyOf(a, a.length);

        int count = 0;
        boolean terminated = false;

        for (int i = 0; i < a.length - 1 && !terminated; i++) {
            terminated = true;
            for (int j = a.length - 2; j >= i; j--) {
                count++;
                if (a[j] > a[j + 1]) {
                    swap(a, j + 1, j);
                    terminated = false;
                }
            }
        }
        System.out.println("冒泡排序比較次數(shù): " + count);
        return a;
    }

    /**
     * 選擇排序：每次選出待排序中最小的一個
     */
    public static int[] selectSort(int[] a) {
        a = Arrays.copyOf(a, a.length);

        int count = 0;
        for (int i = 0; i < a.length - 1; i++) {
            int min = a[i];
            int minIndex = i;
            for (int j = i + 1; j < a.length; j++) {
                count++;
                if (a[j] < min) {
                    minIndex = j;
                    min = a[j];
                }
            }
            swap(a, i, minIndex);
        }
        System.out.println("選擇排序比較次數(shù): " + count);
        return a;
    }

    public static int[] insertSort(int[] a) {
        a = Arrays.copyOf(a, a.length);

        int count = 0;
        for (int i = 1; i < a.length; i++) {// i之前有序,i指向待排序的元素
            if (a[i] < a[i - 1]) {
                int temp = a[i];
                int j = i - 1;// j指向當(dāng)前元素的前一個
                for (; j >= 0 && a[j] > temp; j--) {
                    count++;
                    a[j + 1] = a[j];
                }
                a[j + 1] = temp;
            }
        }

        System.out.println("插入排序比較次數(shù): " + count);
        return a;
    }

    private static void swap(int[] a, int i, int j) {
        if (i == j)
            return;
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    /**
     * 希爾排序
     * 
     * @param a
     * @return
     */
    public static int[] shellSort(int[] a) {
        a = Arrays.copyOf(a, a.length);
        int count = 0;

        int increment = a.length;
        do {
            increment = increment / 3 + 1;
            for (int i = increment; i < a.length; i = i + increment) {
                if (a[i] < a[i - increment]) {
                    int temp = a[i];
                    int j = i - increment;
                    for (; j >= 0 && a[j] > temp; j -= increment) {
                        count++;
                        a[j + increment] = a[j];
                    }
                    a[j + increment] = temp;
                }
            }
        } while (increment > 1);

        System.out.println("希爾排序比較次數(shù)： " + count);
        return a;

    }

    /**
     * 堆排序
     * 
     * @param a
     * @return
     */
    public static int[] heapSort(int[] a) {
        a = Arrays.copyOf(a, a.length);
        int length = a.length;
        for (int i = length / 2 - 1; i >= 0; i--)// 2*i+1<=length-1,最后一個有左孩子的節(jié)點
            heapAdjust(a, i, length);

        for (int i = length - 1; i >= 0; i--) {
            swap(a, 0, i);
            heapAdjust(a, 0, i);//
        }

        return a;
    }

    // 每次將以i為root的子樹滿足最大堆特性;i指向待調(diào)整的節(jié)點
    private static void heapAdjust(int[] a, int i, int length) {
        int temp = a[i];

        for (int j = 2 * i + 1; j < length; j = 2 * i + 1) {// 剛開始時指向左孩子
            if (j + 1 < length && a[j + 1] > a[j])// 如果有做右孩子席怪，且右孩子比左孩子大
                j++;// j指向左右孩子中值較大的一個

            if (temp >= a[j])
                break;
            a[i] = a[j];

            i = j;
        }
        a[i] = temp;
    }

    public static int[] mergeSort(int[] a) {
        a = Arrays.copyOf(a, a.length);
        int[] aux = new int[a.length];
        mergeSort(a, aux, 0, a.length - 1);
        return a;
    }

    private static void mergeSort(int[] a, int[] aux, int lo, int high) {
        if (lo >= high)
            return;

        int mid = (lo + high) / 2;
        mergeSort(a, aux, lo, mid);
        mergeSort(a, aux, mid + 1, high);
        merge(a, aux, lo, mid, high);
    }

    private static void merge(int[] a, int aux[], int lo, int mid, int high) {
        for (int i = lo; i <= high; i++) {
            aux[i] = a[i];
        }

        int lo_h = mid + 1;
        for (int i = lo; i <= high; i++) {
            if (lo > mid)
                a[i] = aux[lo_h++];
            else if (lo_h > high)
                a[i] = aux[lo++];
            else {
                if (aux[lo] <= aux[lo_h])
                    a[i] = aux[lo++];
                else
                    a[i] = aux[lo_h++];
            }
        }
    }

    /**
     * 快速排序
     * 
     * @param a
     * @return
     */

    public static int[] quickSort(int[] a) {
        a = Arrays.copyOf(a, a.length);
        quickSort(a, 0, a.length - 1);
        return a;
    }

    private static void quickSort(int[] a, int low, int high) {
        if (low >= high)
            return;

        int partition = partition(a, low, high);
        quickSort(a, low, partition - 1);
        quickSort(a, partition + 1, high);
    }

    private static int partition(int[] a, int low, int high) {
        int tempt = a[low];

        while (low < high) {
            while (low < high && a[high] >= tempt)
                high--;
            // swap(a,low,high);
            a[low] = a[high];

            while (low < high && a[low] <= tempt)
                low++;
            // swap(a,low,high);
            a[high] = a[low];
        }
        a[low] = tempt;
        return low;
    }

    private static void print(String str, int[] a) {
        System.out.println(str);
        for (int i = 0; i < a.length; i++)
            System.out.print(a[i] + " ");
        System.out.println("\n");
    }

    /**
     * 下面是鏈表的快速排序
     * 
     * @param str
     * @param a
     */
    public static ListNode quickSort(ListNode begin, ListNode end) {
        // 判斷為空应闯，判斷是不是只有一個節(jié)點
        if (begin == null || end == null || begin == end)
            return begin;
        // 從第一個節(jié)點和第一個節(jié)點的后面一個幾點
        // begin指向的是當(dāng)前遍歷到的最后一個<= nMidValue的節(jié)點
        ListNode first = begin;
        ListNode second = begin.next;

        int nMidValue = begin.val;
        // 結(jié)束條件，second到最后了
        while (second != end.next && second != null) {// 結(jié)束條件
            // 一直往后尋找<=nMidValue的節(jié)點挂捻，然后與fir的后繼節(jié)點交換
            if (second.val < nMidValue) {
                first = first.next;
                // 判斷一下孽锥，避免后面的數(shù)比第一個數(shù)小，不用換的局面
                if (first != second) {
                    int temp = first.val;
                    first.val = second.val;
                    second.val = temp;
                }
            }
            second = second.next;
        }
        // 判斷细层，有些情況是不用換的惜辑，提升性能
        if (begin != first) {
            int temp = begin.val;
            begin.val = first.val;
            first.val = temp;
        }
        // 前部分遞歸
        quickSort(begin, first);
        // 后部分遞歸
        quickSort(first.next, end);
        return begin;
    }

    /**
     * 鏈表的歸并排序
     */
    public ListNode sortList1(ListNode head) {
        if (head == null || head.next == null)
            return head;
        quickSort(null, null);
        return mergeSort(head);
    }

    private ListNode mergeSort(ListNode head) {
        if (head == null || head.next == null)
            return head;

        ListNode mid = getMid(head);
        ListNode second = mid.next;
        mid.next = null;

        ListNode left = mergeSort(head);
        ListNode right = mergeSort(second);
        return merge(right, left);
    }

    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        if (l1 != null)
            cur.next = l1;
        else
            cur.next = l2;

        return dummy.next;

    }

    private ListNode getMid(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode slow = head;
        ListNode faster = head.next;
        while (faster != null && faster.next != null) {
            slow = slow.next;
            faster = faster.next.next;
        }
        return slow;
    }
}

package com.sort_algorithm;

public class ListNode {

    int val;
    ListNode next;

    public ListNode(int x) {
        val = x;
        next = null;
    }
    
}