題目描述
承上題，藉由統計位移或是交換元素的次數來計算快速排序法和插入排序法的執行次數，來比較每次都以最尾端的元素作為支點的快速排序法究竟比插入排序法快多少。
原題網址
輸入格式
輸入第一行是一個整數n，範圍在1到1000之間(包含1和1000)，代表陣列的元素數量。
第二行輸入陣列的所有元素，以空格隔開。元素值的範圍在-1000到1000之間(包含-1000和1000)，且不會重複。
輸出格式
分別統計快速排序法位移元素的次數和插入排序法交換元素的次數，將快速排序法位移元素的次數減掉插入排序法交換元素的次數後輸出。
範例輸入
7
1 3 9 8 2 7 5
1 3 9 8 2 7 5
範例輸出
1
額外解釋
插入排序法的過程如下：
● 索引 0 1 2 3 4 5 6 數值 1 3 9 8 2 7 5 ○ ● 索引 0 1 2 3 4 5 6 數值 1 3 9 8 2 7 5 └┬┘ 1 < 3 ○ ○ ● 索引 0 1 2 3 4 5 6 數值 1 3 9 8 2 7 5 └┬┘ 3 < 9 ○ ○ ○ ● 索引 0 1 2 3 4 5 6 數值 1 3 9 8 2 7 5 └┬┘ 9 > 8 ○ ○ 8 ● 索引 0 1 2 3 4 5 6 數值 1 3 9 9 2 7 5 └→┘ ○ ○ 8 ● 索引 0 1 2 3 4 5 6 數值 1 3 9 9 2 7 5 └┬┘ 3 < 8 ○ ○ ○ ○ ● 索引 0 1 2 3 4 5 6 數值 1 3 8 9 2 7 5 └┬┘ 9 > 2 ○ ○ ○ 2 ● 索引 0 1 2 3 4 5 6 數值 1 3 8 9 9 7 5 └→┘ ○ ○ ○ 2 ● 索引 0 1 2 3 4 5 6 數值 1 3 8 9 9 7 5 └┬┘ 8 > 2 ○ ○ 2 ○ ● 索引 0 1 2 3 4 5 6 數值 1 3 8 8 9 7 5 └→┘ ○ ○ 2 ○ ● 索引 0 1 2 3 4 5 6 數值 1 3 8 8 9 7 5 └┬┘ 3 > 2 ○ 2 ○ ○ ● 索引 0 1 2 3 4 5 6 數值 1 3 3 8 9 7 5 └→┘ ○ 2 ○ ○ ● 索引 0 1 2 3 4 5 6 數值 1 3 3 8 9 7 5 └┬┘ 1 < 2 ○ ○ ○ ○ ○ ● 索引 0 1 2 3 4 5 6 數值 1 2 3 8 9 7 5 └┬┘ 9 > 7 ○ ○ ○ ○ 7 ● 索引 0 1 2 3 4 5 6 數值 1 2 3 8 9 9 5 └→┘ ○ ○ ○ ○ 7 ● 索引 0 1 2 3 4 5 6 數值 1 2 3 8 9 9 5 └┬┘ 8 > 7 ○ ○ ○ 7 ○ ● 索引 0 1 2 3 4 5 6 數值 1 2 3 8 8 9 5 └→┘ ○ ○ ○ 7 ○ ● 索引 0 1 2 3 4 5 6 數值 1 2 3 8 8 9 5 └┬┘ 3 < 7 ○ ○ ○ ○ ○ ○ ● 索引 0 1 2 3 4 5 6 數值 1 2 3 7 8 9 5 └┬┘ 9 > 5 ○ ○ ○ ○ ○ 5 ● 索引 0 1 2 3 4 5 6 數值 1 2 3 7 8 9 9 └→┘ ○ ○ ○ ○ ○ 5 ● 索引 0 1 2 3 4 5 6 數值 1 2 3 7 8 9 9 └┬┘ 8 > 5 ○ ○ ○ ○ 5 ○ ● 索引 0 1 2 3 4 5 6 數值 1 2 3 7 8 8 9 └→┘ ○ ○ ○ ○ 5 ○ ● 索引 0 1 2 3 4 5 6 數值 1 2 3 7 7 8 9 └→┘ 7 > 5 ○ ○ ○ 5 ○ ○ ● 索引 0 1 2 3 4 5 6 數值 1 2 3 7 7 8 9 └┬┘ 3 < 5 ○ ○ ○ ○ ○ ○ ○ 索引 0 1 2 3 4 5 6 數值 1 2 3 5 7 8 9 ----------------演算法至此結束----------------
共位移9次。
快速排序法的過程如下：
●
索引 0 1 2 3 4 5 6
數值 1 3 9 8 2 7 5
＞ ＜ ●
索引 0 1 2 3 4 5 6
數值 1 3 9 8 2 7 5 累計：2
＞ ＜ ●
索引 0 1 2 3 4 5 6
數值 1 3 2 8 9 7 5 累計：3
└───┘
＜
＞ ●
索引 0 1 2 3 4 5 6
數值 1 3 2 8 9 7 5
＜
＞ ●
索引 0 1 2 3 4 5 6
數值 1 3 2 5 9 7 8 累計：4
└─────┘
○
索引 0 1 2 3 4 5 6
數值 1 3 2 5 9 7 8
| ○
索引 0 1 2 | 3 4 5 6
數值 1 3 2 | 5 9 7 8
● | ○
索引 0 1 2 | 3 4 5 6
數值 1 3 2 | 5 9 7 8
＜
＞ ● | ○
索引 0 1 2 | 3 4 5 6
數值 1 3 2 | 5 9 7 8 累計：5
＜
＞ ● | ○
索引 0 1 2 | 3 4 5 6
數值 1 2 3 | 5 9 7 8 累計：6
└─┘
○ | ○
索引 0 1 2 | 3 4 5 6
數值 1 2 3 | 5 9 7 8
○ | ○ | ○ | ○
索引 0 | 1 | 2 | 3 4 5 6
數值 1 | 2 | 3 | 5 9 7 8
○ | ○ | ○ | ○ | ●
索引 0 | 1 | 2 | 3 | 4 5 6
數值 1 | 2 | 3 | 5 | 9 7 8
○ | ○ | ○ | ○ | ＞ ＜ ●
索引 0 | 1 | 2 | 3 | 4 5 6
數值 1 | 2 | 3 | 5 | 9 7 8 累計：6
○ | ○ | ○ | ○ | ＞ ＜ ●
索引 0 | 1 | 2 | 3 | 4 5 6
數值 1 | 2 | 3 | 5 | 7 9 8 累計：7
└─┘
＜
○ | ○ | ○ | ○ | ＞ ●
索引 0 | 1 | 2 | 3 | 4 5 6
數值 1 | 2 | 3 | 5 | 7 9 8
＜
○ | ○ | ○ | ○ | ＞ ●
索引 0 | 1 | 2 | 3 | 4 5 6
數值 1 | 2 | 3 | 5 | 7 8 9 累計：8
└─┘
○ | ○ | ○ | ○ | ○
索引 0 | 1 | 2 | 3 | 4 5 6
數值 1 | 2 | 3 | 5 | 7 8 9
○ | ○ | ○ | ○ | ○ | ○
索引 0 | 1 | 2 | 3 | 4 | 5 6
數值 1 | 2 | 3 | 5 | 7 | 8 9
○ | ○ | ○ | ○ | ○ | ○ | ○
索引 0 | 1 | 2 | 3 | 4 | 5 | 6
數值 1 | 2 | 3 | 5 | 7 | 8 | 9
----------------演算法至此結束----------------
共交換8次。
9-8=1，因此輸出「1」。
解題概念
有關於插入排序法的說明可以查看這篇文章：
有關於快速排序法的說明可以查看這篇文章：
這題題目定義的「交換次數」有點抽象。在計算交換次數時，即便是不需實際交換的部份也要去記錄，像是尋找比支點大的元素時，要把往右移動的距離算近交換次數中，因為在找到比支點大的元素前，比支點小的元素以原題的演算法邏輯來看的話會跟自己做交換。且在最後交換支點的時候，不管實際上有沒有交換也要去記錄次數。
參考答案
import java.util.*;
public class Solution {
private static void swap(final int[] A, final int a, final int b) {
final int tmp = A[a];
A[a] = A[b];
A[b] = tmp;
}
private static int insertionSort(final int[] array) {
final int[] A = array.clone();
final int l = A.length;
int time = 0;
for (int i = 0; i < l; ++i) {
final int temp = A[i];
int j = i - 1;
while (j >= 0 && A[j] > temp) {
A[j + 1] = A[j--];
++time;
}
A[j + 1] = temp;
}
return time;
}
private static int quickSort(final int array[], final int start, final int end) {
final int A[] = array.clone();
final int[] stack = new int[end - start + 1]; // 建立堆疊空間
int top = -1;
int s, e;
stack[++top] = start;
stack[++top] = end - 1;
int time = 0;
while (top >= 0) {
e = stack[top--];
s = stack[top--];
final int x = A[e]; // pivot
int a = s;
int b;
int c;
while (a < e && A[a] <= x) {
++a;
++time;
}
b = a;
c = b;
int d = 0;
while (c < e && A[c] >= x) {
++c;
if (A[c] < x && c < e) {
swap(A, b + d++, c);
++time;
}
}
final int f = b + d;
if (f < e) {
swap(A, f, e);
}
++time;
final int ls = s, le = f - 1;
final int rs = f + 1, re = e;
final int ll = le - ls + 1, rl = re - rs + 1;
if (rl > 1) {
stack[++top] = rs;
stack[++top] = re;
}
if (ll > 1) {
stack[++top] = ls;
stack[++top] = le;
}
}
return time;
}
public static void main(final String[] args) {
final Scanner in = new Scanner(System.in);
final int n = in.nextInt();
final int[] A = new int[n];
for (int i = 0; i < n; ++i) {
A[i] = in.nextInt();
}
System.out.println(insertionSort(A) - quickSort(A, 0, n));
}
}