"Chapter-3 分治策略1：快速排序简介及实现"

Section 3 of the chapter introduces the divide and conquer strategy, which involves dividing an array into two sub-arrays, sorting the sub-arrays, and then merging them back together. The example used to illustrate this strategy is the quicksort algorithm, known for its popularity and efficiency with an average time complexity of Θ(nlogn). Quicksort is preferred over merge sort as it sorts the array in place without requiring additional storage space, in contrast to merge sort which requires Θ(n) additional space. The algorithm was developed by Charles A. R. Hoare in 1960 and has since become one of the most widely used algorithms worldwide. Hoare's contributions to the field of computer science and education were recognized with the Turing Award in 1980 and a knighthood from the British monarchy in 2000. In the context of quicksort, an example is provided to demonstrate the sorting of the array A[1...8]={4, 6, 3, 1, 8, 7, 2, 5} in non-decreasing order. The algorithm begins by splitting the array based on a pivot element - the first element in this case. The array is divided into two sub-arrays such that elements to the left of the pivot are less than or equal to the pivot, and elements to the right are greater than or equal to the pivot. The same operation is then applied to the left and right sub-arrays. Overall, the chapter emphasizes the effectiveness and practicality of the divide and conquer strategy, especially in the context of the quicksort algorithm. It highlights the significant contributions of Charles A. R. Hoare to the field of computer science and the widespread use of the quicksort algorithm. Additionally, it provides a clear example of the application of the divide and conquer strategy in sorting an array using the quicksort algorithm.