學習資料結構的重要性

程式＝資料結構 + 演算法，演算法很重要，資料結構也很重要，只有掌握了這兩者，我們才等于掌握了寫程式的本領，才是合格的程式員哦，

演算法復雜度比較

在網上看到的一篇總結，這個要背的，

資料結構重點：排序演算法比較

這是我學資料結構的時候做的一個總結：

為什么要綜合比較

見下圖，這是一道排序演算法的面試題（要求：穩定，快速），我在做這道題的時候，根據我總結的內容，很快便鎖定了演算法，首先，演算法要求一個穩定，快速的演算法，我們便可以確定要從基數排序和二路歸并排序中做選擇，我選擇了基數排序，并快速回憶了快速排序的例子，于是便很快的做出來了這道題，

插入排序

基本思想：

插入排序思想類似于撲克牌手牌整理
原陣列為待起的未排序的手牌
起第一張牌不用整理，從起的第二張開始
和手牌里的牌進行比較，插入到手牌里

實作：

public static int[] insertSort(int[] sourceArray) {
    int s;
    int temp;
    for (int i = 1; i < sourceArray.length; i++) {
        temp = sourceArray[i];
        s = i;
        while (s > 0 && temp < sourceArray[s - 1]) {
            sourceArray[s] = sourceArray[s - 1];
            s = s - 1;
        }
        sourceArray[s] = temp;
    }
    return sourceArray;
}

交換排序

冒泡排序

基本思想：

從左到右執行n次：比較相鄰元素大小，誰大把誰放在右邊

實作：

private static int[] bubbleSort(int[] sourceArray) {
    for (int i = 0; i < sourceArray.length; i++) {
        for (int j = 0; j < sourceArray.length - 1; j++) {
            sortMaxAndPutItRight(sourceArray, j, j+1);
        }
    }
    return sourceArray;
}

private static void sortMaxAndPutItRight(int[] sourceArray, int left, int right) {
    if (sourceArray[left] > sourceArray[right]) {
        int temp = sourceArray[right];
        sourceArray[right] = sourceArray[left];
        sourceArray[left] = temp;
    }
}

快速排序

基本思想：

從左到右執行n次：
選基準元素（例如第一個元素），
左右兩邊往中間走，左邊走的找到比他大的，右邊走的找到比他小的
每次找到交換他們的順序，直到左右走到一起
走到一起之后，選個元素和基準元素交換
——
然后在這個位置左邊重復上述程序，右邊也是

實作：

public static int[] quickSort(int[] sourceArray, int start, int end) {
    if (start < end) {
        int index = sortAndFindIndex(sourceArray, start, end);
        quickSort(sourceArray, start, index - 1);
        quickSort(sourceArray, index + 1, end);
    }
    return sourceArray;
}
private static int sortAndFindIndex(int[] sourceArray, int start, int end) {
    int temp = sourceArray[start];
    while (start < end) {
        while ((sourceArray[end] >= temp) && (start < end)) {
            end --;
        }
        sourceArray[start] = sourceArray[end];
        while ((sourceArray[start] <= temp) && (start < end)) {
            start ++;
        }
        sourceArray[end] = sourceArray[start];
    }
    sourceArray[start] = temp;
    return start;
}

選擇排序

簡單選擇排序

基本思想：

選擇排序類似于撲克牌手牌里的出牌階段
選擇手牌里最小的牌打出去
打完之后，發現出的牌是有順序的

實作：

public static int[] selectionSort(int[] sourceArray) {
    for (int i = 0; i < sourceArray.length - 1; i++) {
        int min = i;
        for (int j = i + 1; j < sourceArray.length; j++) {
            min = sourceArray[j] < sourceArray[min] ? j : min;
        }
        swap(sourceArray, i, min);
    }
    return sourceArray;
}

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

堆排序

基本思想：待寫
實作：待寫

基數排序

基本思想

設最后一位設第一位（例如352的2），倒數第二位是第二位
將數字按照第一位進行排序
將數字按照第二位進行排序
數字相同的保持位置不變

實作

public static int getNumInPos(int num, int pos) {
    int tmp = 1;
    for (int i = 0; i < pos - 1; i++) {
        tmp *= 10;
    }
    return (num / tmp) % 10;
}
    
public static int getMaxDigit(int[] a) {
    int max = a[0];
    for (int i = 0; i < a.length; i++) {
        if (a[i] > max) {
            max = a[i];
        }
    }
   int tmp = 1, d = 1;
   while (true) {
        tmp *= 10;
        if (max / tmp != 0) {
            d++;
        } else {
            break;
        }
    }
    return d;
}

public static void radixSort(int[] a, int d) {
    int[][] array = new int[10][a.length + 1];
    for (int i = 0; i < 10; i++) {
        array[i][0] = 0;
    }
    for (int pos = 1; pos <= d; pos++) {
        for (int i = 0; i < a.length; i++) { 
            int row = getNumInPos(a[i], pos);
            int col = ++array[row][0];
            array[row][col] = a[i];
        }
        for (int row = 0, i = 0; row < 10; row++) { 
            for (int col = 1; col <= array[row][0]; col++) {
                a[i++] = array[row][col];
            }
            array[row][0] = 0; 
        }
    }
}

計數排序

基本思想

找到陣列最大值l，創建一個長度為l的新陣列
將原陣列的值作為新陣列的下標，有幾個，下標對應的數就是幾
將新陣列從左到右遍歷，賦值給原陣列

實作

private static int[] countSort(int[] array) {
    int maxVal = Arrays.stream(array).max().getAsInt();
    int[] sortList = new int[maxVal + 1];
    for (int i : array) {
        sortList[i]++;
    }
    int sortedIndex = 0;
    for (int i = 0; i < (maxVal + 1); i++) {
        while (sortList[i] > 0) {
            array[sortedIndex++] = i;
            sortList[i]--;
        }
    }
    return array;
}

歸并排序

二路歸并排序

基本思想：待寫
實作：待寫

推薦書籍

《資料結構教程(第三版)》