資料結構與算法之排序

排序算法：

内部排序：指将需要處理的所有的資料都加載到内部存儲器中進行排序
外部排序：當資料量過大，無法全部加載到記憶體中，需要借助外部存儲器進行排序
常見的算法分類：

5.1 冒泡排序

基本思想：通過對待排序從前往後（從下标小的元素開始），依次比較相鄰的元素的值，如是發現逆序則交換，使值較大的元素逐漸從前移向後部，像水底的起跑一樣。

總結規則：

一共進行n-1次大循環（數組中有n個元素）
每一次排序的元素在逐漸的減少
如果在某次排序的過程中，沒有發生一次交換，說明排序已經完成了

public static int[] bubbleSort(int[] arr) {
        int temp = 0;
        boolean flag = false;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if(arr[j] > arr[j+1]){
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }

            if(!flag){
                break;
            }else {
                flag = false;
            }
        }
        return arr;
    }

5.2 選擇排序

選擇排序也是屬于内部排序，是從要排序的資料中按照指定的規則挑選出某一進制素，再依照規則交換位置達到排序的目的。

選擇排序的思想：

從arr[0]--arr[n-1]中找到最小的數值，然後交換arr[0]和最小值交換位置
從arr[1]--arr[n-1]中找到最小的數值，然後交換arr[1]和最小值交換位置
........
直到所有的資料進行交換完成

// 選擇排序，選擇數組中的最小的元素與arr[0]進行交換，然後繼續在剩下的位置尋找次最小值與arr[1]交換，直到将所有的資料排序完成
public static int[] selectSort(int[] arr){
        int temp = 0;
        int index = 0;
        for (int i = 0; i < arr.length-1; i++) {
            index = i;	// 初始最小值的索引為i
            for (int j = i+1; j < arr.length; j++) {
                 //如果arr[j]小于arr[index]，則j為最小值的索引
                if(arr[j] < arr[index]){	
                    index = j;
                }
            }
            // 交換最小值和arr[i]的位置
            temp = arr[i];
            arr[i] = arr[index];
            arr[index] = temp;
        }

        return arr;
    }

5.3 插入排序

插入排序屬于内部排序法，是對于欲排序的元素以插入的方式尋找該元素的适當位置。

插入排序的思想：把n個待排序的元素看做是一個有序表和無序表，開始時有序表中隻含有一個元素，無序表中包含n-1個元素。排序的過程中，每次從無序表中取出第一個元素，把它插入到有序表中的适當位置，使之形成新的有序表。

代碼的實作：

/**
     * 插入排序，将清單看做一個有序表和一個無序表
     * @param arr
     * @return
     */
public static int[] insertSort(int[] arr){
    int temp = 0;
    int index = 0;
    for (int i = 1; i < arr.length; i++) {
        temp = arr[i];
        index = i-1;
        // 倒叙判斷從i-1到0進行判斷，如果出現temp>arr[index]，則說明arr[index+1]則為要插入的部分
        while (index >= 0  && temp < arr[index]){
            arr[index+1] = arr[index];	//依次移動資料
            index --;
        }
        // 在arr[index+1]中插入資料
        arr[index+1] = temp;
    }

    return arr;
}

5.4 希爾排序（縮小增量排序）

基本思想：希爾排序是把記錄按下标的一定增量分組，對每組使用直接插入排序算法排序；随着增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個檔案恰被分成一組，算法便終止。

安照一定的步長，将一定數量的資料分為一組。設定每組的資料增量為上一次增量的一半，然後将每組的資料量增加，數組減少，直到隻剩下一個數組為止。

希爾排序方法：

對有序序列插入時采用交換法
對有序序列插入時采用移動法

/**
     * 希爾交換法
     * @param arr
     * @return
     */
    public static int[] shellSort(int[] arr){
        int temp = 0;
        int count = 0;
        for(int gap = arr.length/2; gap > 0; gap /= 2){
            for(int i=gap; i< arr.length; i++){
                // 周遊組中的所有資料，gap為步長
                for(int j=i-gap; j >= 0; j -= gap){
                    if(arr[j] > arr[j+gap]){
                        temp = arr[j];
                        arr[j] = arr[j+gap];
                        arr[j+gap] = temp;
                    }
                }
            }
        }

        return arr;
    }

// 移動位置（結合插入排序）
    public static int[] shellMoveSort(int[] arr){
        for(int gap = arr.length/2; gap > 0; gap /= 2){
            for(int i=gap; i < arr.length; i++){
                int j = i;
                int temp = arr[j];
                if(arr[j] < arr[j-gap]){
                    while (j - gap >= 0 && temp < arr[j - gap]){
                        arr[j] = arr[j-gap];
                        j -= gap;
                    }

                    arr[j] = temp;
                }
            }
        }
        return arr;
    }

5.5 快速排序

基本思想：通過一次排序将要排序的資料分割成獨立的兩個部分，其中一部分的所有資料都比另一部分的所有資料都要小，然後按照這種方法對這兩個部分資料分布進行快速排序，整個排序部分可以使用遞歸進行，以此達到整個資料變成有序序列。

思路分析：

假設數組為arr，左側為left，右側為right，設定選擇的初始位置為
從左側開始查找，找到大于等于mid的值為止，從右側也開始查找，直到找到小于等于mid的值
直到找到 l<r 的位置，然後遞歸進行快速排序。

