冒泡排序

• 原理
  基于比較的排序算法,每次都從下標(biāo)為0的位置開(kāi)始,依次比較相鄰的兩個(gè)元素(下標(biāo)為i和下標(biāo)為i+1的),如果下標(biāo)為i的元素大于下標(biāo)為i+1的元素,則交換兩個(gè)元素,以此類推,每次循環(huán)比較,都會(huì)把一個(gè)元素交換到該放的位置.
• 最好時(shí)間復(fù)雜度:O(N)
• 最壞時(shí)間復(fù)雜度:O(N^2)
• 空間復(fù)雜度:O(1)
• 是穩(wěn)定排序算法

 public static void bubbleSort(int[] a) {
        boolean swap = false;
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a.length - i - 1; j++) {
                if (a[j] > a[j + 1]) {
                    swap = true;
                    int t = a[j + 1];
                    a[j + 1] = a[j];
                    a[j] = t;
                }
            }
            if (!swap) break;
        }
    }

插入排序法

• 原理
  將待排序的數(shù)組分為前后兩部分:前半部分為已排序數(shù)組,后半部分是未排序數(shù)組,每次在處理未排序數(shù)組的第一個(gè)元素時(shí)都從已排序數(shù)組中找到該元素應(yīng)該插入的位置,查找的方法就是依次向后移動(dòng)比該元素大的元素.

• 時(shí)間復(fù)雜度:O(n^2)
• 空間復(fù)雜度:插入排序算法是本地排序,空間復(fù)雜度為O(1)
• 插入排序是穩(wěn)定排序

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

選擇排序法

• 原理
  和插入排序法同樣將數(shù)組分為待排序和已排序兩部分,在每次排序時(shí),都選擇待排序數(shù)組中最小的元素與此元素交換位置.

• 選擇排序法時(shí)間復(fù)雜度:O(N^2)
• 選擇排序法的空間復(fù)雜度:O(1)
• 選擇排序不是穩(wěn)定排序算法.

 public static void selectionSort(int[] a) {
        for (int i = 0; i < a.length; i++) {
            int minValueIndex = i;
            int minV = a[i];
            for (int j = i; j < a.length; j++) {

                if (a[j] < minV) {
                    minValueIndex = j;
                    minV = a[j];
                }
            }
            int t = a[i];
            a[i] = a[minValueIndex];
            a[minValueIndex] = t;
        }
    }

歸并排序算法

• 原理
  歸并排序的原理是把一個(gè)數(shù)組拆成兩個(gè)子數(shù)組,并且這兩個(gè)子數(shù)組分別有序的情況下,只需要將這兩個(gè)有序的子數(shù)組歸并為一個(gè)有序的數(shù)組即可.歸并排序使用遞歸的方式實(shí)現(xiàn).
• 遞推公式：

mergeSort(a,0,r) = merge(mergeSort(a,0,q), mergeSort(a,q+1,r))
終止條件：
p >= r 不用再繼續(xù)分解

• 歸并排序的時(shí)間復(fù)雜度 O(N*log(N))
• 歸并排序的空間復(fù)雜度O(N)

public static void mergeSort(int[] a, int startIndex, int endIndex) {
        if (startIndex >= endIndex) {
            return;
        }
        int mid = (startIndex + endIndex) / 2;

        mergeSort(a, startIndex, mid);
        mergeSort(a, mid + 1, endIndex);
        merge(a, startIndex, mid, endIndex);
   }
    private static void merge(int[] a, int startIndex, int mid, int endIndex) {
        int i = startIndex, j = mid + 1;
        if (i >= j) {
            return;
        }
        int[] tmp = new int[endIndex - startIndex + 1];
        int k = 0;
        while (i <= mid && j <= endIndex) {

            if (a[i] <= a[j]) {
                tmp[k++] = a[i++];
            } else {
                tmp[k++] = a[j++];
            }
        }

        if (i <= mid || j <= endIndex) {
            int start = i <= mid ? i : j;
            int end = i <= mid ? mid : endIndex;
            for (; start <= end; start++) {
                tmp[k++] = a[start];
            }

        }
        for (int m = 0; m < tmp.length; m++) {
            a[m + startIndex] = tmp[m];
        }
    }

快排

