[Java] insertion sort & merge sort

要熟悉某個語言，最簡單的方式就是寫一次基本的演算法。

此外，將來要面試科技公司，基本演算法更要知道怎麼寫，

怎麼用原子筆寫，這很重要。



以某科技公司為例，主管當然知道考古題的存在，

主管會認為題目已經外洩沒理由考不好，但偏偏就是有面試者考不好，

而且這間公司好的標準異常寬鬆，100分拿35分就可以了。



有時候誠意真的很重要。

如果我是主管的話，正妹直接錄取 ((逃))((當作在選後宮))



正題：

Insertion sort，對於小的 array 可以用這個實做

merge sort，divide and conquer 基本應用



public class Sorting {
public static void insertionSort(int[] array) {
for (int j = 1; j < array.length; j++) {
int key = array[j];
int i = j - 1;
while (i >= 0 && array[i] > key) {
array[i+1] = array[i];
i--;
}
array[i + 1] = key;
}
}

public static void mergeSort(int[] array) {
mergeSort(array, 0, array.length - 1);
}

private static void mergeSort(int[] array, int p, int r) {
if (p >= r) {
return;
}
int q = (p + r)/2;
mergeSort(array, p, q);
mergeSort(array, q + 1, r);
merge(array, p, q, r);
}

private static void merge(int[] array, int p, int q, int r) {
int n1 = q - p + 1;
int n2 = r - q;

int[] left = new int[n1 + 1];
int[] right = new int[n2 + 1];

for (int k = 0; k < n1; k++) {
left[k] = array[p + k];
}
for (int k = 0; k < n2; k++) {
right[k] = array[q + 1 + k];
}
left[n1] = Integer.MAX_VALUE;
right[n2] = Integer.MAX_VALUE;

int i = 0;
int j = 0;
for (int k = p; k <= r; k++) {
if (left[i] <= right[j]) {
array[k] = left[i];
i++;
}
else {
array[k] = right[j];
j++;
}
}
}
}