資料結構 -- 排序與搜尋
資料結構簡介陣列排序與搜尋鍊節串列雜湊表二元樹紅黑樹派氏樹多元樹訊息相關網站參考文獻最新修改簡體版English |
範例：泡沫排序法class BobbleSort { public static void main(String[] args) { int a[] = {6, 3, 1, 9, 2}; print(a); sort(a); print(a); } public static void sort(int a[]) { for (int i=0; i<a.length; i++) for (int j=i+1; j<a.length; j++) { if (a[i] > a[j]) { int t = a[i]; a[i] = a[j]; a[j] = t; } } } public static void print(int a[]) { for (int i=0; i<a.length; i++) System.out.print(a[i]+" "); System.out.println(); } } 範例：循序搜尋class StrList { String a[] = new String[10]; int size = 0; public static void main(String[] args) { StrList list = new StrList(); list.append("John"); System.out.println(list.toString()); list.append("Mary"); System.out.println(list.toString()); list.append("George"); System.out.println(list.toString()); list.append("Nancy"); System.out.println(list.toString()); list.remove(2); System.out.println(list.toString()); int i = list.find("Nancy"); System.out.println("i="+i); } void append(String x) { a[size] = x; size ++; } void remove(int k) { for (int i=k; i<size; i++) a[i] = a[i+1]; size--; } int find(String x) { for (int i=0; i<size; i++) if (x.equals(a[i])) return i; return -1; } public String toString() { String rzStr = ""; for (int i=0; i<size; i++) { rzStr += a[i]+" "; } return rzStr; } } 範例：排序後二分搜尋 1class SortArray { public static void main(String[] args) { int a[] = new int[6]; int size = 0; size = insert(a, size, 3); print(a, size); size = insert(a, size, 5); print(a, size); size = insert(a, size, 2); print(a, size); size = insert(a, size, 4); print(a, size); size = insert(a, size, 1); print(a, size); size = delete(a, size, 2); print(a, size); size = delete(a, size, 4); print(a, size); int i = find(a, size, 3); System.out.println("i="+i); int j = find(a, size, 2); System.out.println("j="+j); } public static void print(int a[], int size) { for (int i=0; i<size; i++) System.out.print(a[i]+" "); System.out.println(); } public static int seek(int a[], int size, int x) { for (int i=0; i<size; i++) if (a[i] >= x) return i; return size; } public static int bsearch(int a[], int from, int to, int x) { int mid = (from+to)/2; while (to > from) { if (a[mid] < x) bsearch(a, from, mid-1); if (a[mid] > x) bsearch(a, mid+1, to); } public static int find(int a[], int size, int x) { int i = seek(a, size, x); if (a[i] == x) return i; else return -1; } public static int insert(int a[], int size, int x) { int k = seek(a, size, x); if (a[k] == x) return size; else { for (int i=size; i>=k; i--) a[i+1] = a[i]; a[k] = x; return size+1; } } public static int delete(int a[], int size, int x) { int k = seek(a, size, x); if (a[k] == x) { for (int i=k; i<size; i++) a[i] = a[i+1]; return size-1; } else return size; } } 範例：排序後搜尋 1class SortArray { public static void main(String[] args) { int a[] = new int[6]; int size = 0; size = insert(a, size, 3); print(a, size); size = insert(a, size, 5); print(a, size); size = insert(a, size, 2); print(a, size); size = insert(a, size, 4); print(a, size); size = insert(a, size, 1); print(a, size); size = delete(a, size, 2); print(a, size); size = delete(a, size, 4); print(a, size); int i = find(a, size, 3); System.out.println("i="+i); int j = find(a, size, 2); System.out.println("j="+j); } public static void print(int a[], int size) { for (int i=0; i<size; i++) System.out.print(a[i]+" "); System.out.println(); } public static int seek(int a[], int size, int x) { return bsearch(a, 0, size, x); } public static int bsearch(int a[], int from, int to, int x) { int mid = (from+to)/2; while (to >= from) { mid = (from+to)/2; if (x == a[mid]) return mid; if (x < a[mid]) to = mid-1; if (x > a[mid]) from = mid+1; } return mid; } public static int find(int a[], int size, int x) { int i = seek(a, size, x); if (a[i] == x) return i; else return -1; } public static int insert(int a[], int size, int x) { int k = seek(a, size, x); if (a[k] == x) return size; else { for (int i=size; i>=k; i--) a[i+1] = a[i]; a[k] = x; return size+1; } } public static int delete(int a[], int size, int x) { int k = seek(a, size, x); if (a[k] == x) { for (int i=k; i<size; i++) a[i] = a[i+1]; return size-1; } else return size; } } 範例：排序後搜尋 2class SortArray { public static void main(String[] args) { int a[] = new int[6]; int size = 0; size = insert(a, size, 3); print(a, size); size = insert(a, size, 5); print(a, size); size = insert(a, size, 2); print(a, size); size = insert(a, size, 4); print(a, size); size = insert(a, size, 1); print(a, size); size = delete(a, size, 2); print(a, size); size = delete(a, size, 4); print(a, size); int i = find(a, size, 3); System.out.println("i="+i); int j = find(a, size, 2); System.out.println("j="+j); } public static void print(int a[], int size) { for (int i=0; i<size; i++) System.out.print(a[i]+" "); System.out.println(); } public static int seek(int a[], int size, int x) { return bsearch(a, 0, size, x); } public static int bsearch(int a[], int from, int to, int x) { int mid = (from+to)/2; // System.out.println("from="+from+" to="+to+" mid="+mid); if (to <= from) return from; if (x == a[mid]) return mid; else if (x > a[mid]) return bsearch(a, mid+1, to, x); else return bsearch(a, from, mid-1, x); } public static int find(int a[], int size, int x) { int i = seek(a, size, x); if (a[i] == x) return i; else return -1; } public static int insert(int a[], int size, int x) { int k = seek(a, size, x); if (a[k] == x) return size; else { for (int i=size; i>=k; i--) a[i+1] = a[i]; a[k] = x; return size+1; } } public static int delete(int a[], int size, int x) { int k = seek(a, size, x); if (a[k] == x) { for (int i=k; i<size; i++) a[i] = a[i+1]; return size-1; } else return size; } } |
page revision: 4, last edited: 05 Nov 2010 08:45
Post preview:
Close preview