排序算法是比較基礎(chǔ)，且比較重要的數(shù)據(jù)結(jié)構(gòu)內(nèi)容。今天在這里簡單總結(jié)一下基本原理、代碼和注意事項(xiàng)，讓自己有一個(gè)比較全面的了解，也能方便查看。
本文一共講了選擇排序、冒泡排序、快速排序、歸并排序、插入排序、希爾排序、堆排序、桶排序、基數(shù)排序九種排序算法。

選擇排序

循環(huán)中每次選擇要排序記錄中最小的一個(gè)和最前面的交換。換上n趟，就排好啦~

• 時(shí)間復(fù)雜度：O(n^2)

    public int[] selectSort(int[] input) {

        for (int i = 0; i < input.length; i++) {
            int min = input[i];
            int index = i;
            for (int j = i + 1; j < input.length; j++) {
                if (input[j] < min) {
                    min = input[j];
                    index = j;
                }
            }
            int temp = input[i];
            input[i] = input[index];
            input[index] = temp;
        }
        return input;
    }

冒泡排序

一趟排序中依次比較相鄰的兩個(gè)，如果前面的大于后面的就交換，這樣一趟下來最大的一定會到最后一位。然后運(yùn)行n趟，這整個(gè)為n的記錄就排好序了。

• 時(shí)間復(fù)雜度： O(n^2)

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

快速排序

每一次排序都會把待排序的記錄分成兩部分，其中一部分均比另一部分小，然后再對這兩兩部分分別排序，直到完全有序。

• 具體做法：選擇記錄中第一個(gè)數(shù)字作為關(guān)鍵字，將傳入的左邊界和右邊界作為左右指針，先循環(huán)減少右指針尋找右邊小于關(guān)鍵字的挪到左指針的位置，然后再循環(huán)增加左指針從左邊找大于關(guān)鍵字的挪到右指針位置，直到左指針等于右指針，然后將關(guān)鍵字賦到這個(gè)位置。然后再遞歸調(diào)用這兩部分。直到結(jié)束。
• 時(shí)間復(fù)雜度：O(nlogn)
• 注意：排序算法被認(rèn)為是相同時(shí)間復(fù)雜度里平均性能最好的。如果序列基本有序會退化為冒泡排序，時(shí)間復(fù)雜度為O（n^2）。

    public int[] quickSort(int[] input, int low, int height) {
        if (low >= height) {
            return null;
        }

        int left = low;
        int right = height;
        int key = input[left];
        while (left < right) {
            while (left < right && input[right] >= key) {
                right--;
            }
            input[left] = input[right];
            while (left < right && input[left] <= key) {
                left++;
            }
            input[right] = input[left];
        }
        input[left] = key;

        quickSort(input, low, left - 1);
        quickSort(input, right + 1, height);

        return input;
    }

歸并排序

采用遞歸的方法，將待排序的記錄分成幾個(gè)有序的小部分，然后再進(jìn)行合并。

• 具體做法：遞歸的將記錄分為最小部分，然后再從合并中排序。合并的過程中，先從兩個(gè)的左邊開始比較，如果較小就放到臨時(shí)數(shù)組里，直到有一方空了，再把另一個(gè)數(shù)組的剩余部分全部放進(jìn)臨時(shí)數(shù)組里。然后再把臨時(shí)數(shù)組重新放到原數(shù)組。最后合并為一個(gè)完全有序的記錄。
• 時(shí)間復(fù)雜度：O(nlogn)
• 空間復(fù)雜度：O(n)

    public void mergeSort(int[] input, int low, int height) {
        if (low < height) {
            int mid = (low + height) / 2;
            mergeSort(input, low, mid);
            mergeSort(input, mid + 1, height);
            merge(input, low, height);
        }
    }

    public void merge(int[] input, int left, int right) {
        int[] temp = new int[input.length];
        int mid = (left + right) / 2;
        int index = left;

        int i = left;
        int j = mid + 1;
        while (i <= mid && j <= right) {
            if (input[i] < input[j]) {
                temp[index++] = input[i++];
            } else {
                temp[index++] = input[j++];
            }
        }

        while (i <= mid) {
            temp[index++] = input[i++];
        }
        while (j <= right) {
            temp[index++] = input[j++];
        }

        for (int a = left; a <= right; a++) {
            input[a] = temp[a];
        }
    }

直接插入排序

將一個(gè)記錄插入到已經(jīng)排好序的有序表中，得到一個(gè)新的、記錄數(shù)增一的有序表。

• 形象描述：就像打牌的時(shí)候，我們每抓一張牌都會把這張牌插入到已經(jīng)排好順序的牌里面。
• 具體做法：外層循環(huán)從1到n-1。內(nèi)層循環(huán)查看當(dāng)前數(shù)字是否比前一個(gè)數(shù)字小，如果大的話就跳過，如果小就要循環(huán)已排好序數(shù)列，然后將當(dāng)前數(shù)字插入到合適位置。
• 時(shí)間復(fù)雜度：O(n^2)
• 注意：在基本有序情況下，直接插入算法是最快的排序算法，時(shí)間復(fù)雜度為O（n）

    public int[] straightInsertionSort(int[] input) {
        for (int i = 1; i < input.length; i++) {
            int temp = input[i];
            int j;
            for (j = i - 1; j >= 0 && temp < input[j]; j--) {
                input[j + 1] = input[j];
            }
            input[j + 1] = temp;
        }
        return input;
    }

