插入排序：直接插入排序、希尔排序
交换排序：冒泡排序、快速排序
选择排序：简单选择排序、堆排序
其他：归并排序、基于统计的排序
一、直接插入排序
#include
#include
/*
直接插入排序：是就地排序，是稳定的，时间复杂度：O（n^2）
*/
int a[105];
int n;
int main()
{
int t;
scanf("%d",&n);
for(int i=1;i=1;j--)
{
if(a[j]>t)
{
a[j+1]=a[j];
}
else{
break;
}
}
a[j+1]=t;
}
for(int i=1;i二、希尔排序
#include
#include
/*
希尔排序：取希尔增量序列时： 是就地排序，不是稳定的，时间复杂度：O（n^2）
*/
int a[105];
int n;
int main()
{
int t;
scanf("%d",&n);
int k=0;
for(int i=1;i=1;d=d/2)
{
k++;//计算趟数
//以增量d分组，对每组进行直接插入排序
for(int i=1+d;i=1;j=j-d)
{
if(a[j]>t)
{
a[j+d]=a[j];
}
else{
break;
}
}
a[j+d]=t;
}
printf("第%d趟，增量为%d,排好的结果：",k,d);
for(int i=1;i三、冒泡排序
#include
#include
#define maxx 100
/*所谓交换,是指根据序列中两个关键字比较的结果来对换这两个关键字在序列中的位置。*/
int a[maxx],n,t;
int v;//标记
int main()
{
scanf("%d",&n);
for(int i=1;ia[j+1])
{
v=1;
t = a[j];
a[j] = a[j+1];
a[j+1] = t;
}
}
if(v==0)//v仍然等0，说明没交换，说明完全有序
{
break;
}
}
for(int i=1;i四、快速排序
排序区间[l,r] , 选a[l] 做基准数
两个下标i=l,j=r;相对遍历。
先用j 找一个比x小的数，放在i位置，i++
再用i 找一个比x大的数，放在j位置，j–
不断循环，直到 i==j为止，此时i(j)位置就是x的位置
#include
#include
/*交换排序：基于数据交换的排序
1.冒泡排序：是就地排序， 是稳定的，时间复杂度 O（n^2）
2.快速排序：---递归: 是就地排序，不稳定，时间复杂度O(nlogn) ------待排序的数组已经保持需要的顺序了，容易退化成O(n^2)
每一趟：先选一个标准（基准数），按照基准数进行划分，把比基准数小的交换到他前面，
把比基准数大的交换到他后面
基准数怎么选：对区间(l,r)
（1）选排序区间的第一个数--a[l]------为例
（2）选排序区间的最后一个数--a[r]
*/
void QuickSort(int a[],int l,int r)
{//选排序区间的第一个数--a[l]做基准数
if(l>=r)
{
return;
}
int x=a[l];
int i=l;
int j=r;
while(ix)j--;
if(i五、（简单）选择排序
每趟从待排序区中，选择一个最小的数，放到待排序区的第一个位置。从而实现排序
#include
#include
#define maxx 100
int a[maxx],n,t;
int minn;
int main()
{
int minn;//最小元素的下标
scanf("%d",&n);
for(int i=1;i六、堆排序
堆—–>完全二叉树—–>数组存储
a[i]父亲：a[i/2]
a[i]左孩子：a[2*i]
a[i]右孩子：a[2*i+1]
1.建堆（两种方法）
（1）自我初始化：在原数组的基础上进行初始化
从子树入手由小到大去调整每棵子树；
对于每棵子树，我们向下调整：
让根节点和左右孩子节点作比较，如果子树值小：最小值和根节点交换，继续向下调整子树
（2）通过插入来建堆
数组每多一个数据就调整一次。新插入的数据放在放在最后，如果其比父亲大或者新插入的数据是根节点就不用调整否则就向上调整
堆排序：
（1）建堆（流程见上）
（2）循环n次 每次输出最小的数—->a[1],
删掉a[1]—>让堆中最后一个节点来替换a[1]，然后重新对a[1]向下调整
#include
#include
#define maxx 100
/*升序排列
堆排序:就地排序，不稳定 ，时间复杂度O(nlogn)
n个元素，保存在a数组中，直接在a数组中
1.初始化成一个小顶堆：
下标最大的内部节点的下标是几？最后一个内部节点的下标是几？
n/2
（1）找到最后一个内部节点（n/2）,依次调整每棵子树
调整过程：依次向下比较调整：若该节点比左右孩子节点中的最小值大，进行交换，直到不满足该条件位置
2.在小顶堆的基础上，进行堆排序
循环n-1次：
（1）输出（删除）根节点；
（2）最后一个位置的节点代替根节点
（3）向下调整
---输入最后一个元素
3.堆中插入一个元素：
（1）把元素放到数组最后
（2）向上和父亲节点比较进行调整
*/
void downAdjust(int a[],int i,int m)//对以 下标i的元素 为根节点的子树进行向下调整
{//now是当前调整的节点，next是now的孩子，也是下一次要调整的节点
int now=i;
int next;
int t;
while(now*21)
{
n服务器托管网ext=now/2;// now的父亲
if(a[next]=1;i--)
{
downAdjust(a,i,n);
}
//堆排序
int m=n;//数组最后一个元素下标
int t;
for(int i=1;i七、归并排序
#include
#include
#define maxx 100
void merge(int a[],int l,int mid,int r)
{
//l~mid
//mid+1~r
int t[maxx];
int k=0;//t数组的下标
int i=l;
int j=mid+1;
while(i八、基于统计的排序
1.计数排序
统计一下每个数出现的次数，然后直接按次数输出即可（以空间换时间的算法）
缺点：
a.无法对负整数进行排序（偏移量优化）
b.极其浪费内存空间
c服务器托管网.是一个不稳定排序（可优化）
2.桶排序
1、将代排序的序列部分分到若⼲个桶中，每个桶内的元素再进⾏个别的排序。
2、时间复杂度最好可能是线性的O（n），桶排序不是基于⽐较的排序
3.基数排序
略
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
前面的文章中，介绍了，的模拟实现，本篇文章将介绍对于的模拟实现。 目录 1. list的基本结构： 2. list功能实现：尾部插入元素： 3. list迭代器的实现： 4. list功能实现：在任意位置前插入元素： 4.1 函数实现方法： 4.2 函数运行逻…
