[工學(xué)]9抽象數(shù)據(jù)類型和算法-在線瀏覽
2025-03-08 10:50本頁面
【正文】 While (more items) Get next item Print Item Know Length return length 2022/2/16 Fundamentals of Computer Science Hai Mo Page 29 Sorted Lists From the application view, how do the sorted an unsorted list differ? The deposition of which algorithm steps must be different? List,Stack,Queue,Array,link List stack queue Arraybased implementation Linkedbased implementation 2022/2/16 Fundamentals of Computer Science Hai Mo Page 31 Sorting ? Selection Sort(選擇排序 ) 1. Find the name that es first in the alphabet, and write it on a second sheet of paper. 2. Cross out the name on the original list. 3. Continue this cycle until all the names on the original list have been crossed out and written onto the second list, at which point the second list is sorted. 2022/2/16 Fundamentals of Computer Science Hai Mo Page 32 Selection Sort 2022/2/16 Fundamentals of Computer Science Hai Mo Page 33 Selection Sort Selection Sort 2022/2/16 Fundamentals of Computer Science Hai Mo Page 34 Question ? How many parisons are needed to finish a selection sort for a list of n elements? 2022/2/16 Fundamentals of Computer Science Hai Mo Page 35 2022/2/16 Fundamentals of Computer Science Hai Mo Page 36 Sorting ? Bubble Sort(冒泡排序 ) － Starting with the last element of a list, we pare successive pairs of elements, swapping whenever the bottom element of the pair is smaller than the one above it 2022/2/16 Fundamentals of Computer Science Hai Mo Page 37 Bubble Sort 2022/2/16 Fundamentals of Computer Science Hai Mo Page 38 2022/2/16 Fundamentals of Computer Science Hai Mo Page 39 Sorting ? Quicksort － Be based on the idea that it is faster and easier to sort two small lists than one larger one. － The basic strategy of this sort is to divide and conquer. 2022/2/16 Fundamentals of Computer Science Hai Mo Page 40 Quicksort Quicksort If (there is more than one item in list[first]..list[last]) Select splitVal Split the list so that list[first]..list[splitPoint1] = splitVal list[splitPoint] = splitVal list[splitPoint+1]..list[last] splitVal Quicksort the left half Quicksort the right half 2022/2/16 Fundamentals of Computer Science Hai Mo Page 41 Quicksort Split 2022/2/16 Fundamentals of Computer Science Hai Mo Page 42 Split Set left to first + 1 Set right to last Do Increment left until list[left] splitVal OR left right Decrement right until list[right] splitVal OR left right If (left right) Swap list[left] and list[right] While (left = right) Set splitPoint to right Swap list[first] and list[right] 2022/2/16 Fundamentals of Computer Science Hai Mo Page 43 Splitting algorithm a Initialization 9 20 6 10 14 8 60 11 [first] [left] [right] b Increment left until list[left] splitVal or leftright 9 20 6 10 14 8 60 11 [first] [left] [right] c Decrement right until list[right] =splitVal or leftright 9 20 6 10 14 8 60 11 [fi
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1