快捷導(dǎo)航

Java經(jīng)典排序算法之歸并排序?qū)崿F(xiàn)代碼

更新時間：2023年10月20日 10:01:42 作者：惡魔青葉

這篇文章主要介紹了Java經(jīng)典排序算法之歸并排序?qū)崿F(xiàn)代碼,歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法的一個非常典型的應(yīng)用,將已有序的子序列合并,得到完全有序的序列,需要的朋友可以參考下

1.簡介

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

將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。

歸并排序的時間復(fù)雜度是O(nlogn），空間復(fù)雜度是O(n)。是穩(wěn)定的排序。

歸并排序的思路流程是：

第一步、將待排序數(shù)列中的數(shù)字分為若干組，每個數(shù)字分成一組，即如果數(shù)列中8個數(shù)字，就分成8組。
第二步、將這些組兩兩合并，保證合并之后的數(shù)列是有序的。
第三步、重復(fù)第二步操作，直到只剩下一組，即排序完成。

看文字理解可能有點云里霧里，接下來我們用圖來解釋下這個過程。

2.圖解步驟

在這里插入圖片描述

3.代碼實現(xiàn)

import java.util.Arrays;
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {2,3,4,1,5,7,8,6};
        System.out.println(Arrays.toString(arr));
        mergeSort(arr,0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    /**
     *
     * @param arr  //待排序數(shù)組
     * @param low  //左邊標(biāo)識
     * @param high  //右邊標(biāo)識
     */
    public static void mergeSort(int[] arr,int low,int high){
           if(low >= high){
               return;
           }
           int mid = (low +high) >>> 1;
           mergeSort(arr,low,mid);
           mergeSort(arr,mid+1,high);
           //合并
           merge(arr, low, mid, high);
    }
    private static void merge(int[] arr, int low, int mid, int high) {
          int s1 = low;  //第一個歸并段開始
          int s2 = mid+1 ;//第二個歸并段開始
          //臨時數(shù)組
          int[] ret  = new int[high-low +1];
          int i = 0; //ret數(shù)組的下標(biāo)
         //歸并段有數(shù)據(jù)
         while (s1 <= mid && s2 <=high )
         {
                  //s1和s2數(shù)據(jù)比較
             if(arr[s1] <= arr[s2]){
                 ret[i++] = arr[s1++];
             }else {
                    ret[i++] = arr[s2++];
             }
         }
         //跳出循環(huán)
        while (s1 <= mid){
            ret[i++] = arr[s1++];
        }
        while (s2 <= high){
            ret[i++] = arr[s2++];
        }
        for (int j = 0; j < ret.length ; j++) {
                    arr[j+low]= ret[j];
        }
    }
}

到此這篇關(guān)于Java經(jīng)典排序算法之歸并排序?qū)崿F(xiàn)代碼的文章就介紹到這了,更多相關(guān)Java歸并排序?qū)崿F(xiàn)代碼內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: