2011年1月9日 星期日

[ Data Structures with Java ] Section 5.6 : Generic Search/Sorting Algorithms

Preface : 
In Chapter 4, we introduce an integer version of selectionSort(). A generic version is more functional. It can order arrays of different types. For each pass, the integer version of the method uses the operator < to identify the index of the smallest element in the unsorted tail of the list. The generic version specifies that the object type must implement the Comparable interface and uses compareTo() for the ordering relation. With minor adjustment to the code, we can implement a generic version of selectionSort(). Note the generic tag in the headers. You can find a listing of the method in Array class. 

Generic selection sort : 

- Array.java 代碼 (Partly)
  1. void selectionSort(T[] arr){  
  2.     int smallIndex;  
  3.     int pass, n=arr.length;  
  4.     T temp;  
  5.     for(pass=0; pass<(n-1); pass++) {  
  6.         smallIndex = pass;  
  7.         for(int j=(pass+1); j
  8.             if(arr[smallIndex].compareTo(arr[j])>0) {  
  9.                 smallIndex = j;  
  10.             }  
  11.         }  
  12.         if(smallIndex!=pass) {  
  13.             temp = arr[pass];  
  14.             arr[pass] = arr[smallIndex];  
  15.             arr[smallIndex] = temp;  
  16.         }  
  17.     }  
  18. }  
  19.   
  20. public static void main(String args[]){  
  21.     String[] strArr = {"red""green""blue"};  
  22.     Integer[] intArr = {40705030};  
  23.     Arrays.selectionSort(strArr);  
  24.     System.out.println("Sorted strings: "+  
  25.             Arrays.toString(strArr));  
  26.     Arrays.selectionSort(intArr);  
  27.     System.out.println("Sorted integers: "+  
  28.             Arrays.toString(intArr));  
  29. }  


Output :
Sorted strings: [blue, green, red]
Sorted integers: [30, 40, 50, 70]

Generic Binary Search Method : 
The binary search may be used with any ordered array. Its implementation uses equality to detect a match and either less than (<) or greater than (>) to locate the sublist for the next iteration. A generic version of binSearch() requires that the object type implement the Comparable interface. You can find a listing of the method in the Arrays class. 

Generic binSearch() : 

- Arrays.java 代碼 (partly)
  1. int binSearch(T[] arr, int first, int last, T target) {  
  2.     int mid;  
  3.     while(first
  4.         mid = (first+last)/2;  
  5.         if(arr[mid].compareTo(target)==0) {  
  6.             //System.out.println("Target="+target+",Object="+arr[mid]+", mid="+mid);  
  7.             return mid;  
  8.         } else if(arr[mid].compareTo(target)>0){  
  9.             last = mid;  
  10.             continue;  
  11.         } else {  
  12.             first = mid+1;  
  13.             continue;  
  14.         }  
  15.     }  
  16.     return -1;  
  17. }  
  18. public static void main(String args[]){  
  19.     String[] strArr = {"red""green""blue""orange""tan"};  
  20.     int index;  
  21.     Arrays.selectionSort(strArr);  
  22.     System.out.println("Sorted: "+Arrays.toString(strArr));  
  23.     index = Arrays.binSearch(strArr, 0, strArr.length, "tan");  
  24.     System.out.println("Find in "+index);  
  25. }  


Output :
Sorted: [blue, green, orange, red, tan]
Find in 4

補充說明 : 
* JavaWorld@TW : Generics 簡介 [精華]

沒有留言:

張貼留言

[Git 常見問題] error: The following untracked working tree files would be overwritten by merge

  Source From  Here 方案1: // x -----删除忽略文件已经对 git 来说不识别的文件 // d -----删除未被添加到 git 的路径中的文件 // f -----强制运行 #   git clean -d -fx 方案2: 今天在服务器上  gi...