一裙顽、插入排序

插入排序（Insertion sort）是一種簡(jiǎn)單直觀且穩(wěn)定的排序算法亭珍。

Image-插入排序.png

算法思維

每次將一個(gè)待排序的記錄敷钾，按其關(guān)鍵字大小插入到前面的已經(jīng)排好的子表中的適當(dāng)?shù)奈恢谩Ｖ钡饺坑涗洸迦胪瓿蔀橹埂?/p>

算法性能

• 時(shí)間復(fù)雜度為 O(n^2)肄梨。

類型

插入排序主要包括：直接插入排序阻荒，二分插入排序（又稱折半插入排序），鏈表插入排序众羡，希爾排序（又稱縮小增量排序）侨赡。

• 直接插入排序：

【解釋】：直接插入排序是一種簡(jiǎn)單的插入排序法，其基本思想是：把待排序的記錄按其關(guān)鍵碼值的大小逐個(gè)插入到一個(gè)已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止羊壹，得到一個(gè)新的有序序列蓖宦。

直接插入排序的算法思路：
（1） 設(shè)置監(jiān)視哨r[0]，將待插入記錄的值賦值給r[0]油猫；
（2） 設(shè)置開(kāi)始查找的位置j稠茂；
（3） 在數(shù)組中進(jìn)行搜索，搜索中將第j個(gè)記錄后移情妖，直至r[0].key≥r[j].key為止主慰；
（4） 將r[0]插入r[j+1]的位置上。

• 折半插入排序

【解釋】：將直接插入排序中尋找A[i]的插入位置的方法改為采用折半比較鲫售，即可得到折半插入排序算法共螺。

算法的基本過(guò)程(思路)：

（1）計(jì)算 0 ~ i-1 的中間點(diǎn)，用 i 索引處的元素與中間值進(jìn)行比較情竹，如果 i 索引處的元素大藐不，說(shuō)明要插入的這個(gè)元素應(yīng)該在中間值和剛加入i索引之間，反之秦效，就是在剛開(kāi)始的位置 到中間值的位置雏蛮，這樣很簡(jiǎn)單的完成了折半；

（2）在相應(yīng)的半個(gè)范圍里面找插入的位置時(shí)阱州，不斷的用（1）步驟縮小范圍挑秉，不停的折半，范圍依次縮小為 1/2 1/4 1/8 .......快速的確定出第 i 個(gè)元素要插在什么地方苔货；

（3）確定位置之后犀概，將整個(gè)序列后移，并將元素插入到相應(yīng)位置夜惭。

• 希爾排序法

希爾排序法的基本思想是：先選定一個(gè)整數(shù)姻灶，把待排序文件中所有記錄分成個(gè)組，所有距離為的記錄分在同一組內(nèi)诈茧，并對(duì)每一組內(nèi)的記錄進(jìn)行排序产喉。

各組內(nèi)的排序通常采用直接插入法。
由于開(kāi)始時(shí)s的取值較大敢会，每組內(nèi)記錄數(shù)較少曾沈，所以排序比較快。隨著不斷增大鸥昏，每組內(nèi)的記錄數(shù)逐步增多塞俱，但由于已經(jīng)按排好序，因此排序速度也比較快互广。

【Java_Code】語(yǔ)言解法如下：

import java.util.Scanner;