• 原理
  快排的思想是如果要排序數(shù)組a中從下標(biāo)p到下標(biāo)r的數(shù)據(jù)， 從p到q之間選擇任意一個(gè)點(diǎn)作為分界點(diǎn)（pivot），我們遍歷p到r之間的數(shù)據(jù)，把小于pivot的點(diǎn)放在左邊，把大于pivot的點(diǎn)放在右邊，將pivot放在中間。經(jīng)過(guò)這個(gè)步驟之后，我們就把數(shù)據(jù)分成三部分，小于pivot的、等于pivot的和大于pivot的。我們認(rèn)為pivot的下標(biāo)為q。
  根據(jù)遞歸分治的思想，用遞歸處理下標(biāo)p到q-1、和q到r之間的數(shù)據(jù)，直到區(qū)間大小縮小為1，說(shuō)明整個(gè)數(shù)組就是有序的了。
• 時(shí)間復(fù)雜度：O(N*log(N))
• 空間復(fù)雜度：快排是原地排序，空間復(fù)雜度為O(1)

public static void quickSort(int[] a, int p, int r) {

        if (p >= r) {
            return;
        }
        int q = partition(a, p, r);
        quickSort(a, p, q - 1);
        quickSort(a, q + 1, r);
    }

    private static int partition(int[] a, int p, int r) {

        int pivot = a[r];
        int i = p;
        int j = p;
        for (; j < r; j++) {
            if (a[j] > pivot) {
                int tmp = a[j];
                a[j] = a[i];
                a[i] = tmp;
                i++;
            }
        }
        int tmp = a[i];
        a[i] = a[r];
        a[r] = tmp;
        return i;
    }

堆排序

堆有以下兩個(gè)特性：

• 堆，首先是棵完全二叉樹(shù)，所以對(duì)適合使用數(shù)組存儲(chǔ)
• 堆中的節(jié)點(diǎn)都大于等于該節(jié)點(diǎn)下所有子節(jié)點(diǎn)
• 當(dāng)堆的頂點(diǎn)大于堆中所有子樹(shù)的節(jié)點(diǎn)時(shí)，這個(gè)堆是大頂堆
• 當(dāng)堆得頂點(diǎn)小于堆中所有子樹(shù)的節(jié)點(diǎn)時(shí)，這個(gè)堆是小頂堆

使用堆排序有兩個(gè)過(guò)程，建堆+排序

• 建堆的過(guò)程是兩種：
  • 從數(shù)組下標(biāo)0開(kāi)始為初始堆，依次向堆中添加元素，不斷堆化，最后所有的元素都加到堆里
  • 如代碼buildHeap

• 堆排序，建堆之后的結(jié)構(gòu)是個(gè)大頂堆，數(shù)組中的第一個(gè)元素就是堆頂?shù)脑?，也就是最大的，把它和下?biāo)為n的元素對(duì)換，那么就把最大的元素放到下標(biāo)為n的位置了，把原來(lái)下標(biāo)為n的元素放到堆頂。這就是相當(dāng)于刪除了堆頂元素，然后再把剩余的n-1個(gè)元素進(jìn)行堆化，建堆之后，再把堆頂?shù)脑胤诺较聵?biāo)為n-1的位置，以此類推重復(fù)這個(gè)過(guò)程，直到堆中只有一個(gè)元素時(shí)，那么堆排序就完成了。

public class Heap {
    private int[] a; // 數(shù)組，從下標(biāo) 1 開(kāi)始存儲(chǔ)數(shù)據(jù)
    private int n;  // 堆可以存儲(chǔ)的最大數(shù)據(jù)個(gè)數(shù)
    private int count; // 堆中已經(jīng)存儲(chǔ)的數(shù)據(jù)個(gè)數(shù)
 public Heap(int capacity) {
        a = new int[capacity + 1];
        n = capacity;
        count = 0;
    }

 private void buildHeap(int[] a, int n) {
        for (int i = n / 2; i >= 1; --i) {
            heapify(a, n, i);
        }
    }
 private void heapify(int[] a, int n, int i) { // 自上往下堆化
        while (true) {
            int maxPos = i;
            if (i * 2 <= n && a[i] < a[i * 2]) maxPos = i * 2;
            if (i * 2 + 1 <= n && a[maxPos] < a[i * 2 + 1]) maxPos = i * 2 + 1;
            if (maxPos == i) break;
            swap(a, i, maxPos);
            i = maxPos;
        }
    }

    private void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    // n 表示數(shù)據(jù)的個(gè)數(shù)，數(shù)組 a 中的數(shù)據(jù)從下標(biāo) 1 到 n 的位置。
    public void sort(int[] a, int n) {
        buildHeap(a, n);
        int k = n;
        while (k > 1) {
            swap(a, 1, k);
            --k;
            heapify(a, k, 1);
        }
    }