前言

好久沒有更新文章啦，前段時間練習JavaWeb的一個專案去了，有一說一，沒有用到spring的系列框架，構建一個javaweb的專案確實有點麻煩，最后卡在了用jsp實作購物車的功能，后續，等到自己Java功底逐漸成熟過后，我也會更新JavaWeb相關的文章

今天給大家帶來的是一種高級排序

歸并排序

一、什么是歸并排序？

以整個陣列為物件執行mergeSort
mergeSort:
1.將給定的包含n個元素的區域陣列分割成兩個區域陣列，
每個陣列包含n/2個元素
2.對兩個區域陣列分別執行mergeSort排序
3.通過merge將兩個已經排序完畢的區域陣列“整合”成一個數
組

二、分析步驟

1.分割陣列

在解釋分割陣列之前，我們不得不提一下分治法，

分治法可以通俗的解釋為：把一片領土分解，分解為若干塊小部分，然后一塊塊地占領征服，被分解的可以是不同的政治派別或是其他什么，然后讓他們彼此異化，
分治法的精髓：
分–將問題分解為規模更小的子問題；
治–將這些規模更小的子問題逐個擊破；
合–將已解決的子問題合并，最終得出“母”問題的解；

簡單的來說，分三步：
1.將問題“分割”
2.遞回求解區域問題
3.整合，解決原問題

2.分別排序

這里我們用到遞回，分別對分割后的兩個陣列進行排序

mergeSort(A,n,left,mid);
mergeSort(A,n,mid,right);

3.整合陣列

這里在提一點，在遞回時，一定要有結束條件，所以，這里給出merge進行遞回結束，

void merge(int[] A,int n,int left,int mid,int right){
        int n1 = mid - left;
        int n2 = right - mid;
        for (int i = 0; i < n1; i++) {
            L[i] = A[left+i];
        }
        for (int i = 0; i < n2; i++) {
            R[i] = A[mid+i];
        }
        L[n1] = R[n2] = SENTINEL;
        int i = 0,j = 0;
        for (int k = left; k < right; k++) {
            cut++;
            if (L[i]<=R[j])
                A[k] = L[i++];
            else
                A[k] = R[j++];
        }
    }

總結

所謂的高等排序，都是將初等函式進行分割，在用分治的思想構建而成，

需要完整的代碼來我的GitHub

在這里插入圖片描述

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/264822.html

標籤：java

上一篇：一致性Hash演算法在分布式場景的應用

下一篇：外觀模式