Java實現(xiàn)插入排序,希爾排序和歸并排序

更新時間：2022年12月22日 11:05:37 作者：程序小猿2

這篇文章主要為大家詳細介紹了插入排序,希爾排序和歸并排序的多種語言的實現(xiàn)（JavaScript、Python、Go語言、Java），感興趣的小伙伴可以了解一下

插入排序

插入排序的代碼實現(xiàn)雖然沒有冒泡排序和選擇排序那么簡單粗暴，但它的原理應(yīng)該是最容易理解的了，因為只要打過撲克牌的人都應(yīng)該能夠秒懂。插入排序是一種最簡單直觀的排序算法，它的工作原理是通過構(gòu)建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。

插入排序和冒泡排序一樣，也有一種優(yōu)化算法，叫做拆半插入。

算法步驟

1.將第一待排序序列第一個元素看做一個有序序列，把第二個元素到最后一個元素當(dāng)成是未排序序列。

2.從頭到尾依次掃描未排序序列，將掃描到的每個元素插入有序序列的適當(dāng)位置。（如果待插入的元素與有序序列中的某個元素相等，則將待插入元素插入到相等元素的后面。）

動圖演示

JavaScript代碼實現(xiàn)

function insertionsort(arr){
    var len = arr.length;
    var preIndex,current;
    for(var i = 1;i < len;i++){
        preIndex = i - 1;
        current = arr[i];
        while(preIndex >= 0 && arr[preIndex] > current){
            arr[preIndex+1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex+1] = current;
    }
    return arr;
}

Python代碼實現(xiàn)

def insertionSort(arr):
    for i in range(len(arr)):
        preIndex = i-1
        current = arr[i]
        while preIndex >= 0 and arr[preIndex] > current:
            arr[preIndex+1] = arr[preIndex]
            preIndex-=1
        arr[preIndex+1] = current
    return arr

Go代碼實現(xiàn)

func insertionSort(arr []int)[]int{
    for i := range arr {
        preIndex := i - 1
        current := arr[i]
        for preIndex >= 0 && arr[preIndex] > current {
            arr[preIndex+1] = arr[preIndex]
            preIndex -= 1
        }
        arr[preIndex+1] = current
    }
    return arr
}

Java代碼實現(xiàn)

public class InsertSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        //對arr進行拷貝，不改變參數(shù)內(nèi)容
        int[] arr = Array.copyOf(sourceArray,sourceArray.length);
        
        //從下標(biāo)為1的元素開始選擇合適的位置插入，因為下標(biāo)為0的只有一個元素，默認(rèn)是有序的
        for(int i = 1;i < arr.length;i++{
        
            //記錄要插入的數(shù)據(jù)
            int temp = arr[i];
            
            //從已經(jīng)排序的序列最右邊開始比較，找到比其小的數(shù)
            int j = i;
            while(j > 0 && temp < arr[j - 1] {
                arr[j] = arr[j-1];
                j--;
            }
            
            //存在比其小的數(shù)，插入
            if(j != i){
                arr[j] = temp;
            }
            
        }
        return arr;
    }
}

希爾排序

希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。但希爾排序是非穩(wěn)定排序算法。

希爾排序是基于插入排序以下兩點性質(zhì)而提出改進方法的：

插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時，效率高，即可以達到線性排序的效率；
但插入排序一般來說是低效的，因為插入排序每次只能將數(shù)據(jù)移動一位；

希爾排序的基本思想是：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。

算法步驟

選擇一個增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
按增量序列個數(shù) k，對序列進行 k 趟排序；
每趟排序，根據(jù)對應(yīng)的增量 ti，將待排序列分割成若干長度為 m 的子序列，分別對各子表進行直接插入排序。僅增量因子為 1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

JavaScript代碼實現(xiàn)

function shellSort(arr) {
    var len = arr.length,
        temp,
        gap = 1;
    while(gap < len/3) { //動態(tài)定義間隔序列
        gap =gap*3+1;
    }
    for (gap; gap > 0; gap = Math.floor(gap/3)) {
        for (var i = gap; i < len; i++) {
            temp = arr[i];
            for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
                arr[j+gap] = arr[j];
            }
            arr[j+gap] = temp;
        }
    }
    return arr;
}

python代碼實現(xiàn)

def shellSort(arr):
    import math
    gap=1
    while(gap < len(arr)/3):
        gap = gap*3+1
    while gap > 0:
        for i in range(gap,len(arr)):
            temp = arr[i]
            j = i-gap
            while j >=0 and arr[j] > temp:
                arr[j+gap]=arr[j]
                j-=gap
            arr[j+gap] = temp
        gap = math.floor(gap/3)
    return arr
}

Go代碼實現(xiàn)

