（转载请注明出处）

了解并掌握排序的概念，并熟悉常见的几种排序算法；

掌握常见的几种排序算法的基本思想方法；

对问题实例运用不同的排序算法进行求解，并能比较不同方法的效率好坏和适用的应用场景；

基本操作：

a. 将序列分解,将n个元素组成的数组b，以b[p]为基准元素，划分成三段：b[0:p-1],b[p],b[p+1:n].使得b[0:p-1]中的任何一个元素小于等于b[p]，b[p+1:n]中任何一个元素大于等于b[p].

b. 通过递归调用快速排序算法分别对b[0:p-1],b[p+1:n]进行排序。

c. 进行合并，此时每个序列都已是排好的序后，所以不执行任何的计算b就已排好序。

基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

性质：时间复杂度=O(nlogn) ,不稳定排序算法。

eg:(以最后一个元素为基准)

3 1 4 1 5 9 2 6 5 3 5 8 9

3 1 4 1 5 8 2 6 5 3 5 9 9

3 1 4 1 5 3 2 6 5 8 5

3 1 4 1 5 3 2 5 6 8 5

3 1 4 1 5 3 2 5 5 8 6

3 1 4 1 2 3 5 5 5 6 8

3 1 4 1 2 3 5 5 5

2 1 4 1 3 3

2 1 1 4 3 3

2 1 1 3 3 4

1 2 1

1 1 2

1 1 2 3 3 4 5 5 5 6 8 9 9

基本操作：

a. 先将序列中每一个元素分成一个序列。

b. 再依次两两比较两个序列头部元素的大小，将小元素放入放入两个元素组成的新序列中。

c. 重复上述步骤，直至成为一个序列。

基本思想：归并合并法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

性质：时间复杂度=O(nlogn) ,稳定排序算法。

eg:

3 1 4 1 5 9 2 6 5 3 5 8 9

1 3 1 4 5 9 2 6 3 5 5 8 9

1 1 3 4 2 5 6 9 3 5 5 8 9

1 1 2 3 4 5 6 9 3 5 5 8 9

1 1 2 3 3 4 5 5 5 6 8 9 9

基本操作：

a. 它重复地走访过要排序的元素列，依次比较两个相邻的元素，每次将大的元素放后面。

b. 走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。（最多进行n-1趟）

基本思想：它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

性质：时间复杂度= O(n^2) ,稳定排序算法。

eg:

3 1 4 1 5 9 2 6 5 3 5 8 9

1 3 1 4 5 2 6 5 3 5 8 9 9

1 1 3 4 2 5 5 3 5 6 8 9

1 1 3 2 4 5 3 5 5 6 8

1 1 2 3 4 3 5 5 5 6

1 1 2 3 3 4 5 5 5

1 1 2 3 3 4 5 5 5

1 1 2 3 3 4 5 5 5 6 8 9 9

基本操作：

a. 首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换。

b. 再通过n-2次比较，从剩余的n-1次个记录中找出关键字次小的记录，将它再与第二个记录交换。

c. 重复上述操作，共进行n-1趟排序后，排序结束。

基本思想：在待排序的数据中找出最大（小）的元素放在其最终的位置。

性质：时间复杂度 = O（n²），不稳定排序算法。

3 1 4 1 5 9 2 6 5 3 5 8 9

1 3 4 1 5 9 2 6 5 3 5 8 9

1 4 3 5 9 2 6 5 3 5 8 9

2 3 5 9 4 6 5 3 5 8 9

3 5 9 4 6 5 3 5 8 9

9 4 6 5 5 5 8 9

4 9 6 5 5 5 8 9

5 6 9 5 5 8 9

5 9 6 5 8 9

5 6 9 8 9

6 9 8 9

8 9 9

9 9

9

1 1 2 3 3 4 5 5 5 6 8 9 9

基本操作：

a. 先插入第一个元素。

b. 插入第二个元素，并于第一个元素相比较，如果小于第一个元素，则插在第一个元素之前，反之则插在第一个元素的后面。

c. 按照b步骤依次插入全部元素，排序完成。

基本思想：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

性质：时间复杂度=O(n^2)，是稳定排序算法。

eg:

3 1 4 1 5 9 2 6 5 3 5 8 9

3

1 3

1 3 4

1 1 3 4

1 1 3 4 5

1 1 3 4 5 9

1 1 2 3 4 5 9

1 1 2 3 4 5 6 9

1 1 2 3 4 5 5 6 9

1 1 2 3 3 4 5 5 6 9

1 1 2 3 3 4 5 5 5 6 9

1 1 2 3 3 4 5 5 5 6 8 9

1 1 2 3 3 4 5 5 5 6 8 9 9

基本操作：

a. 确定一个增量逐段分割，将相隔某个增量dk的记录组成一个子序列。

b. 让增量dk逐渐缩短，知道dk=1为止。

基本思想：先将整个待排序列分割成若干个子序列，分别进行直接插入排序，待将整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

性质：时间复杂度=O(n^(1.3–2)),不稳定算法。

eg:

3 1 4 1 5 9 2 6 5 3 5 8 9

3 5 9 增量为5

1 2 8 4 6 9 1 5 3 5

3 1 4 1 3 5 2 6 5 5 9 8 9

1 2 3 5 9 增量为3

1 3 6 9

4 5 5 8

1 1 4 2 3 5 3 6 5 5 9 8 9

1 1 2 3 3 4 5 5 5 6 8 9 9 增量为1

小结：

1.只有快速排序和归并排序空间复杂度要远高于其它排序算法，因为只有这两种排序产生了新的序列，需要分配新的储存空间。

2.不同的排序方法适用的场景，而且有些有相似的地方。如当数组元素基本有序时，快速排序将没有任何优势，基本退化为冒泡排序，可在选取基准元素时选取中间值进行优化。希尔排序就是在插入排序中增加了一个变量。冒泡排序和简单选择排序区别在于，冒泡排序每次找出最大元素时，元素之间要相互交换，而选择排序直接找出最小元素，不进行元素之间的交换。

3.以上排序，只有归并排序是外部排序。选择排序，快速排序，冒泡排序，插入排序，希尔排序都是内部排序。

以下是用C写的快速排序 #include

void quickSort(int arr[], int low, int high)

{

}

int main() {

}