程式设计与算法基础.pptVIP

程序设计与算法基础(3) 潘爱民 2006/10/9 Outline Sorting algorithms Complexity analysis Sorting The idea is simple, make a serial of elements sorted according to some criteria of order Rearrange n elements into ascending order. 7, 3, 6, 2, 1 ? 1, 2, 3, 6, 7 The comparison method is defined first The number of comparison is defined as the complexity of a sorting algorithm Sometimes we also consider the number of data movements About sorting Sorting is a fundamental problem Why sorting It is necessary to efficiently process the data Algorithms often use sorting as a key subroutine For complexity analysis Sorting algorithms Insertion sort Selection sort Bubble sort Shell sort Heap sort Quick sort Merge sort Insertion Sort n = 1 ? already sorted. So, assume n 1. If a[0] … a[i] are sorted, a[i+1] is inserted at the proper position To find the position, compare a[i+1] with a[i]…a[0] Move the elements greater than a[i+1] backward by one positon Until a[n-1] is inserted into the sorted a[0]…a[n-2] Insertion Sort void InsertionSort(T data[], int n) { for(int i =1, j; i n; i ++) { T tmp = data[i]; for( j= i; j 0 tmp data[j-1]; j--) data[j] = data[j-1]; data[j] = tmp; } } Complexity analysis for insertion sort The number of comparisons Cbest = n-1 Cworst = 1+2+…+(n-1) = n(n-1)/2 Caverage = ?[(1+2+…+i)/i] = ?(i+1)/2=(n2+n-2)/4 The number of data movements Mbest = 2(n-1) Mworst = 1+2+…+(n-1) + 2(n-1) = (n2+3n-4)/2 Maverage = ?[(1+2+…+i-1)/i + 2] = ?(i+3)/2=(n2+5n-6)/4 Selection Sort Idea: find a misplaced element first and putting it in its final place Find the smallest element and exchange it with a[0] Find the smallest element among a[1]…a[n-1], and exchange it with a[1] … Until the smaller between a[n-2] and a[n-1] is selected and put at the right place Selection sort void SelectionSort(T data[], int n) { for(int i =0, j, least; i n-1; i++) { for( j = i+1, least = i; j n; j++) if (data[j] data[least]) least = j; swap(data[least], data[i]); } } Complexity a