直接插入排序+希尔排序+冒泡排序+快速排序+选择排序+堆排序+归并排序+基于统计的排序
插入排序：直接插入排序、希尔排序
交换排序：冒泡排序、快速排序
选择排序：简单选择排序、堆排序
其他：归并排序、基于统计的排序
一、直接插入排序
#include<stdio.h>
#include<stdlib.h>
/*
直接插入排序：是就地排序，是稳定的，时间复杂度：O（n^2）
*/
int a[105];
int n;
int main()
{
int t;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
//认为：a[1] 是有序区域，a[2---n]是乱序区
for(int i=2;i<=n;i++)
{
t=a[i];
int j;
for(j=i-1;j>=1;j--)
{
if(a[j]>t)
{
a[j+1]=a[j];
}
else{
break;
}
}
a[j+1]=t;
}
for(int i=1;i<=n;i++)
{
printf("%d ",a[i]);
}
return 0;
}二、希尔排序
#include<stdio.h>
#include<stdlib.h>
/*
希尔排序：取希尔增量序列时： 是就地排序，不是稳定的，时间复杂度：O（n^2）
*/
int a[105];
int n;
int main()
{
int t;
scanf("%d",&n);
int k=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int d=n/2;d>=1;d=d/2)
{
k++;//计算趟数
//以增量d分组，对每组进行直接插入排序
for(int i=1+d;i<=n;i++)
{
t=a[i];
int j;
for(j=i-d;j>=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<=n;i++)
{
printf("%d ",a[i]);
}
printf("n");
}
return 0;
}三、冒泡排序
#include<stdio.h>
#include<stdlib.h>
#define maxx 100
/*所谓交换,是指根据序列中两个关键字比较的结果来对换这两个关键字在序列中的位置。*/
int a[maxx],n,t;
int v;//标记
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
//冒泡排序
//外层循环控制 排序的趟数 n个元素排序需要循环n-1次 【1】
for(int i=1;i<=n-1;i++)
{
v=0;
//内层循环控制比较的次数 n个元素第i趟比较n-i次 【2】
for(int j=1;j<n-i+1;j++)
{
//比较相邻的元素大小 目的：将最大的元素选出到移动到最后
if(a[j]>a[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<=n;i++)
{
printf("%d ",a[i]);
}
return 0;
}四、快速排序
排序区间[l,r] , 选 a[l] 做基准数
两个下标i=l,j=r;相对遍历。
先用j 找一个比x小的数，放在i位置，i++
再用i 找一个比x大的数，放在j位置，j--
不断循环，直到 i==j为止，此时i(j)位置就是x的位置
#include<stdio.h>
#include<stdlib.h>
/*交换排序：基于数据交换的排序
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(i<j)
{
//先 从后往前，找一个小于基准数小的数，放到i位置
while(i<j&&a[j]>x)j--;
if(i<j)
{
a[i]=a[j];
i++;
}
//再从前往后，找一个小于基准数大的数，放到j位置
while(i<j&&a[i]<x)i++;
if(i<j)
{
a[j]=a[i];
j--;
}
}
a[i]=x;
QuickSort(a,l,i-1);
QuickSort(a,i+1,r);
}
int main()
{
int a[105];
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
//快速排序
QuickSort(a,1,n);
for(int i=1;i<=n;i++)
{
printf("%d ",a[i]);
}
printf("n");
return 0;
}五、（简单）选择排序
每趟从待排序区中，选择一个最小的数，放到待排序区的第一个位置。从而实现排序
#include<stdio.h>
#include<stdlib.h>
#define maxx 100
int a[maxx],n,t;
int minn;
int main()
{
int minn;//最小元素的下标
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
//简单选择排序:就地排序， 时间复杂度O(n^2) ,不稳定的排序
//简单选择排序:进行n-1趟排序，每次都在乱序区中选择一个最小的元素，放在乱序的第一个位置，此时有序区+1，乱序区-1
for(int i=1;i<=n-1;i++)//控制循环趟数
{
minn=i;
for(int j=i+1;j<=n;j++)//控制乱序区，去找最小的元素的位置
{
if(a[j]<a[minn])
{
minn=j;
}
}
//把minn位置的元素放在乱序区的第一个位置，即i位置
if(minn!=i)
{
int t=a[i];
a[i]=a[minn];
a[minn]=t;
}
}
for(int i=1;i<=n;i++)
{
printf("%d ",a[i]);
}
printf("n");
return 0;
}六、堆排序
堆----->完全二叉树----->数组存储
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<stdio.h>
#include<stdlib.h>
#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*2<=m)
{
next=now*2;//now的左孩子
if(next+1<=m&&a[next+1]<a[next])
{
next=next+1;//now的右孩子
}
if(a[now]<=a[next])
{
break;
}
else{
t=a[now];
a[now]=a[next];
a[next]=t;
now=next;
}
}
}
void upAdjust(int a[],int n)
{//now是当前调整的节点，next是now的父亲，也是下一次要调整的节点
int now=n;
int next;
int t;
while(now>1)
{
next=now/2;// now的父亲
if(a[next]<=a[now])//父亲节点比当前节点大
{
break;
}
else
{
t=a[now];
a[now]=a[next];
a[next]=t;
now=next;
}
}
}
int main()
{
int n;//元素个数
int a[maxx];//
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
//把a数组初始化成小顶堆
for(int i=n/2;i>=1;i--)
{
downAdjust(a,i,n);
}
//堆排序
int m=n;//数组最后一个元素下标
int t;
for(int i=1;i<=n;i++)
{
printf("%d ",a[1]);
t=a[1];
a[1]=a[m];
a[m]=t;
m--;
downAdjust(a,1,m);
}
printf("n");
for(int i=1;i<=n;i++)
{
printf("%d ",a[i]);
}
printf("n");
//在堆中插入一个元素；
n++;
scanf("%d",&a[n]);
upAdjust(a,n);
return 0;
}
//堆的应用--优先队列 七、归并排序
#include<stdio.h>
#include<stdlib.h>
#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<=mid&&j<=r)
{
if(a[i]<=a[j])
{
t[k]=a[i];
k++;
i++;
}
else{
t[k]=a[j];
k++;
j++;
}
}
while(i<=mid)
{
t[k]=a[i];
k++;
i++;
}
while(j<=r)
{
t[k]=a[j];
k++;
j++;
}
for(int i=0;i<k;i++)
{
a[l+i]=t[i];
}
}
void merge_sort(int a[],int l,int r)
{
int mid;
if(l<r)
{
mid=(l+r)/2;
//l~mid
merge_sort(a,l,mid);
//mid+1~r
merge_sort(a,mid+1,r);
merge(a,l,mid,r);
}
}
int main()
{
int n;//元素个数
int a[maxx];//
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
merge_sort(a,1,n);
for(int i=1;i<=n;i++)
{
printf("%d ",a[i]);
}
printf("n");
return 0;
}八、基于统计的排序
1.计数排序
统计一下每个数出现的次数，然后直接按次数输出即可（以空间换时间的算法）
缺点：
a.无法对负整数进行排序（偏移量优化）
b.极其浪费内存空间
c.是一个不稳定排序（可优化）
2.桶排序
1、将代排序的序列部分分到若⼲个桶中，每个桶内的元素再进⾏个别的排序。
2、时间复杂度最好可能是线性的O（n），桶排序不是基于⽐较的排序
3.基数排序
略