C14-排序讲解.ppt

advanced sorting concepts;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;11-1 General sort concept;11-2 Insertion sorts; Straight insertion sorts; Shell sorts;77; algorithm Shellsort; insertion sort algorithm efficiency;11-3 Selection sorts; Straight selection sort example ; selection sort algorithm efficiency;11-4 Exchange sorts; Bubble sort example ; Quick sorts;Find the median value of an array, sortData[left…right], and place it in the location sortData[left].; Quick sort pivot;An array ,list [left…right] is sorted using recursion. Pre list is an array of data to be sorted left and right identify the first and last elements of the list, respectively Post list is sorted ; Exchange Sorts Algorithm efficiency;Summary of this chapter;Summary of this chapter (Continue);Two methods of exchange sorting were discussed in this chapter: bubble sort and quick sort. In the bubble sort, the list at any moment is divided into two sublists: sorted and unsorted. In each pass, the smallest element is bubble up from the unsorted sublist and moved to the sorted sublist. The quick sort is the new version of exchange sort in which the list is continuously divided into smallest sublists and exchange takes place between elements that are out of order. Each pass of the quick sort selects a pivot and divides list into three groups: a partition of elements whose key is less than the pivot element that is place in its ultimate correct position, and a partition of elements greater than or equal to the pivot’s key. The sorting then continues by quick sorting the left partition followed by quick sorting the right partition. The efficiency of straight insertion, straight se