希爾排序

先將整個(gè)待排序記錄分為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄基本有序時(shí)，再進(jìn)行一次直接插入排序。

• 具體實(shí)現(xiàn)：先選擇插入的距離為length/2完成第一次插入排序，然后再從原來的基礎(chǔ)上/2,最后當(dāng)距離變成1的時(shí)候就變成了直接插入排序。
• 時(shí)間復(fù)雜度：不好說，但肯定比直接插入排序智能點(diǎn)。

    public int[] shellSort(int[] input) {
        int dk = input.length / 2;
        while (dk > 0) {
            for (int i = dk; i < input.length; i++) {
                int temp = input[i];
                int j;
                for (j = i - dk; j >= 0 && temp < input[j]; j -= dk) {
                    input[j + dk] = input[j];
                }
                input[j + dk] = temp;
            }
            dk /= 2;

        }
        return input;
    }

堆排序

先將記錄轉(zhuǎn)化為最大堆或者最小堆，然后不斷地將第一個(gè)數(shù)字拿出來存儲，然后調(diào)整堆，最后堆為空的時(shí)候，排序完成。

• 具體視線：首先生成堆，然后把堆的第一個(gè)元素和最后一個(gè)元素交換，減少堆的長度。然后重新把被破壞了的堆重新調(diào)整成堆。然后再完成交換，直到結(jié)束。
• 時(shí)間復(fù)雜度：O(nlogn)

    public int[] heapSort(int[] input) {
        buildHeap(input);

        for (int i = input.length - 1; i >= 0; i--) {
            int t = input[i];
            input[i] = input[0];
            input[0] = t;

            adjustHeap(input, 0, i);
        }
        return input;
    }

    private void buildHeap(int[] input) {
        for (int i = (input.length - 1) / 2; i >= 0; i--) {
            adjustHeap(input, i, input.length);
        }
    }

    private void adjustHeap(int[] input, int s, int length) {
        int temp = input[s];
        int child = 2 * s + 1;
        while (child < length) {
            if (child + 1 < length && input[child + 1] > input[child]) {
                child++;
            }
            if (input[child] > input[s]) {
                input[s] = input[child];
                input[child] = temp;
                s = child;
                child = 2 * s + 1;
            } else {
                break;
            }
        }
    }

桶排序

新建一個(gè)容量為最大數(shù)字+1個(gè)的數(shù)組空間。然后把每個(gè)數(shù)直接放到該數(shù)組與自己對應(yīng)的地方，然后按次序拿出來就好了。

• 時(shí)間復(fù)雜度：O(n)
• 注意：考慮負(fù)數(shù)和有相同數(shù)字的情況，本程序沒考慮。

    public int[] bucketSort(int[] input, int max) {
        int[] temp = new int[max + 1];
        for (int i = 0; i < input.length; i++) {
            temp[input[i]] = input[i];
        }
        int index = 0;
        for (int i = 0; i < max + 1; i++) {
            if (temp[i] != 0) {
                input[index++] = temp[i];
            }
        }
        return input;
    }

基數(shù)排序

分別以各位數(shù)字進(jìn)行桶排序，然后按順序取出，遍歷完所有位遍完成排序。

• 具體實(shí)現(xiàn)：先建立一個(gè)二維數(shù)組，然后將個(gè)位上相同的數(shù)字放進(jìn)同一個(gè)桶，然后依次取出放回原數(shù)組，這樣就實(shí)現(xiàn)了個(gè)位上的有序，然后百位，千位，最后遍歷完成所有位即完成排序。
• 時(shí)間復(fù)雜度：O(d(n+rd))
• 空間復(fù)雜度：O(rd)
• 注意：要考慮存在負(fù)數(shù)的情況。本程序里沒有考慮。

    public int[] radixSort(int[] input, int max) {
        int[][] temp = new int[10][input.length];
        int[] num = new int[10];

        int index = 1;
        int n = 1;
        while (index <= max) {
            for (int i = 0; i < input.length; i++) {
                int wei = input[i] / n % 10;
                temp[wei][num[wei]++] = input[i];
            }
            int count = 0;
            for (int i = 0; i < 10; i++) {
                for (int j = 0; j < input.length; j++) {
                    if (temp[i][j] == 0) {
                        break;
                    } else {
                        input[count++] = temp[i][j];
                    }
                }
            }
            for (int i = 0; i < 10; i++) {
                num[i] = 0;
                for (int j = 0; j < input.length; j++) {
                    temp[i][j] = 0;
                }
            }

            index++;
            n *= 10;
        }
        return input;
    }

就醬~

歡迎關(guān)注【Funny新青年】微信公眾號～