幾大排序算法

直接插入排序

算法描述

1. 從第一個元素開始，該元素可以認為已經被排序
2. 取出下一個元素，在已經排序的元素序列中從後向前掃描
3. 如果該元素（已排序）大于新元素，将該元素移到下一位置
4. 重複步驟3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到該位置後
6. 重複步驟2~5

算法實作(Java)

/**
 * 直接插入排序
 */
public void insertSort(int[] datas) {
    for (int i = 1; i < datas.length; i++) {
        // 儲存目前周遊到的元素值
        int t = datas[i];
        int j = i - 1;
        // 周遊左邊已經排序好的元素，如果目前元素小于周遊到元素，繼續判斷
        for (; j >= 0 && t < datas[j]; j--)
            datas[j + 1] = datas[j];
        datas[j + 1] = t;
    }
}
           

算法實作(c++)

void insertion_sort(int[] arr, int len)
{
    // 數組中的第一個元素,預設是排序的,是以周遊時隻需從下标為 1 的開始即可
    for (int i = 1; i < len; i++)
    {
        // 儲存目前周遊到的元素值
        int t = arr[i];
        // 擷取到以排序數組的最後一個元素下标
        int j = i - 1;
        // 從後往前掃描,一旦遇到比之前儲存的元素值(t)小或等于的值,終止循環
        for (; j >= 0 && t < arr[j]; j--)
            arr[j + 1] = arr[j];
        // 由于上面 for 循環停止時,下标剛好處于不滿足的最後一個元素的位置,此時需要将目前下标後一位指派為目标值(t)
        arr[j + 1] = t;
    }
}
           

二分查找插入排序(直接插入排序的改進版本)

算法描述

基本思路跟直接插入排序的算法是一樣的,不一樣的是在于查找需要插入的位置時,采取的方法不一樣,二分插入排序,采取的方法時通過二分法找到需要插入的位置.

算法實作(Java)

public void insertBinarySort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        // 取出目前周遊到的值
        int temp = arr[i];
        int begin = 0, end = i - 1, mid = (begin + end) / 2;
        while (begin < end) {
            // 比較 temp 和 arr[mid] 的關系
            if (temp < arr[mid])
                end--;
            else if (temp > arr[mid])
                begin++;
            // 如果這個條件滿足的,說明 mid 就是找到的位置,此時需要将 mid 後的元素全部後移一位,将目前 temp 值插入到 mid 後一位
            else
                break;
            mid = (begin + end) / 2;
        }
        // 元素需要插入的位置是 mid + 1,是以需要将 mid + 2 --> j 的元素全部後移一位
        for (int j = i; j > mid + 1; j--)
            arr[j] = arr[j - 1];
        arr[mid + 1] = temp;
    }

}
           

希爾排序

算法描述

1. 将一個資料序列分成若幹組,每組由若幹相鄰一段距離(稱為增量)的元素組成,在一個組内采用直接插入排序算法進行排序
2. 增量初值通常為資料長度的一半,然後每趟增量減半,最後值為1,

代碼實作(Java)

public void shellSort(int[] arr) {
    for (int len = arr.length / 2; i > 0; len /= 2) {
        for (int i = len; i < arr.length; i += len) {
            int j = i - len;
            int temp = arr[i];
            // 結束判斷時,temp 與 是大于等于目前周遊到的元素
            // 是以 arr[j + 1] = temp
            for (; j > 0 && temp < arr[j]; j -= len)
                arr[j + len] = arr[j];
            arr[j + len] = temp;
        }
    }
}
           

冒泡排序

算法描述

比較相鄰兩個元素大小,如果反序,則交換.若按升序排序,每趟将資料序列中的最大元素交換到最後位置.

算法實作(Java)

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

快速排序

算法描述

算法實作(Java)

public void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
}

