最坏情况下时间复杂度：O(n^2) ，一般是O(n^1.3)，是一个不稳定算法。只适用于顺序存储。空间复杂度：O(1)
插入排序总结
算法名称时间复杂度空间复杂度是否稳定适用于直接插入排序O(n^2)O(1)稳定顺序存储和链式存储折半插入排序O(n^2)O(1)稳定顺序存储希尔排序O(n^2)O(1)不稳定顺序存储
3.交换排序
3.1.冒泡排序
基本思想：假设待排序表长为n，从后往前（从前往后），两两比较相邻元素的值，若为逆序（即A[i-1]>A[i]），则交换他们直到序列比较结束。
第一次循环从前往后进行比较，我们发现最总我们将最大的值9放到了最后面的位置，因为我们的比较的时候如果前面的值大于后面的值就会交换位置，所以出现了这种情况。
所以再冒泡排序中有这样的特点：一次冒泡会将一个元素放置到它最终的位置上 。也就是一次冒泡可以确定一个元素的位置，就如上图，接下来我们只需要对9元素前面的位置进行冒泡就又可以确定一个元素的位置，然后依次(n-1次)冒泡即可将一个乱序序列，排成一个递增的序列。
代码实现：
<code>void BubbleSort(ElemType A[],int n){
for(int i=0;i-1;i++){
bool flag=false;
for(int j=n-1;j>i;j--){
if(A[j-1].key>A[j].key){
swap(A[j-1],A[j]);
flag=true;
}
}
if(flag==false){
return;
}
}
}
/<code>时间复杂度（最好、平均、最坏）：O(n)、O(n2)、O(n2)，空间复杂度：O(1)，是稳定的算法。适用于顺序存储和链式存储。
3.2.快速排序
基本思想：在待排序表L[1....n] 中任取一个元素pivot 作为基准，通过一趟排序将待排序表划分为具有如下特点的两部分：（这里我们默认选取第一个元素作为基准）
这里第一次排序（一趟Partition）之后pivot左侧的元素全是小于pivot的，右侧的元素全是大于pivot的
我们可以发现一次排序后会将一个元素pivot放置到它的最终位置上 ，因为pivot左侧的元素全是小于pivot的，右侧的元素全是大于pivot的。
接下来对pivot前面的这部分在进行一次快速排序，后面的部分再进行一次快速排序。同样可以得到两个元素放置到它们最终的位置上。让后继续…【快速排序的思路】
Partition的基本思路：
初始化标记low为划分部分的第一个元素的位置，high为最后一个元素的位置，然后不断地移动两标记交换位置：
- high向前移动找到第一个比pivot小的元素
- low向后移动找到第一个比pivot大的元素
- 交换当前两个位置的元素
- 继续移动标记，执行 1、2、3 的过程，直到low大于等于high为止
Partition代码实现：
<code>
int Partition(ElemType A[],int low,int high){
ElemType pivot=A[low];
while(low/<code>第一次进行Partition：
接下来需要利用返回的这个基准的下标将数组划分为两部分，分别进行Partition
快速排序代码实现
<code>
void QuickSort(ElemType A[],int low,int high){
if(lowint pivotpos=Partition(A,low,high);
QuickSort(A,low,pivotpos-1);
QuickSort(A,pivotpos+1,high);
}
}
/<code>可以发现 快速排序是一个不稳定 的算法。时间复杂度：O(high-low+1)
快速排序的执行过程：
我们可以发现整个过程类似一颗树，也就是说如果我们基准选择的好，那么这个树的深度就比较浅，相对的递归次数就比较少，那对应工作栈的长度就越小，空间利用就越小。所以它的最好、平均空间复杂度
如果一个序列初始基本有序或逆序的情况如上，则最坏空间复杂度为O(n)。最坏的时间复杂度O(n^2)
交换排序总结
算法时间复杂度空间复杂度是否稳定适用于冒泡排序O(n^2)O(1)稳定顺序存储和链式存储快速排序O(nlog2n)O(log2n)不稳定顺序存储（链式存储）
4.选择排序
4.1.简单选择排序
基本思想：每一趟在后面n-i+1(i=1,2…n-1)个待排序元素中选取关键字最小的元素，作为有序子序列的第i个元素，直到n-1趟做完，待排序元素只剩下1个。
综上：一趟排序会将一个元素放置在最终的位置上
代码实现
选择排序是不稳定的，另外根据算法我们可以看无论初始序列是什么样的我们都要进行逐个遍历，所以时间复杂度是O(n^2)，与初始序列无关。空间复杂度为O(1)，适用于顺序存储和链式存储。
4.2.堆排序
什么是堆?
堆是一棵完全二叉树，而且满足任何一个非叶结点的值都**不大于(或不小于)**其左右孩子结点的值。
如果是每个结点的值都不小于它的左右孩子结点的值,则称为大顶堆。
如果是每个结点的值都不大于它的左右孩子结点的值,则称为
小顶堆。
什么是堆排序?
我们知道对于一个堆来说,它的根结点是整个堆中所有结点的值的最大值(顶堆或者最小值(小顶堆)所以堆排序的思想就是每次将无序序列调节成一个堆,然后从堆中选择堆顶元素的值,这个值加入有序序列,无序序列减少一个,再反复调节无序序列,直到所有关键字都加入到有序序列。
所以堆排序最重要的操作就是将无序序列调节成一个堆。
12 52 19 45 23 45 92 （以大顶堆排序为例），首先排成一个完全二叉树序列
①建堆对初始序列的完全二叉树调整成一个大顶堆调整方法：二叉树由下至上由右至左 (数组的下标由大到小)。检查每个结点是否满足大顶堆的要求,如果不满足进行调整。
- 45 23 45 92 四个结点都是叶子结点,不需要调整
- 19<45<92，所以要用92和19进行交换
- 52>45且>23 不需要调整
- 12<52<92 要用92交换12
- 12<19<45 要用45和12交换
- 到这里就建好了一个大顶堆
②将堆顶结点和最后一个结点19交换，也就是将最大值92移动到数组的最末尾，有序序列中加入了结点92，无序序列减少结点92，到这里堆排序的第一趟完成。【此时二叉树不满足堆的性质了，需要调堆】
③调堆：调整二叉树的结点使得满足大顶堆的要求。调整方法和建堆时一样。
- 45>12不需要调整，52也不需要
- 19<45<52需要将结点19和52交换
- 19<23<45需要将结点19和45交换
- 到这里又调成了一个大顶堆类似之前的操作，选出根结点52作为有序序列的第二个数值
二叉树性质5：
对完全二叉树按从上到下、从左到右的顺序依次编号1,2…,N,则有以下关系
①当i>1时，结点i的双亲结点编号为i/2，即当i为偶数时，其双亲结点的编号为i/2。它是双亲结点的左孩子，当i为奇数时，其双亲结点的编号为(i-1)/2，它是双亲结点的右孩子。
②当2i≤N时，结点i的左孩子编号为2i，否则无左孩子。
③当2i+1≤N时，结点i的右孩子编号为2i+1，否则无右孩子。
设最后一个结点编号为N，N等于二叉树中结点数量，它肯定是叶子结点。所以 第一个可能需要调整的非叶结点的下标为N/2 ，从它的左孩子开始检查，它的左孩子下标为*N/2 2，如果发生交换,下一轮检查交换过的结点的左右孩子
代码实现
空间复杂度：堆排序只需在交换节点的时候需要额外存储空间来辅佐，所以空间复杂度为O(1)
时间复杂度：堆排序的总时间可以分为①建堆部分+②n-1次向下调整堆=O(n)+
=
稳定性：不稳定
5.归并排序
假定待排序表含有n个记录，则可以看成是n个有序的子表，每个子表长度为1，然后两两归并，得到n/2 个长度为2或1的有序表；再两两归并，……如此重复，直到合并成一个长度为n的有序表为止，这种排序方法称为
2-路归并排序。例如：49 38 65 97 76 13 27
①首先将整个序列的每个关键字看成一个单独的有序的子序列
②两两归并,49和38归并成{38 49},65和97归并成(65 97,}76和13归并成(13 76}，27没有归并对象
③两两归并,{38 49}和{65 97归并成{38 49 65 97}，{13 76}和27归并成{13 27 76}
④两两归并,{38 49 65 97}和{13 27 76}归并成{13 27 38 49 65 76 97}
更据这个排序方法可以看出相当于使用了分治和递归的方法
代码实现
<code>ElemType *B=(ElemType *)malloc((n+1)*sizeof(ElemType));
void Merge(ElemType A[],int low,int mid,int high){
for(int k=low;k/<code>时间复杂度：一共n个元素
Merge第①趟:子序列长度为2.所以有n/2对子序列,每个子序列需要执行1次 Merge 。Merge时间复杂度为子序列长度之和，即2。所以第①趟 merge的时间复杂度为(n/2*2)=0(n)
第②趟 Merge:子序列长度为4,所以有n/4对子序列,每个子序列需要执行1次 Merge, Merge时间复杂度为子序列长度之和即4所以第②趟 merge的时间复杂度为O(n/4*4)=(n)
第k趟归并：子序列长度为2k，所有有n/2k对子序列。
当n/2^k=1时,k=log2n，此时需要归并的两个子序列长度为n/2，只需要一次 Merge就能实现整个序列有序。所以一共执行了k=log2n趟排序,每趟排序的时间复杂度都是(n)，所以整个归并排序的时间复杂度为O(nlog2n)
空间复杂度：因为需要将这个待排序序列转存到一个数组,所以需要额外开辟大小为n的存储空间,即空间复杂度为O(n)
**稳定性：**稳定的
6.基数排序
基数排序(也叫桶排序)是一种很特别的排序方法,它不是基于比较进行排序的,而是采用多关键字排序思想(即基于关键字各位的大小进行排序的),借助“分配”和“收集”两种操作对单逻辑关键字进行排序。基数排序又分为**最高位优先(MSD)排序和最低位优先(LSD)**排序。
例子：53，3，542，748，14，214，154，63，616
首先补充位数：053，003，542，748，014，214，154，063，616
桶实际是一个队列，先进先出（从桶的上面进，下面出）
第一次"分配"（队列从上入队）（我们这里采用最低位优先 ：即关键字补充后的个位进行比较，然后各位数对应同的序号，如果个位数为3，则进入桶3。按照依次进队）
第一次"收集"（队列从下出队）（从桶0到桶9依次出队，此时可以看出每个关键字的个位数依次递增）
第二次"分配"（队列从上入队）（第二次分配很显然使用关键字的十位数字进入桶，同样是依次入桶）
第二次"收集"（队列从下出队）（从桶0到桶9依次出队，此时可以看出每个关键字的十位数依次递增）
003 014 214 616 542 748 154 053 063
第三次"分配"（队列从上入队）
第三次"收集"（队列从下出队）（从桶0到桶9依次出队，此时可以看出每个关键字的百位数依次递增）
003 014 053 063 154 214 542 616 748
此时发现由于关键字现在三个位数都排列有序，所以整个关键字序列都排列有序。
关键字数量为n，关键字的位数为d，比如748 d=3，r为关键字的基的个数,就是组成关键字的数据的种类,比如十进制数字一共有0至9共10个数字,即r=10
空间复杂度：需要开辟关键字基的个数个队列,所以空间复杂度为O®
时间复杂度：需要进行关键字位数d次"分配"和"收集"，一次分配需要将n个关键字放进各个队列中，一次收集需要将r个桶都收集一遍，所以一次分配和一次收集时间复杂度为O(n+r)。d次就需要O(d(n+r))的时间复杂度。
稳定性：由于是队列,先进先出的性质,所以在分配的时候是按照先后顺序分配,也就是稳定的,所以收集的时候也是保持稳定的。即基数排序是稳定的排序算法。
最高位优先则是从最高位开：例子：53，3，542，748，14，214，154，63，616
其实我们这里可以对桶中关键字个数不为1的桶递归排序
首先我们现在针对桶0进行排序：即同样拿出10个桶对桶中关键字的次高位进行分配
同样看有没有关键字个数不为1的桶。此时各个桶中都只有一个关键字,递归结束,收集各桶返回到上一层。此时桶中是这个样子。
收集各桶：得到有序序列003 014 053 063 154 214 542 616 748
7.理木客
数据结构相关知识，公众号理木客同步更新中，欢迎关注！