public class InsertionSort{
    public static void main(String[] array){
        int[] array_one = {23,34,567,78,56,423,99,11};
        int[] array_two = insertionSort(array_one);
        int[] array_three = insertionSort_2(array_one);

        printNumbers(array_two);
        printNumbers(array_three);

        // 技能點(diǎn)提升:給自定義的數(shù)組【插入排序】敛腌；
        System.out.println("請(qǐng)輸入您要排序的數(shù)組：" +'\n');
        Scanner sc = new Scanner(System.in);
        String inputString = sc.nextLine();
        String stringArray[] = inputString.split(",");
        // 數(shù)組類型轉(zhuǎn)換；
        int num[] = new int[stringArray.length];
        for (int i = 0; i < stringArray.length; i++) {
              num[i] = Integer.parseInt(stringArray[i]);
        }
        int[] array_four = insertionSort_2(num);
        printNumbers(array_four);

    }
    private static void printNumbers(int[] input) {
        System.out.println("正在排序中..." +'\n');
        for (int i = 0; i < input.length; i++) {
            System.out.print(input[i] + ", ");
        }
        System.out.println("\n");
    }
    public static int[] insertionSort(int[] array){
        for (int i = 1;i < array.length; i++){
            for(int j = i; j > 0;j--){
                if(array[j] < array[j-1]){
                    int temp = array[j];
                    array[j] = array[j-1];
                    array[j-1] = temp;
                }
            }
        }
        return array;
    }
    // 【算法改進(jìn)】： 因?yàn)閕nsertionSort中每一次位置置換的時(shí)候需要定義一個(gè)temp惫皱，這這多浪費(fèi)內(nèi)存跋穹！
    //所以我的解決思路是旅敷，將所有要后移的元素全部都存在一個(gè)新開(kāi)辟的內(nèi)存空間中生棍，然后再進(jìn)行比較重排序。只定義了一個(gè)temp
    public static int[] insertionSort_2(int[] array){
        for(int i = 1;i < array.length;i++){
            int temp = array[i];
            int k;
            for (k = i;k > 0 && array[k-1] > temp;k--){
                array[k] = array[k-1];
            }
            array[k] = temp;
        }
        return array;
    }

}

Image-插入排序.png

【Python_Code】如下媳谁，寥寥幾行就實(shí)現(xiàn)了涂滴。

import random
Range = 100
Length = 5
list = random.sample(range(Range),Length)    #在指定序列中隨機(jī)獲取指定長(zhǎng)度片段
print('before sort:',list)
for i in range(1,Length):                   #默認(rèn)第一個(gè)元素已經(jīng)在有序序列中，從后面元素開(kāi)始插入    
    for j in range(i,0,-1):                 #逆向遍歷比較晴音，交換位置實(shí)現(xiàn)插入        
        if list[j] < list[j-1]:            
            list[j],list[j-1] = list[j-1],list[j]
print('after sort:',list)

二柔纵、快速排序

算法思想：基于分治的思想，是冒泡排序的改進(jìn)型锤躁。

首先在數(shù)組中選擇一個(gè)基準(zhǔn)點(diǎn)搁料。基準(zhǔn)點(diǎn)的選取可能會(huì)影響快速排序的效率系羞。

算法的思維

然后分別從數(shù)組的兩端掃描數(shù)組郭计，設(shè)兩個(gè)指示標(biāo)志（low指向起始位置，high指向末尾)椒振，首先從后半部分開(kāi)始昭伸，如果發(fā)現(xiàn)有元素比該基準(zhǔn)點(diǎn)的值小，就交換low和high位置的值澎迎。

然后從前半部分開(kāi)始掃秒庐杨，發(fā)現(xiàn)有元素大于基準(zhǔn)點(diǎn)的值，就交換low和high位置的值夹供，如此往復(fù)循環(huán)辑莫，直到low>=high,然后把基準(zhǔn)點(diǎn)的值放到high這個(gè)位置。

Image-快速排序.png

算法性能

• 理想的情況：算法的時(shí)間復(fù)雜度為 O(nlog2 n)

• 最壞的情況：排序算法的時(shí)間復(fù)雜度為 O(n^2)

• 快速排序的空間復(fù)雜度為O(log2n))罩引；

【注釋】：它是基于關(guān)鍵字比較的內(nèi)部排序算法中速度最快的各吨，快速排序亦因此而得名。

public class QuickSort {

    private int array[]; //定義一個(gè)數(shù)組
    private int length;  // 定義一個(gè)私有屬性

