Monday, May 17, 2004
Sorts總整理2--Merge Sort
Merge Sort 的演算法和程式碼
《Merge Sort》
Algorithm :
Merge(A,p,q,r)
java code:整數排序
n1←q-p+1 n2←r-q △cerate arrays L(1..n1+1) and R(1..n2+1) for i←1 to n1 do L[i]←A[p+i-1] for j←1 to n2 do R[j]←A[q+j] L[n1+1]←∞ R[n2+1]←∞ i←1 j←1 for k←p to r do if L[i]≦R[j] then A[k]←L[i] i←i+1 else A[k]←R[j] j←j+1Merge-Sort(A,p,r)
if p<r then q←└(p+r)/2┘ Merge-Sort(A,p,q) Merge-Sort(A,q+1,r) Merge(A,p,q,r)
void mergeSort(int[] Array, int p, int r){ if( p < r ){ int q = ( p + r )/2; mergeSort(Array, p, q); mergeSort(Array, q + 1, r); merge(Array, p, q, r); } } void merge(int[] Array, int p, int q, int r){ int n1 = q - p + 1; int n2 = r - q; int[] L = new int[n1 + 1], R = new int[n2 + 1]; int i, j; for(i = 0; i < n1; i++){ L[i] = Array[p + i]; } for(j = 0; j < n2; j++){ R[j] = Array[q + j + 1]; } L[n1] = R[n2] = Integer.MAX_VALUE; i = j = 0; for(int k = p; k <= r; k++){ if(L[i] <= R[j]){ Array[k] = L[i]; i++; } else{ Array[k] = R[j]; j++; } } }java code:字串排序
void mergeSort(String[] Array){ mergeSort(Array,0,Array.length-1); } void mergeSort(String[] Array, int p, int r) { if (p < r) { int q = (p + r) / 2; mergeSort(Array, p, q); mergeSort(Array, q + 1, r); merge(Array, p, q, r); } } void merge(String[] Array, int p, int q, int r) { int n1 = q - p + 1; int n2 = r - q; String[] L = new String[n1 + 1]; String[] R = new String[n2 + 1]; int i; int j; for (i = 0; i < n1; i++) { L[i] = Array[p + i].name; } for (j = 0; j < n2; j++) { R[j] = Array[q + j + 1].name; } L[n1] = R[n2] = new String(new char[]{Character.MAX_VALUE}); i = j = 0; for (int k = p; k <= r; k++) { if (L[i].compareTo(R[j])<= 0) { Array[k].name = L[i]; i++; } else { Array[k].name = R[j]; j++; } } }由 shumi 發表於 May 17, 2004 12:01 AM