蜜桃av色欲a片精品一区,麻豆aⅴ精品无码一区二区,亚洲人成网站在线播放影院在线,亚洲 素人 字幕 在线 最新

  基礎(chǔ)算法篇——?dú)w并排序

發(fā)布日期：2022/11/2 10:27:47      瀏覽量：

本次我們介紹基礎(chǔ)算法中的快速排序，我們會從下面幾個(gè)角度來介紹快速排序：

• 歸并排序思想
• 歸并排序代碼
• 歸并排序拓展

歸并排序思想

我們首先來介紹歸并排序思想（分治思想）：

1. 確定分界點(diǎn)

我們首先確定整個(gè)數(shù)組的分界點(diǎn)
以我們的習(xí)慣而言還是以arr[l],arr[r],arr[(r+l)/2]為分界點(diǎn)

1. 遞歸排序

我們首先需要將數(shù)組分界點(diǎn)兩側(cè)進(jìn)行分組，這時(shí)他們會劃分為左側(cè)和右側(cè)
我們再對已經(jīng)劃分的左側(cè)和右側(cè)進(jìn)行分界點(diǎn)分組，這時(shí)就會劃分為4個(gè)分組
依次類推，直到每個(gè)分組數(shù)為1時(shí)結(jié)束分組，然后我們才會開始進(jìn)行歸并操作

1. 歸并數(shù)組

這個(gè)方法需要額外空間：我們需要一個(gè)新數(shù)組來裝排序完成的數(shù)組
我們首先對最后一次分組的左右側(cè)進(jìn)行歸并，將兩組個(gè)數(shù)為1的分組化為一個(gè)排序整齊的組
依次類推，我們從開始的一個(gè)數(shù)為一組變?yōu)閮蓚€(gè)數(shù)為一組，逐漸歸并，直到最后所有數(shù)都變?yōu)橐唤M

至于歸并的方法：
我們目前左右兩側(cè)的數(shù)組是順序排列，我們只需要依次比較左右兩側(cè)最小數(shù)的大小
我們依舊采用指針的方法，左側(cè)指向l，右側(cè)指向mid+1，同時(shí)比較兩者大小，將較小的數(shù)拿出來放在數(shù)組中，并且將指針向后移動(dòng)一位

歸并排序代碼

我們這里給出歸并排序的代碼展示：

import java.util.Scanner; public class Main { public static final int N = 10000010; // 額外空間數(shù)組：這里也可以在歸并方法中設(shè)置，設(shè)置大小為r-l+1即可滿足條件 public static int[] tmp = new int[N]; public static void main(String[] args) { // 給出數(shù)組 Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] arr = new int[n]; for (int i = 0; i < arr.length; i++) {
            arr[i] = scanner.nextInt();
        } // 打印數(shù)組 System.out.print("排序前："); for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
        }
        System.out.println(" "); // 進(jìn)行歸并排序 merge_sort(arr,0,n-1); // 打印數(shù)組 System.out.print("排序后："); for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
        }
        System.out.println(" ");

    } private static void merge_sort(int[] arr,int l,int r) { // 判斷還存在數(shù)組？ if (l >= r) return; // 設(shè)置中間值 int mid = (l+r)/2; // 先進(jìn)行排序 merge_sort(arr,l,mid);
        merge_sort(arr,mid+1,r); // 對左右兩側(cè)進(jìn)行判斷 // k是目前排序的數(shù),i,j為左右兩側(cè)指針 int k = 0; int i = l,j = mid + 1; // 比較判斷 while (i <= mid && j <= r){ if (arr[i] < arr[j]){
                tmp[k++] = arr[i++];
            }else {
                tmp[k++] = arr[j++];
            }
        } // 判斷左右剩余？然后累加在最后 while (i <= mid){
            tmp[k++] = arr[i++];
        } while (j <= r){
            tmp[k++] = arr[j++];
        } // 最后賦值回去 for (i = l, j = 0; i <= r;i++,j++){
            arr[i] = tmp[j];
        }
    }
}

歸并排序拓展

題目：

• 給定一個(gè)長度為n的整數(shù)數(shù)列，請你計(jì)算數(shù)列中的逆序?qū)Φ臄?shù)量

逆序?qū)Χx：

• 對于數(shù)列的第 i 個(gè)和第 j 個(gè)元素，如果滿足 i < j 且 a[i] > a[j]，則其為一個(gè)逆序?qū)?；否則不是。

解題思路：

• 我們采用分治的思想，使用歸并排序?qū)⒛嫘驅(qū)Φ臄?shù)量統(tǒng)計(jì)分為三部分
• 第一部分：左半邊逆序?qū)?shù)量meger_sort(L,mid)
• 第二部分：右半邊逆序?qū)?shù)量meger_sort(mid+1,R)
• 第三部分：左右兩側(cè)逆序?qū)?shù)量

解題要點(diǎn)：

• 實(shí)際上我們的第一部分和第二部分的數(shù)量計(jì)算都是基于第三部分的逆序?qū)y(tǒng)計(jì)，所以我們只需要思考第三部分的計(jì)算

解題方法：

• 我們左右兩側(cè)的數(shù)都是按照順序排列
• 所以我們只需要按順序?qū)⒋笥谟覀?cè)某個(gè)數(shù)的左側(cè)的第一個(gè)數(shù)找出來，然后該數(shù)后面的數(shù)都會大于右側(cè)的數(shù)
• 我們通過簡單的計(jì)算可以得知，該數(shù)所對應(yīng)的逆序?qū)Φ膫€(gè)數(shù)為mid - i + 1

解題代碼：

import java.util.Scanner; public class mmm { private static final int N = 1000010; private static int[] tmp = new int[N]; // 逆序?qū)€(gè)數(shù) private static int result = 0; public static void main(String[] args) { // 基本歸并框架 Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] arr = new int[n]; for (int i = 0;i < arr.length;i++){
            arr[i] = scanner.nextInt();
        }

        System.out.print("排序前："); for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
        }
        System.out.println("");

        merge_sort(arr,0,n-1);


        System.out.print("排序后："); for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
        }
        System.out.println("");

        System.out.println("逆序?qū)? + result + "個(gè)");
    } private static void merge_sort(int[] arr,int l,int r) { if (l >= r) return; int mid = (l+r)/2;

        merge_sort(arr, l, mid);
        merge_sort(arr,mid+1,r); int k = 0; int i = l,j = mid+1; while (i <= mid && j<= r){ if (arr[i] < arr[j]){
                tmp[k++] = arr[i++];
            }else {
                tmp[k++] = arr[j++]; // 我們找到了右側(cè)該數(shù)的針對左側(cè)最小的大于該數(shù)的值，并根據(jù)其計(jì)算逆序?qū)?/span> result += mid - i + 1;
            }
        } while (i <= mid){
            tmp[k++] = arr[i++];
        } while (j <= r){
            tmp[k++] = arr[j++];
        } for (i=l,j=0;i<=r;i++,j++){
            arr[i] = tmp[j];
        }
    }
}