“`” 参考回答：
归并算法：
<pre><code>#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;
}
</code></pre>
小顶堆：
<pre><code>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)));
}
}
</code></pre>
<pre><code> "“`
Was this helpful?
0 /
0