C14-排序讲诉.ppt

advanced sorting concepts Vocabulary Sort (排序) Internal sort (内排序) External sort (外排序) Ascending order (升序) Descending order (降序) Insertion sort (插入排序) Straight insertion sort (直接插入排序) Shell sort (希尔排序) Selection sort (选择排序) Straight selection sort (直接选择排序) Heap sort (堆排序) Exchange sort (交换排序) Bubble sort (冒泡排序) Quick sort (快速排序) Stability (稳定性) Pass (一趟排序) Highlights in this chapter General sort concept Sort order Sort stability Sort efficiency passes Insertion sorts Selection sorts Exchange sorts 11-1 General sort concept Internal sort External sort Sort order Sort stability Sort efficiency passes 11-2 Insertion sorts Insertion sort: in each pass of an insertion sort, one or more pieces of data are inserted into their correct location in an order list. In this section we study two insertion sorts, the straight insertion sort and the shell sort. Straight insertion sorts In the straight insertion sort, the list at any moment is divided into two sublists: sorted and unsorted. In each pass, the first element of the unsort sublist is transferred to the sorted sublist by inserting it at the appropriate place. Shell sorts The shell sorts is an improve version of the straight insertion sort, in which diminishing partition are used to sort data. The segments in a shell sort: Diminishing increments in shell sort algorithm Shellsort insertion sort algorithm efficiency Straight insertion sort 11-3 Selection sorts Selection sort: In each pass of an selection sort, we select the smallest item of unsorted list and place it in the sorted list. In this section we study two selection sorts, the straight selection sort and the heap sort. Straight selection sorts In the straight selection sort, the list at any moment is divided into two sublists: sorted and unsorted. In each pass, we select the smallest element from the unsorted sublist and exchange it with the element at the beginning of the unsort data. selection sort algorithm e