/**
     * 快速排序
     *
     * @param arr
     * @param left
     * @param right
     * @return
     */
public static int[] quickSort(int[] arr, int left, int right) {
    if (left >= right) return null;
    // 如果數組中left與right相等或者left大于right，則跳出程式
    int l = left;
    int r = right;
    int mid = arr[(l + r) / 2];
    int temp = 0;
    while (l < r) {
        while (l < r && arr[l] < mid) {
            l++;
        }

        while (r > l && arr[r] > mid) {
            r--;
        }

        if (l >= r) {
            break;
        }

        temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;

        if (arr[l] == mid){
            r--;
        }
        if (arr[r] == mid) {
            l++;
        }
    }

    quickSort(arr, left, l - 1);
    quickSort(arr, r + 1, right);
    return arr;
}

5.6 歸并排序

歸并排序是利用歸并的思想實作的排序方法，該算法采用經典的分治政策（分治法将問題分為一些小的問題然後遞歸求解，而治階段則将分的階段得到的各答案“修補”在一起，即分而治之）

基本方法：

首先将數組成分成兩個部分，一直拆分直到拆分到每個子數組中隻有一個元素
然後進行合并相同相鄰的拆分部分，按照順序進行合并，直到合并成完整的數組
使用遞歸方法完成最好，時間複雜度為 O(nlogn)

/**
     * 歸并排序
     * @param arr
     * @param left
     * @param right
     * @return
     */
public static int[] mergeSort(int[] arr, int left, int right){
    // 如果left大于right，說明數組中隻有1個或者沒有資料，則将直接傳回空
    if(left >= right) return null;
    int mid = (left + right)/2;

    // 分割
    mergeSort(arr, left, mid);
    mergeSort(arr, mid+1, right);

    int i = left;
    int j = mid+1;
    int t = 0;
    int[] temp = new int[(right - left + 1)];
    while (i <= mid && j <= right){
        if(arr[i] <= arr[j]){
            temp[t] = arr[i];
            t ++;
            i ++;
        }else {
            temp[t] = arr[j];
            t ++;
            j ++;
        }
    }
    // 将剩餘的内容填充到temp中
    while (i <= mid){
        temp[t] = arr[i];
        t++;
        i++;
    }
    // 将剩餘的right内容填充到temp中
    while (j <= right){
        temp[t] = arr[j];
        t++;
        j++;
    }

    // 将temp資料拷貝到arr中
    for(int k=left; k<=right; k++){
        arr[k] = temp[k-left];
    }
    System.out.println("排序後的資料為：" + Arrays.toString(temp));
    return arr;
}

5.7 基數排序

基數排序屬于“配置設定式排序”，又稱桶子法，它是通過鍵值的各個位的值，将要排序的元素配置設定到某些“桶”中，達到排序的作用
基數排序屬于穩定性的排序，基數排序法的是效率高的穩定性排序法
基數排序是桶排序的拓展
基數排序的實作方法：将整數位按照位數切割成不同的數字，然後按照每個位分别比較。

實作的方法：

定義一個二維數組，表示10個桶，每一個桶就是一個一維數組
為了防止在放入輸的時候資料溢出，則每個一維數組（桶），大小定為arr.length
基數排序就是使用空間換時間的經典算法。

/**
     * 基數排序
     * @param arr
     * @return
     */
public static int[] radixSort(int[] arr){
    int[][] bubble = new int[10][arr.length];   //設定桶的數量，每個桶最多盛放整個數組
	// 尋找數組中最大的數
    int max = arr[0];
    for(int i=1; i<arr.length; i++){
        if(arr[i] > max){
            max = arr[i];
        }
    }

    int maxLength = (max + "").length();
    // 根據數值中最大資料的位數判定需要多少次循環
    for (int i = 0; i < maxLength; i++) {
        int[] bubbleLength = new int[10];   // 桶的放的資料的量
        // 将資料根據個位、十位、百位依次放入桶中
        for (int j = 0; j < arr.length; j++) {
            int size = arr[j] / (int)Math.pow(10, i) % 10;
            bubble[size][bubbleLength[size]] = arr[j];
            bubbleLength[size] ++;
        }

        //依次将資料取出，并放入到原來的數組中
        int index = 0;
        for(int j=0; j<bubble.length; j++){
            if(bubbleLength[j] > 0){
                for(int k=0; k<bubbleLength[j]; k++){
                    arr[index++] = bubble[j][k];
                }
            }
        }
    }

    return arr;
}

資料結構與算法之排序

5.1 冒泡排序

5.2 選擇排序

5.3 插入排序

5.4 希爾排序（縮小增量排序）

5.5 快速排序

5.6 歸并排序

5.7 基數排序

繼續閱讀

Codeforces 1417 D. Make Them Equal(思維+構造)

查找算法之二分查找查找算法之二分查找

查找算法學習之二分查找（Python版本）——BinarySearch

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

hdu7108哈希

資料結構與算法之排序

5.1 冒泡排序

5.2 選擇排序

5.3 插入排序

5.4 希爾排序（ 縮小增量排序 ）

5.5 快速排序

5.6 歸并排序

5.7 基數排序

繼續閱讀

5.4 希爾排序（縮小增量排序）