題目來源：https://www.acwing.com/problem/content/description/789/
題目描述
給定你一個長度為 n 的整數數列，
請你使用歸并排序對這個數列按照從小到大進行排序，
并將排好序的數列按順序輸出，
輸入格式
輸入共兩行，第一行包含整數 n，
第二行包含 n 個整數（所有整數均在 1～1091～109 范圍內），表示整個數列，
輸出格式
輸出共一行，包含 n 個整數，表示排好序的數列，
資料范圍
1≤n≤1000001≤n≤100000
輸入樣例：
5
3 1 2 4 5
輸出樣例：
1 2 3 4 5
思路講解
- 首先確定中間基準點mid = left + （right - left） / 2，在每次進行方法時先進性一次遞推進行陣列的分割，將陣列分為單個值后進行排序，在對每個小陣列及進行歸并，最后歸并為一個排好序的陣列
- 那么如何進行排序呢？我們應當確定的是，先經過遞推后的輸皆為單個數，那么二者進行比較后將該數存入臨時陣列中即可，這樣我們就得到了兩兩成對的陣列，然后我們再進行判斷，例如陣列a1,a2,b1,b2，首先我們應確定的是a1<a2,b陣列同理，那么我們便要將兩個陣列中較小的值，也就是靠前的值進行比較，然后再接著比··· ···直到整個陣列合并完成，
- 需要注意的是，為了防止某一段陣列的長度大于另一端，需加入判斷陳述句，將剩下的值一起存入臨時陣列（因為剩下的值也是排序好的，直接加進去就好）
代碼
import java.util.Scanner;
public class Main {
//開辟足夠大的陣列空間
static int N = 100010;
static int[] q = new int[N], temp = new int[N];
public static void main(String[] args) {
//輸入陣列大小以及陣列的值
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
q[i] = sc.nextInt();
}
//進行排序
merge_sort(q,0,n-1);
//輸出結果
for(int i = 0; i < n; i ++) System.out.print(q[i] + " ");
}
public static void merge_sort(int []q,int left,int right) {
//進行判斷
if (left >= right) return;
//進行遞回，將陣列分為最小單位的值,接著在從最小進行排序，逐漸到整個陣列
int mid = left + (right - left) / 2;
merge_sort(q, left, mid);
merge_sort(q, mid + 1, right);
int i = left, j = mid + 1;//建立雙指標，i指向前一個數，j指向后一個數
int k = 0;//令temp從0開始，往其中添加元素
//進行歸并操作，將數存放至臨時陣列temp
while (i <= mid && j <= right) {//確認邊界
if (q[i] <= q[j])
temp[k++] = q[i++];
else
temp[k++] = q[j++];
}
//防止i或j提前用光的情況發生
while (i <= mid) temp[k++] = q[i++];
while (j <= right) temp[k++] = q[j++];
for(i = left, k = 0; i <= right; i ++, k ++) q[i] = temp[k];//把原陣列未排序的部分覆寫成已排序部分
}
}
個人失誤
while (i <= mid && j <= right) {//確認邊界
if (q[i] <= q[j])
temp[k++] = q[i++];
else
temp[k++] = q[j++];
}
在這里我將if-else中的temp[k++] = q[i++]與temp[k++] = q[j++]中的q全部失誤寫成了temp，直接導致結果中出現了不該存在的“0”，查了好幾遍才發現······
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/544176.html
標籤：Java