现场用collabedit写代码，一个怪异的归并算法。。。之前没遇到过，直接把归并写出来，但是说复杂度太高，优化了三遍还不行，最后说出用小顶堆解决了。。。

Answer 1

参考回答：

归并算法：

#include using namespace std;
//将有二个有序数列a[first...mid]和a[mid...last]合并。
void __merge(int a[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;
while (i <= m && j <= n)
{
	if (a[i] <= a[j])
		temp[k++] = a[i++];
	else
		temp[k++] = a[j++];
}
while (i <= m)
temp[k++] = a[i++];
while (j <= n)
temp[k++] = a[j++];
for (i = 0; i < k; i++)
	a[first + i] = temp[i];
}
void __merge_sort(int a[], int first, int last, int temp[])
{
    if (first < last)
    {
        int mid = (first + last) / 2;
        __merge_sort(a, first, mid, temp);
        __merge_sort(a, mid + 1, last, temp);
        __merge(a, first, mid, last, temp);
    }
}
bool MergeSort(int a[], int n)
{
    int *p = new int[n];
    if (p == NULL)
    {
    	return false;
    }
    else
    {
    	__merge_sort(a, 0, n - 1, p);
    	delete[] p;
    	return true;
    }
}
int main()
{
    const int LEN = 10;
    int a[LEN] = { 23, 40, 45, 19, 12, 16, 90, 39, 87, 71 };
    cout<<"Before the merge sort, the Array is:"<<endl;
    for(int i = 0; i < LEN; ++i)
    {
    	cout<<a[i]<<" ";
    }
    cout<<endl;
    cout<<endl;
    MergeSort(a, LEN);
    cout<<"After the merge sort, the Array is:"<<endl;
    for(int i = 0; i < LEN; ++i)
    {
    	cout<<a[i]<<" ";
    }
    cout<<endl;
    system("pause");
    return 0;
}

小顶堆：

import java.util.Arrays;
public class SmallHeap {
    public static int[] topN(int[] arr, int n) {
    int[] list = new int[n];
    System.arraycopy(arr, 0, list, 0, n);
    for (int i = 0; i < n; i++) {
    	int t = i; while (t != 0 && list[parent(t)] > list[t]) {
    	swap(list, t, t = parent(t));
    }}
    for (int i = n, len = arr.length; i < len; i++) {
    if (arr[i] >= list[0]) {
    // 置换栈顶
    list[0] = arr[i];
    // 调整栈顶
    int t = 0;
    while((left(t)<n&&list[t]>list[left(t)])||(right(t)<n&& list[t]>list[right(t)])) {
    if (right(t) < n && list[right(t)] < list[left(t)]) {
    swap(list, t, t = right(t));
    } else {
    swap(list, t, t = left(t));
    }
    }
    }
    }
    return list;
    }
    private static void swap(int[] list, int i, int j) {
    int tmp = list[i];
    list[i] = list[j];
    list[j] = tmp;
    }
    private static int parent(int i) {
    return (i - 1) / 2;
    }
    private static int left(int i) {
    return 2 * i + 1;
    }
    private static int right(int i) {
    return 2 * i + 2;
    }
    public static void main(String[] args) {
        int[] arr = new int[]{56, 30, 71, 18, 29, 93, 44, 75, 20, 65, 68, 34};
        System.out.println("原始数组: ");
        System.out.println(Arrays.toString(arr));
        System.out.println("调整后数组: ");
        System.out.println(Arrays.toString(SmallHeap.topN(arr, 5)));
    }
}