-2.1 Elementary Sorts

Elementary Sorts

这一节讲的是一些基础的排序算法，包括选择排序，插入排序，希尔排序
这是这一章里面一个实现一种排序算法的类的模板API：

Selection Sort

定义:First, find the smallest item in the array and exchange it with the first entry (itself if the first entry is already the smallest). Then, find the next smallest item and exchange it with the second entry. Continue in this way until the entire array is sorted. This method is called selection sort because it works by repeatedly selecting the smallest remaining item.

实现:

Insertion Sort

定义:
The algorithm that people often use to sort bridge hands is to consider the cards one at a time, inserting each into its proper place among those already considered (keeping them sorted). In a computer implementation, we need to make
space to insert the current item by moving larger items one position to the right, before inserting the current item into the vacated position.

实现:

Shell Sort

定义:
The idea is to rearrange the array to give it the property that taking every hth entry(starting anywhere) yields a sorted subsequence. Such an array is said to be h-sorted. Put another way, an h-sorted array is h independent sorted subsequences, interleaved together. By h-sorting for some large values of h, we can move items in the array
long distances and thus make it easier to h-sort for smaller values of h. Using such a procedure for any sequence of values of h that ends in 1 will produce a sorted array
主要是定义一个H序列(如何产生没有一个固定的结论)，针对每个H序列使用插入排序(以H为步长,相当于对插入排序步长为1做出了对应的优化)

实现: