我們有一個偶數排序和奇數排序的陣列，這意味著具有偶數索引的子陣列是排序的，具有奇數索引的子陣列是排序的。
例如 -{1,4,2,7,4,18,5,19,20}兩個排序的子陣列是{1,2,4,5,20}-{4,7,18,19}一組具有偶數索引，另一組具有奇數索引。
O(1)有沒有辦法用空間復雜度和時間對這個唯一排序的陣列進行排序O(n)？（意思是重新排列它以正常排序）
uj5u.com熱心網友回復：
不，您無法在 O(n) 時間和 O(1) 空間內實作這一點，因為如果可能的話，您可以實作僅使用 O(1) 空間的合并排序。只需拆分奇數和偶數索引即可將您的值分成兩半。
您可以在此問題中閱讀有關為什么合并排序需要至少 O(n) 空間的資訊： 合并排序時間和空間復雜度
uj5u.com熱心網友回復：
我認為您可以獲得的最佳性能是O(1) - spaceand O(n log n) - time。這是就地合并排序。
public final class InPlaceMergeSort {
public static void sortAsc(int[] arr) {
sortAsc(arr, 0, arr.length - 1);
}
private static void sortAsc(int[] arr, int lo, int hi) {
if (hi > lo) {
int mid = lo (hi - lo) / 2;
sortAsc(arr, lo, mid);
sortAsc(arr, mid 1, hi);
merge(arr, lo, mid, hi);
}
}
private static void merge(int[] arr, int lo, int mid, int hi) {
if (arr[mid] > arr[mid 1]) {
for (int i = lo, j = mid, k = mid 1; i <= j && k <= hi; i ) {
if (arr[i] > arr[k]) {
rotateRight(arr, i, k );
j ;
}
}
}
}
private static void rotateRight(int[] arr, int lo, int hi) {
int tmp = arr[hi];
if (hi - lo >= 0)
System.arraycopy(arr, lo, arr, lo 1, hi - lo);
arr[lo] = tmp;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/415932.html
標籤：
上一篇：python中的演算法操作排列：測驗函式執行的不同順序
下一篇：在c中找到一列二維陣列的最大和