合并两个排序的一半，无需额外的内存！
|
给定一个整数数组，其前半部分和后半部分已排序。编写一个函数将两个部分合并以在原位置创建一个单个排序的数组（不要使用多余的空间）。
一种方法是
例如：
// 1,3,6,8，-5，-2,3,8
int l = 0;
int u = size;
int mid = (l+u)/2;
int i;
for (i = 0; i < mid; i++) {
for (j = mid; j < size; j++) {
if (a[i] >= a[j]) {
temp = a[j];
for (i = mid-1; i >= 0; i--)
a[i+1] = a[i];
a[0] = temp;
}
}
}
没有找到相关结果
已邀请:
5 个回复
醒荒捆府绣
/** * Created by deian on 2016-12-22. */ public class Merge { public static void swap(int[] a, int i1, int i2) { int t = a[i1]; a[i1] = a[i2]; a[i2] = t; } public static void merge(int[] a) { int i1 = 0; int i2 = a.length / 2; System.out.printf(\" %s, i(%d,%d) \\n\", Arrays.toString(a), i1, i2 ); for (int di = 0; di < a.length-1; di++) { int ni; int oi1=i1; int oi2=i2; // i1 and i2 - always point to the smallest known numbers if (a[i1] > a[i2]) { ni = i2; i2++; if (i2>=a.length) { i2--; } } else { ni = i1; i1++; if (i1 >= i2) { i1 = di; } } if (di == i1) { i1 = ni; } swap(a, di, ni); System.out.printf(\"#%d: %s, i(%d,%d)s(%d>%d)i(%d,%d) \\n\", di+1, Arrays.toString(a), oi1, oi2,ni, di, i1,i2); } System.out.printf(\" %s\\n\", Arrays.toString(a)); } public static void main(String[] args) { // int[] a = new int[]{1, 3, 6, 8, -5, -2, 3, 8}; // int[] a = new int[]{1, 3, 6, 8, -5, 2, 3, 8}; int[] a = new int[]{1, 5, 6, 8, -5, 2, 3, 4}; merge(a); } }脖呐
伞腹
#include <stdio.h> void sort(int index, int start1, int end1, int start2, int end2, int* array) { if (index >= end2) { return; } int lower; if (array[start1] <= array[start2]) { lower = array[start1]; sort(index+1, start1+1, end1, start2, end2, array); } else { lower = array[start2]; sort(index+1, start1, end1, start2+1, end2, array); } array[index]=lower; } int main(int argc, char** argv) { int a[] = {1,3,6,8,-5,-2,3,8}; sort(0, 0, 3, 4, 7, a); int i; for (i = 0; i <= 7; i++) { printf(\"%d, \", a[i]); } printf(\"\\n\"); return 0; }芭隘的盘石
究补闯
void Merge(int array[N]) { for(int i=N/2;i<N;i++){ int j=i; while(array[j]<array[j-1]&& j>=1){ int temp=array[j]; array[j]=array[j-1]; array[j-1]=temp; j--; } } } void Merge2(int array[N]) { for(int i=N/2;i<N;i++){ int key=array[i]; int j=i-1; while(array[j]>key&& j>=0){ array[j+1]=array[j]; j--; } array[j+1]=key; } }