    public void sort(int[] inputArr) {
        if (inputArr == null || inputArr.length == 0) {
            return;
        }
        this.array = inputArr;
        length = inputArr.length;
        quickSort(0, length - 1);
    }
    // 快速排序算法
    private void quickSort(int lowerIndex, int higherIndex) {
        int i = lowerIndex;
        int j = higherIndex;
        
        int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
        // 分為兩部分
        while (i <= j) {
            while (array[i] < pivot) {
                i++;
            }
            while (array[j] > pivot) {
                j--;
            }
            if (i <= j) {
                exchangeNumbers(i, j);
                //move index to next position on both sides
                i++;
                j--;
            }
        }
        // call quickSort() method recursively
        if (lowerIndex < j)
            quickSort(lowerIndex, j);
        if (i < higherIndex)
            quickSort(i, higherIndex);
    }
    // 元素置換
    private void exchangeNumbers(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void main(String a[]){
        QuickSort sorter = new QuickSort();
        int[] input = {11,88,9,99,66,77,333,678,345,123,101,100,90,55};
        sorter.sort(input);
        for(int i:input){
            System.out.print(i);
            System.out.print(" ");
        }
    }
}

Image快速排序

三袁铐、歸并排序

歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用揭蜒。

通過(guò)將已有序的子序列合并，得到完全有序的序列剔桨；即先使每個(gè)子序列有序屉更，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表洒缀，稱為二路歸并瑰谜。

GIF形象表示歸時(shí)并

算法描述

• 第一步：申請(qǐng)空間欺冀，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列

• 第二步：設(shè)定兩個(gè)指針萨脑，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置

• 第三步：比較兩個(gè)指針?biāo)赶虻脑匾x擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置

算法地位

速度僅次于快速排序渤早，為穩(wěn)定排序算法职车。

歸并原理.png

【Java_Code】語(yǔ)言解法如下：

public class MergeSort {

    private int[] array;
    private int[] tempMergArr;
    private int length;

    public static void main(String a[]){

        int[] inputArr = {11，88,9,99,66,77,333,678,345,123,101,100,90,55};
        MergeSort mms = new MergeSort();
        mms.sort(inputArr);
        for(int i:inputArr){
            System.out.print(i);
            System.out.print(" ");
        }
    }

    public void sort(int inputArr[]) {
        this.array = inputArr;
        this.length = inputArr.length;
        this.tempMergArr = new int[length];
        doMergeSort(0, length - 1);
    }

    private void doMergeSort(int lowerIndex, int higherIndex) {

        if (lowerIndex < higherIndex) {
            int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
            // Below step sorts the left side of the array
            doMergeSort(lowerIndex, middle);
            // Below step sorts the right side of the array
            doMergeSort(middle + 1, higherIndex);
            // Now merge both sides
            mergeParts(lowerIndex, middle, higherIndex);
        }
    }

    private void mergeParts(int lowerIndex, int middle, int higherIndex) {

        for (int i = lowerIndex; i <= higherIndex; i++) {
            tempMergArr[i] = array[i];
        }
        int i = lowerIndex;
        int j = middle + 1;
        int k = lowerIndex;
        while (i <= middle && j <= higherIndex) {
            if (tempMergArr[i] <= tempMergArr[j]) {
                array[k] = tempMergArr[i];
                i++;
            } else {
                array[k] = tempMergArr[j];
                j++;
            }
            k++;
        }
        while (i <= middle) {
            array[k] = tempMergArr[i];
            k++;
            i++;
        }
    }
}

歸并排序

【Python_Code】

def MergeSort(lists):
    if len(lists) <= 1:
        return lists
    num = int( len(lists) / 2 )
    left = MergeSort(lists[:num])
    right = MergeSort(lists[num:])
    return Merge(left, right)
def Merge(left,right):
    r, l=0, 0
    result=[]
    while l<len(left) and r<len(right):
        if left[l] <= right[r]:
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1
    result += list(left[l:])
    result += list(right[r:])
    return result
print MergeSort([1, 2, 3, 4, 5, 6, 7, 90, 21, 23, 45])