public void quickSort(int[] arr, int begin, int end) {
    if (begin >= 0 && begin < arr.length && end >= 0 && end < arr.length && begin < end) {
        int i = begin, j = end;
        // 擷取數組中的一個元素值
        int vot = arr[0];
        while (i != j) {
            while (i < j && arr[j] > vot)
                j--;
            if (i < j)
                arr[i++] = arr[j];
            while (i < j && arr[i] < vot)
                i++;
            if (i < j)
                arr[j--] = arr[i];
        }
        arr[i] = vot;
        quickSort(arr, begin, i - 1);
        qucikSort(arr, i + 1, end);
    }
}
           

選擇排序

算法描述

算法實作(Java)

/**
 * 每次将指定序列中的最小值找出來
 */
public void selectSort(int[] arr) {
    // arr.length - 1 趟周遊
    for (int i = 0; i < arr.length - 1; i++) {
        // 存儲最小值的下标
        int min = i;
        // 從 i + 1 到數組最後一個元素,找到最小的元素值,存儲下标
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < min)
                min = j;
        }
        // 如果最小值不是目前 i 所在的值,交換最小值和目前 i 位置的值
        if (min != i) {
            int temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        }
    }
}
           

堆排序

算法描述

算法實作(Java)

/**
 * 預設的是升序
 */ 
public void heapSort(int[] arr) {
    // 建立一個二叉堆
    heapSort(arr, true);
}

public void heapSort(int[] arr, boolean minheap) {
    // 建立一個最小/大堆
    for (int i = arr.length / 2 - 1; i >= 0; i--)
        sift(arr, 0, i, minheap);
    // 周遊二叉堆,每次将堆頂取出,置于數組最後,然後從新恢複二叉堆
    for (int i = arr.length - 1; i > 0; i--) {
        int temp = arr[i];
        arr[i] = arr[0];
        arr[0] = temp;

        sift(arr, 0, i - 1, minheap);
    }
}

/**
 * 恢複二叉堆的性質
 */ 
public void sift(int[] arr, int parent, int end, boolean minheap) {
    // 擷取父節點的左孩子結點
    int child = parent * 2 + 1;
    // 儲存父節點的值
    int value = arr[parent];
    // 由于 end 始終是在數組内
    while (child <= end) {
        // 目的是取出兩個孩子的最小/大值
        if (child < end && (minheap ? arr[child] < arr[child + 1] : arr[child] > arr[child + 1]))
            child++;
        if (minheap ? arr[child] < value : arr[child] > value) {
            arr[parent] = child;
            parent = child;
            child = parent * 2 + 1;
        } else
            break;
    }
    // 循環條件結束的情況下,child 是越界了,是以 arr[parent] = value
    // 如果是 break 跳出循環,說明孩子都比樹大/小,滿足最大堆最小堆的情況
    // 此時假設 if 沒有成功過, int value = arr[parent] arr[parent] = value; 剛好是逆過程
    arr[parent] = value;
}

           

歸并排序

算法描述

算法實作(Java)

public void mergeSort(int[] arr) {
  
// 建立一個新的數組對象,長度跟 arr.length 一樣
    int[] temp = new int[arr.length];
    // 每次有序的單元長度
    int n = 1;
    while (n < arr.length) {
        // 将 arr 數組中的元素,按照單元長度 n 複制到 temp 數組中
        mergepass(arr, temp, n);
        n *= 2;
        if (n < arr.length) {
            // 将 temp 數組中的元素,按照單元長度 n 指派到 arr 數組中
            mergepass(temp, pass, n);
            n *= 2;
        }
    }
}

/**
 * 一趟對并
 */
public void mergepass(int[] x, int[] y, int n) {
    // 每次後移 2 * n, 4
    for (int i = 0; i < x.length; i += 2 * n)
        merge(x, y, i, i + n, n);
}

public void merge(int[] x, int[] y, int begin1, int begin2, int n) {
    int i = begin1, begin2, k = begin1;
    while (i < begin1 + n && j < begin2 + n && j < x.length) {
        y[k++] = x[i] < x[j] ? x[i++] : x[j++];
        for (; i < begin1 + n && i < x.length; y[k++] = x[i++]);
        for (; j < begin2 + n && j < x.length; y[k++] = x[j++]);
    }
}