【文章內(nèi)容簡介】 Java More Java Examples Normal Distribution Random number 交通大學資訊工程學系 蔡文能 第 27頁 Java More Java Examples Insertion Sort public class InsSort { public static void sort(double[ ] nums) { for(int i = 1。 i 。 i++) { double tmp = nums[i]。 /* we want to put this in proper position */ k = i – 1。 while ((k=0) nums[k] tmp ) { /* smaller than me */ nums[k+1] = nums[k])。 /* move it down */ k。 } nums[k+1] = tmp。 /* copy it into correct position */ } } } 交通大學資訊工程學系 蔡文能 第 28頁 Java More Java Examples Test the Insertion Sort ? In separate file as previous example (Selection sort): public class SortNumber { public static void main (String[ ] args) { double[ ] nums = new double[10]。 //Create an array to hold numbers for(int i = 0。 i 。 i++) //Generate random numbers nums[i] = ( )*100。 (nums)。 //Sort them using insertion sort for (int j = 0。 j 。 j++) //Print them out (nums [j] )。 } } 交通大學資訊工程學系 蔡文能 第 29頁 Java More Java Examples Bubble Sort public class BubSort { public static void sort(double[ ] nums) { for(int i = 。 i =0。 i) { int flag = 0。 /* Assume no exchange */ for(k=0。 k = i。 ++k) { /* walk through all every pass */ if ( nums[k] nums[k+1] ) { /* incorrect order */ double tmp=nums[k]。 nums[k]=nums[k+1]。 nums[k+1]=tmp。 ++flag。 } } if(flag == 0) break。 /* no need to do next pass */ } } } 交通大學資訊工程學系 蔡文能 第 30頁 Java More Java Examples Algorithm quick_sort(array A, from, to) Input: from pointer to the starting position of array A to pointer to the end position of array A Output: sorted array: A’ 1. Choose any one element as the pivot。 2. Find the first element a = A[i] larger than or equal to pivot from A[from] to A[to]。 3. Find the first element b = A[j] smaller than or equal to pivot from A[to] to A[from]。 4. If i j then exchange a and b。 5. Repeat step from 2 to 4 until j = i。 6. If from j then recursive call quick_sort(A, from, j)。 7. If i to then recursive call quick_sort(A, i, to)。 Quick Sort (1/6) 交通大學資訊工程學系 蔡文能 第 31頁 Java More Java Examples ? Quick sort main idea: 1st step: 3 1 6 5 4 8 10 7 2nd step: 3 2 1 5 8 9 10 7 3rd step: 3 2 1 4 5 6 8 9 10 7 Choose 5 as pivot from to 2 9 6 4 Smaller than any integer right to 5 greater than any integer left to 5 i j Quick Sort (2/6) 交通大學資訊工程學系 蔡文能 第 32頁 Java More Java Examples ? Quick sort 4th step: 2 4 5 6 10 9 5th step: 1 2 3 4 5 pivot from to 3 1 8 7 5 6 7 8 10 9 6th step: pivot from to 7 8 10 9 7th step: 9 10 8th step: Quick Sort (3/6) 交通大學資訊工程學系 蔡文能 第 33頁 Java More Java Examples public class QuickSorter { public static void sort (int[ ] a, int from, int to) { if ((a == null) || ( 2)) return。 int i = from, j = to。 int pivot = a[(from + to)/2]。 do { while ((i to) (a[i] pivot)) i++。 while ((j from) (a[j] = pivot)) j。 if (i j) { int tmp =a[i]。 a [i] = a[j]。 a[j] = tmp。} i++。 j。 }while (i = j)。 if (from j) sort(a, from, j)。 if (i to) sort(a, i, to)。 } } Quick Sort (4/6) 交通大學資訊工程學系 蔡文能 第 34頁 Java More Java Examples 14 3, 4, 6, 1, 10, 9, 5, 20, 19, 14 1, 12, 2, 15, 21, 13, 18, 17, 8, 16, 3, 4, 6, 1, 10, 9, 5, 8, 19, 1, 12, 2, 15, 21, 13, 18, 17, ,16, 3, 4, 6, 1, 10, 9, 5, 8, 13 , 1, 12, 2, 15, 21, 19, 18, 17, 20, 16, i j 3, 4, 6, 1, 10, 9, 5, 8, 13 , 1, 12, 2 i j Quick Sort (5/6) 3, 4, 6, 1, 10, 9, 5, 20, 19, 14, 12, 2, 15, 21, 13, 18, 17, 8, 16, 1 j i 20, 14 i j 3, 4, 6, 1, 10, 9, 5, 8, 13 , 1, 12, 2, 14, 21, 19, 18, 17, 20, 16, 15 14 交通大學資訊工程學系 蔡文能 第 35頁 Java More Java Example