func shellSort(arr []int) []int {
    length := len(arr)
    gap := 1
    for gap < gap/3 {
        gap = gap*3 + 1
    }
    for gap > 0 {
        for i := gap; i < length; i++ {
            temp := arr[i]
            j := i - gap
            for j >= 0 && arr[j] > temp {
                arr[j+gap] = arr[j]
                j -= gap
            }
            arr[j+gap] = temp
        }
        gap = gap / 3
    }
    return arr
}

Java代碼實現(xiàn)

public class ShellSort implements IArraySort{

    @Override
    public int[] sort(int[] sourceArray) throws Exception{
        //對arr進行拷貝，不改變參數(shù)內(nèi)容
        int[] arr = Arrays.copyOf(sourceArray,sourceArray.length);
        
        int gap = 1;
        while(gap < arr.length/3){
            gap = gap * 3 = 1;
        }
        
        while(gap > 0){
            for (int i = gap; i < arr.length; i++) {
                int tmp = arr[i];
                int j = i - gap;
                while (j >= 0 && arr[j] > tmp) {
                    arr[j + gap] = arr[j];
                    j -= gap;
                }
                arr[j + gap] = tmp;
            }
            gap = (int) Math.floor(gap / 3);
        }

        return arr;
    }
}

歸并排序

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

作為一種典型的分而治之思想的算法應(yīng)用，歸并排序的實現(xiàn)由兩種方法：

自上而下的遞歸（所有遞歸的方法都可以用迭代重寫，所以就有了第 2 種方法）；
自下而上的迭代；

在《數(shù)據(jù)結(jié)構(gòu)與算法 JavaScript 描述》中，作者給出了自下而上的迭代方法。但是對于遞歸法，作者卻認(rèn)為：

However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.

然而，在 JavaScript 中這種方式不太可行，因為這個算法的遞歸深度對它來講太深了。

說實話，我不太理解這句話。意思是 JavaScript 編譯器內(nèi)存太小，遞歸太深容易造成內(nèi)存溢出嗎？還望有大神能夠指教。

和選擇排序一樣，歸并排序的性能不受輸入數(shù)據(jù)的影響，但表現(xiàn)比選擇排序好的多，因為始終都是 O(nlogn) 的時間復(fù)雜度。代價是需要額外的內(nèi)存空間。

算法步驟

1.申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列；

2.設(shè)定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置；

3.比較兩個指針?biāo)赶虻脑?，選擇相對小的元素放入到合并空間，并移動指針到下一位置；

4.重復(fù)步驟 3 直到某一指針達到序列尾；

5.將另一序列剩下的所有元素直接復(fù)制到合并序列尾。

動圖演示

JavaScript代碼實現(xiàn)

function mergeSort(arr) { // 采用自上而下的遞歸方法
    var len = arr.length;
    if(len < 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right)
{
    var result = [];

    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}

python代碼實現(xiàn)

def mergeSort(arr):
    import math
    if(len(arr)<2):
        return arr
    middle = math.floor(len(arr)/2)
    left, right = arr[0:middle], arr[middle:]
    return merge(mergeSort(left), mergeSort(right))
    
def merge(left,right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0));
        else:
            result.append(right.pop(0));
    while left:
        result.append(left.pop(0));
    while right:
        result.append(right.pop(0));
    return result

Go代碼實現(xiàn)

func mergeSort(arr []int) []int {
    length := len(arr)
    if length < 2 {
        return arr
    }
    middle := length / 2
    left := arr[0:middle]
    right := arr[middle:]
    return merge(mergeSort(left), mergeSort(right))
}

func merge(left []int, right []int) []int {
    var result []int
    for len(left) != 0 && len(right) != 0 {
        if left[0] <= right[0] {
            result = append(result, left[0])
            left = left[1:]
        } else {
            result = append(result, right[0])
            right = right[1:]
        }
    }

    for len(left) != 0 {
        result = append(result, left[0])
        left = left[1:]
    }

    for len(right) != 0 {
        result = append(result, right[0])
        right = right[1:]
    }

    return result
}

Java代碼實現(xiàn)

public class MergeSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 對 arr 進行拷貝，不改變參數(shù)內(nèi)容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        if (arr.length < 2) {
            return arr;
        }
        int middle = (int) Math.floor(arr.length / 2);

        int[] left = Arrays.copyOfRange(arr, 0, middle);
        int[] right = Arrays.copyOfRange(arr, middle, arr.length);

        return merge(sort(left), sort(right));
    }

    protected int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0;
        while (left.length > 0 && right.length > 0) {
            if (left[0] <= right[0]) {
                result[i++] = left[0];
                left = Arrays.copyOfRange(left, 1, left.length);
            } else {
                result[i++] = right[0];
                right = Arrays.copyOfRange(right, 1, right.length);
            }
        }

        while (left.length > 0) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }

        while (right.length > 0) {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }

        return result;
    }

}

以上就是Java實現(xiàn)插入排序,希爾排序和歸并排序的詳細內(nèi)容，更多關(guān)于Java排序的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: