集計ソート再帰版と非再帰版の実装(java)
115204 ワード
集計ソートの実装(java)
固定リンク:https://www.zybuluo.com/xujun94/note/424570
二分検索については、私のこのブログの二分検索に関するアルゴリズムの問題を参考にすることができます.
集計ソートについては、私のブログ集計ソート再帰版と非再帰版の実装(java)を参照してください.
クイックソートについては、私のブログを参考にしてください. 高速ソートに関するアルゴリズム問題(java)
転載は元のブログの住所を明記してください: http://write.blog.csdn.net/postedit/51292207
集計ソートとは集計ソートは、実際には2つのことをします. 「分解」--シーケンスを半分に分割します. 「連結」--分割されたシーケンスセグメントを2つ連結して並べ替えます.
まず分解がどのように実現されているかを見てみましょう.
次に合併はどのように実現されたのでしょうか.は1つの配列を初期化し、左右の配列の数を比較する、小さい数を中間配列 に格納する.さらに左右の配列の残りの数を中間配列 に格納.最後に、中間配列を元の配列 にコピーする
java 固定リンク:https://www.zybuluo.com/xujun94/note/424570
二分検索については、私のこのブログの二分検索に関するアルゴリズムの問題を参考にすることができます.
集計ソートについては、私のブログ集計ソート再帰版と非再帰版の実装(java)を参照してください.
クイックソートについては、私のブログを参考にしてください. 高速ソートに関するアルゴリズム問題(java)
転載は元のブログの住所を明記してください: http://write.blog.csdn.net/postedit/51292207
集計ソートとは
まず分解がどのように実現されているかを見てみましょう.
// ， left》=right if (left < right) { // center = (left + right) / 2; // mSort(k, 0, center); // mSort(k, center + 1, right); // merging(k, left, center, right); }
次に合併はどのように実現されたのでしょうか.
private static void merging(int[] k, int left, int center, int right) { int tempArr[] = new int[k.length];// // third int mid = center + 1; int third = left; int temp = left; while (left <= center && mid <= right) { // tempArr if (k[left] < k[mid]) { tempArr[third++] = k[left++]; } else { tempArr[third++] = k[mid++]; } }
// while (mid <= right) { tempArr[third++] = k[mid++]; }
while (left <= center) { tempArr[third++] = k[left++]; } // while (temp <= right) { k[temp] = tempArr[temp++]; } }
}
// package com.xujun.mergesort;
public class MergeSort {
static int[] a = new int[] { 20, 9, 3, 5, 26, 100, 8, -1, 7, 50, -5 };
public static void main(String[] args) { System.out.println("before sort"); ArrayUtils.printArray(a); mergeSort(a); System.out.println("after sort"); ArrayUtils.printArray(a);
}
private static void mergeSort(int[] k) { mSort(k, 0, k.length - 1); }
private static void mSort(int[] k, int left, int right) { int center // ， left》=right if (left < right) { // center = (left + right) / 2; // mSort(k, 0, center); // mSort(k, center + 1, right); // merging(k, left, center, right);
} }
private static void merging(int[] k, int left, int center, int right) { // int tempArr[] = new int[k.length]; // third int mid = center + 1; int third = left; int temp = left; while (left <= center && mid <= right) { // tempArr if (k[left] < k[mid]) { tempArr[third++] = k[left++]; } else { tempArr[third++] = k[mid++]; } }
// while (mid <= right) { tempArr[third++] = k[mid++]; }
while (left <= center) { tempArr[third++] = k[left++]; } // while (temp <= right) { k[temp] = tempArr[temp++]; } }
}
- 1 ， 2 。
- ， ，
// while (len <= t.length) { for (int i = 0; i + len <= t.length - 1; i += len * 2) { // System.out.println("len="+len); low = i; mid = i + len - 1; high = i + len * 2 - 1; if (high > t.length - 1) high = t.length - 1; merge(t, i, mid, high); }// len += len; } return true; }
：
package com.xujun.mergesort1;
public class MergeSort2 { /** * - * * @param <T> * @param t * @return */ public static <T extends Comparable> boolean mergeSortRecursive(T[] t) { if (t == null || t.length <= 1) return true;
MSortRecursive(t, 0, t.length - 1);
return true; }
/** * - * * @param <T> * @param t * @param low * @param high * @return */ private static <T extends Comparable> boolean MSortRecursive(T[] t, int low, int high) { if (t == null || t.length <= 1 || low == high) return true;
int mid = (low + high) / 2; MSortRecursive(t, low, mid); MSortRecursive(t, mid + 1, high); merge(t, low, mid, high);
return true; }
public static <T extends Comparable> boolean mergeSortNonRecursive(T[] t) { if (t == null || t.length <= 1) return true;
int len = 1; int low = 0; int mid; int high; // while (len <= t.length) { for (int i = 0; i + len <= t.length - 1; i += len * 2) { // System.out.println("len="+len); low = i; mid = i + len - 1; high = i + len * 2 - 1; if (high > t.length - 1) high = t.length - 1; merge(t, i, mid, high); }// len += len; } return true; }
/** * * * @param <T> * @param t * @param low * @param mid * @param high * @return */ private static <T extends Comparable> boolean merge(T[] t, int low, int mid, int high) { T[] s = t.clone();//
int i, j, k;// ，i t[low...mid]，j t[mid+1...high]，k s[low...high] for (i = low, j = mid + 1, k = low; i <= mid && j <= high; k++) { if (t[i].compareTo(t[j]) <= 0) { s[k] = t[i++]; } else { s[k] = t[j++]; } }
// s if (i <= mid) { for (; k <= high; k++) { s[k] = t[i++]; } } else { for (; k <= high; k++) { s[k] = s[j++]; } } for (int m = low; m <= high; m++) {// t[m] = s[m]; }
return true; }
public static void main(String[] args) { Integer[] arr = new Integer[] { 2, 3, 6, 8, 9, 2, 0, 1 }; long startTime = System.currentTimeMillis(); // mergeSortRecursive(arr); long endTime = System.currentTimeMillis(); // System.out.println(" ：" + (endTime - startTime)); for (int i : arr) { System.out.println(i); } startTime = System.currentTimeMillis(); // mergeSortNonRecursive(arr); endTime = System.currentTimeMillis(); // System.out.println(" ：" + (endTime - startTime)); for (int i : arr) { System.out.println(i); } }}
，
， （java）
： http://write.blog.csdn.net/postedit/51292207
： http://download.csdn.net/detail/gdutxiaoxu/9565965