一、插入排序
插入排序包括直接插入排序，折半插入排序、希尔排序。直接插入排序就是简单粗暴的插入，折半排序是利用了二分查找的插入排序，希尔排序是先局部后整体的插入排序。
其算法的主要思想就是每次将一个待排序的记录按其关键字大小插入到前面已经排好序的子序列，直到全部记录插入完成。
1.直接插入排序
①算法的执行过程：
对于待排序表L[1...n]，假设在某个状态下，待排序元素为L(i)，则L[1...i-1]为已经排好序的序列，L[i+1...n]为无序序列。
将L(i)依次与L(i-1)...L(1)相比较，找出L(i)在有序序列中要插入的位置k。
将L[k...i-1]中的所有元素依次后移一个位置。
将L(i)复制到L(k)i后移，重复2.直到有序序列长度为n
②算法执行过程可视化演示：
③算法代码：
void InsertSort(ElemType A[], int n){ for(int i = 2; i <= n; i++){ //默认首个元素为有序序列，将2~n位置的关键字依次插入 if(A[i] < A[i-1]){ //如果待插入元素小于有序序列最大元素，则需要插入 A[0] = A[i]; //A[0]为“哨兵”，用来存放待插入元素 for(int j = i-1; A[0] < A[j]; j--) //从后往前查找待插入的位置 A[j+1] = A[j]; //依次向后移动 A[j+1] = A[0]; //找到位置之后，将待排序元素插入有序序列 } } }
④性能分析：
1.空间效率：使用常数个辅助单元，空间复杂度为O(1)
2.时间效率：进行了n-1趟插入操作，每趟操作都分为比较和移动元素，所以与表的初始状态有关
最好情况下：表已经有序，只需比较不需移动元素，此时时间复杂度为O(n)；
最坏情况下：此时为逆序，比较次数为2+3+……+n，总的移动次数为(2+1)+(3+1)+……+(n+1)
平均情况下：出现概率随机，取最好和最坏的平均值，总的比较和移动次数约为(1/4)n2.所以插入排序算法的时间复杂度为O(n2)
3.稳定性： 稳定
4.适用性：适用于线性表为顺序存储或链式存储的情况。
2.折半插入排序
①算法的执行过程： 总体过程与上一个类似，只是在寻找插入位置的时候使用的二分查找算法
②算法执行过程可视化演示： 与上一个相同。
③算法代码：
void BinaryInsertSort(ElemType A[], int n){ int low, high, mid; for(int i = 2; i <= n; i++){ //默认首个元素为有序序列，将2~n位置的关键字依次插入 A[0] = A[i]; //A[0]为“哨兵”，用来存放待插入元素 low = 1, high = i-1; while(low <= high){ //low=high时表明查找到要插入的位置 mid = (low+high)/2; //为了保证稳定，相等的情况需要查找右半子表 if(A[mid] > A[0]) high = mid-1; //查找左半子表 else low = mid+1; //查找右半子表 } for(int j = i-1; j >= high+1; j--) //从后往前查找待插入的位置 A[j+1] = A[j]; //依次向后移动 A[high+1] = A[0]; //将待排序元素插入有序序列 } }
④性能分析：
1.空间效率：与直接插入排序相同空间复杂度为O(1)
2.时间效率：进行了n-1趟插入操作，每趟操作都分为比较和移动元素，比较操作与表的初始状态无关，为O(n log2n)，移动次数取决于初始状态，所以折半插入排序时间复杂度为O(n2)
3.稳定性： 不稳定
4.适用性：仅适用于线性表为顺序存储的情况。
3.希尔排序
希尔排序的由来：当待排序序列为基本有序时，插入排序复杂度可以提高至O(n)，所以我们可以让整体基本有序，也就是说部分有序，最后使用插入排序进行排序。由此得出希尔排序，也称缩小增量排序
①算法的执行过程：
希尔排序思想即先局部后整体，首先设置增量d，把待排序的表分为k个子表，对每个子表排序后，增量d变为原来的一半，直到减小为d=1.
此时的表已经基本有序，进行最后一趟排序之后得到有序序列，这里在每个子表中使用的排序算法仍是插入排序.
②算法执行过程演示：
③算法代码：
void ShellSort(ElemType A[], int n){ //通过增量d把序列分为多个子表，外层for循环控制增量的变化 for(int dk = n/2; dk >= 1; dk /= 2){ //对于每一个增量得到的子表进行插入排序 for(int i = dk+1; i <= n; i++){ if(A[i] < A[i-dk]){ //如果待插入元素小于有序序列最大元素，则需要插入 A[0] = A[i]; //将元素暂存到A[0]，但在这里并没有起到哨兵的作用 for(int j = i-dk; j > 0 && A[0] < A[j]; j -= dk) A[j+dk] = A[j]; //依次向后移动 A[j+dk] = A[0]; //将待排序元素插入有序序列 } } } }
④性能分析：
1.空间效率：使用常数个辅助单元，空间复杂度为O(1)
2.时间效率：由于希尔排序的复杂度依赖增量序列的函数，所以时间复杂度分析比较困难。当n在某个特定范围时，其时间复杂度为O(n1.3)，最坏情况下为O(n2)。
3.稳定性：不稳定
4.适用性：仅适用于线性表为顺序存储的情况。
二、交换排序
此类排序是根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。
1.冒泡排序
①算法的执行过程：
冒泡排序是一种基于比较的简单交换排序，会进行多轮交换，在每趟排序中，从后往前两两比较相邻元素的值，若为逆序，则交换他们。
在每趟排序完成后，都会将当前待排序序列中最小的元素放到第一个位置（或最大的元素放到最后一个位置）。
最多进行n-1趟处理后，所有元素就能排好。第i趟排序要进行n-i次比较。
②算法执行过程可视化演示：
③算法代码：
void BubbleSort(ElemType A[], int n){ for(int i = 0; i < n-1; i++){ //一共n-1趟 for(int j = 0; j < n-1-i; j++){ //对应每一趟的比较 if(A[j] > A[j+1]){ //若为逆序则交换 swap(A[j], A[j+1]); } } } }
④性能分析：
1.空间效率：使用常数个辅助单元，空间复杂度为O(1)
2.时间效率：最好情况下时间复杂度为O(n)，最坏情况下初始为逆序，需要n-1趟排序，第i趟需要n-i次关键字的比较，每次比较都需要移动元素3次来交换元素位置，所以最坏情况和平均情况复杂度都为O(n2).
3.稳定性：稳定
4.适用性：适用于线性表为顺序存储和链式存储的情况。
拓展（链式存储的冒泡排序）：
void sort_list(PNODE pHead){ int i,j,t; PNODE p, q; int len= length_list(pHead); for (i=0,p=pHead->pNext;i<len-1;++i,p=p->pNext){ for (j=i+1,q=p->pNext;j<len;++j,q=q->pNext){ if (p->data > q->data){ t = p->data; p->data = q->data; q->data = t; } } } }
2.快速排序
①算法的执行过程：
- 快速排序是一种基于分治思想的交换排序
- 在待排表
L[1...n]中任取一个元素pivot作为枢轴（或基准）
通过一趟排序将待排序表划分为两个部分，L[1...k-1]和L[k+1...n]，使得L[1...k-1]中所有元素小于pivot，L[k+1...n]中所有元素大于pivot。 - 此时的枢轴元素privot已经放到了最终的位置上。
- 递归的对两个子表重复以上步骤，直到每个子表只有一个元素或为空。
②算法执行过程演示：
③算法代码：
//划分操作 int Partition(ElemType A[], int low, int high){ ElemType pivot = A[low]; //定义第一个元素为枢轴元素 while(low < high){ while(low < high && A[high] > pivot) high--; A[low] = A[high]; //从后往前找到第一个小于枢轴的元素放到左边 while(low < high && a[low] < pivot) low++; A[high] = A[low]; //从前往后找到第一个大于枢轴的元素放到右边 } A[low] = pivot; //将枢轴元素放到最终的位置 return low; //返回枢轴元素的位置 } //递归的进行快排 void QuickSort(ElemType A[], int low, int high){ if(low < high){ //如果两个指针的位置相反或者相等，表明递归结束 int pos = Partition(A, low, high); //找到枢轴元素的位置 QuickSort(A, low, pos-1); //递归排序左子表 QuickSort(A, pos+1, high); //递归排序右子表 } }
④性能分析：
1.空间效率：由于快排是递归的，所以空间复杂度与递归深度有关。
二分递归空间复杂度最好情况下为O(log2n)，最坏情况下进行n-1次调用，深度为O(n)
2.时间效率：与划分的好坏有关
最坏情况下：每层递归都是最大限度的不对称（两个区域分别包含n-1和0个元素），复杂度为O(n2)也就是对应初始排序表基本有序或基本逆序。
最理想情况：每层递归能能完美的划分，复杂度为O(nlog2n)。得到的两个子问题规模都小于n/2。
3.稳定性：不稳定
4.适用性：适用于线性表为顺序存储的情况。
