一、算法稳定性

1.稳定： 插入、归并、基数、冒泡
2.不稳定： 选择、希尔、堆、快速

二、算法思想

1.直接插入排序

思想： 将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录+1的有序表

时间复杂度：

T=O（n^2)

例题：

49 38 65 97 76 13 27 49*
初始关键字：[49] 38 65 97 76 13 27 49*
i=2: [38 49] 65 97 76 13 27 49*
i=3: [38 49 65] 97 76 13 27 49*
i=4:[38 49 65 97] 76 13 27 49*
i=5:[38 49 65 76 97] 13 27 49*
i=6:[13 38 49 65 76 97] 27 49*
i=7:[13 27 38 49 65 76 97] 49*
i=8:[13 27 38 49 49* 65 76 97]

2.希尔排序

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

时间复杂度：
平均：T=O（ n*log2n）与增量有关 O（nlogn）～O（n2）

例图：

49 38 65 97 76 13 27 49*（增量选择 4 2 1）
增量4：49 13 27 49* 76 38 65 97
（a[1],a[5]),(a[2],a[6]),(a[3],a[7]),(a[4],a[8])排序

增量2：13 27 49*49 38 65 76 91
（a[1],a[5],a[2],a[6]),(a[3],a[7],a[4],a[8])排序

增量1：13 27 38 49 49* 65 76 97
（a[1],a[5],a[2],a[6],a[3],a[7],a[4],a[8])排序

3.冒泡排序

思想： 将第一个记录和第二个记录对比，若为逆序则交换位置，比较第二个值和第三个记录的值，依此类推，直至第n-1个值和第n个值进行比较位置，此时为第一次起泡排序，其结果值得最大值被安置在最后一个记录的位置上，然后进行第二次起泡排序，对前n-1个记录进行同样操作，直至在一次起泡排序过程中没有交换记录的操作。
时间复杂度：

T=(O（n^2))

例题：

49 38 65 97 76 13 27 49*
i=1:38 49 65 76 13 27 49* 97
(49>38交换位置，49<65，比较49后面的值,65<97比较65后面的值，
97>76交换位置，97>13交换位置，97>27交换位置,97>49*，交换位置）
i=2:38 49 65 13 27 49* 76 97
i=3:38 49 13 27 49* 65 76 97
i=4:38 13 27 49 49* 65 76 97
i=5:13 27 38 49 49* 65 76 97
i=6:13 27 38 49 49* 65 76 97

4.快速排序

思想： 通过一趟排序把待排记录分割成两部分，其中一部分记录的关键字均比另一部分记录小，则分别对这两记录进行排序。

简而言之：两个指针low、hight,第一个设为枢纽p，从high所指位置向前搜索出第一个小于p的值，交换位置，从low往后找到奥第一个小于p的值，交换位置，直至low=high。依此类推

时间复杂度：

T=O(n*log2n)

例题：
在这里插入图片描述

5.简单选择排序

思想： 第一次循环，遍历数组找出数组中最小的数字，放入a[0]，第二次循环，找出剩下数组中最小的数字放入a[1]一次类推。

时间复杂度： `

最小值：T=（0），最大值T=（3（n-1))

例题：

49 38 65 97 76 13 27 49*
i=1:[13] 49 38 65 97 76 27 49*
i=2:[13 27] 49 38 65 97 76 49*
i=3:[13 27 38] 49 65 97 76 49*
i=4:[13 27 38 49] 65 97 76 49*
i=5:[13 27 38 49* 49] 65 97 76 
i=6:[13 27 38 49* 49 65] 97 76 
i=7:[13 27 38 49* 49 65 76] 97
i=8:[13 27 38 49* 49 65 76 97]