宜昌微网站建设,长沙本土网站建设公司,杭州广告公司网站建设,帮做网站的插入排序#xff1a;直接插入排序、希尔排序
交换排序#xff1a;冒泡排序、快速排序
选择排序#xff1a;简单选择排序、堆排序
其他#xff1a;归并排序、基于统计的排序
一、直接插入排序
#includestdio.h
#includestdlib.h
/*
直接插入排序#…插入排序直接插入排序、希尔排序
交换排序冒泡排序、快速排序
选择排序简单选择排序、堆排序
其他归并排序、基于统计的排序
一、直接插入排序
#includestdio.h
#includestdlib.h
/*
直接插入排序是就地排序是稳定的时间复杂度On^2
*/
int a[105];
int n;
int main()
{int t;scanf(%d,n);for(int i1;in;i){scanf(%d,a[i]);}//认为a[1] 是有序区域a[2---n]是乱序区for(int i2;in;i){ta[i];int j;for(ji-1;j1;j--){if(a[j]t){a[j1]a[j];} else{break;}}a[j1]t;} for(int i1;in;i){printf(%d ,a[i]);}return 0;
}
二、希尔排序
#includestdio.h
#includestdlib.h
/*
希尔排序取希尔增量序列时 是就地排序不是稳定的时间复杂度On^2
*/
int a[105];
int n;
int main()
{int t;scanf(%d,n);int k0;for(int i1;in;i){scanf(%d,a[i]);}for(int dn/2;d1;dd/2) {k;//计算趟数 //以增量d分组对每组进行直接插入排序for(int i1d;in;i){ta[i];int j;for(ji-d;j1;jj-d){if(a[j]t){a[jd]a[j];}else{break;}}a[jd]t; } printf(第%d趟增量为%d,排好的结果,k,d);for(int i1;in;i){printf(%d ,a[i]);}printf(\n);} return 0;
}
三、冒泡排序
#includestdio.h
#includestdlib.h
#define maxx 100
/*所谓交换,是指根据序列中两个关键字比较的结果来对换这两个关键字在序列中的位置。*/
int a[maxx],n,t;
int v;//标记
int main()
{scanf(%d,n);for(int i1;in;i){scanf(%d,a[i]);}//冒泡排序//外层循环控制 排序的趟数 n个元素排序需要循环n-1次 【1】for(int i1;in-1;i) {v0;//内层循环控制比较的次数 n个元素第i趟比较n-i次 【2】for(int j1;jn-i1;j) {//比较相邻的元素大小 目的将最大的元素选出到移动到最后 if(a[j]a[j1]){v1;t a[j];a[j] a[j1];a[j1] t;}}if(v0)//v仍然等0说明没交换说明完全有序 {break;}}for(int i1;in;i){printf(%d ,a[i]);}return 0;
}
四、快速排序
排序区间[l,r] , 选 a[l] 做基准数
两个下标il,jr;相对遍历。
先用j 找一个比x小的数放在i位置i
再用i 找一个比x大的数放在j位置j--
不断循环直到 ij为止此时i(j)位置就是x的位置
#includestdio.h
#includestdlib.h
/*交换排序基于数据交换的排序
1.冒泡排序是就地排序 是稳定的时间复杂度 On^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(lr){return;} int xa[l];int il;int jr; while(ij){//先 从后往前找一个小于基准数小的数放到i位置 while(ija[j]x)j--; if(ij){a[i]a[j];i;} //再从前往后找一个小于基准数大的数放到j位置while(ija[i]x)i; if(ij){a[j]a[i];j--;} }a[i]x;QuickSort(a,l,i-1); QuickSort(a,i1,r);
}int main()
{int a[105]; int n;scanf(%d,n);for(int i1;in;i){scanf(%d,a[i]);}//快速排序QuickSort(a,1,n); for(int i1;in;i){printf(%d ,a[i]);}printf(\n);return 0;
}
五、简单选择排序
每趟从待排序区中选择一个最小的数放到待排序区的第一个位置。从而实现排序
#includestdio.h
#includestdlib.h
#define maxx 100int a[maxx],n,t;
int minn; int main()
{int minn;//最小元素的下标 scanf(%d,n);for(int i1;in;i){scanf(%d,a[i]);}//简单选择排序:就地排序 时间复杂度O(n^2) ,不稳定的排序 //简单选择排序:进行n-1趟排序每次都在乱序区中选择一个最小的元素放在乱序的第一个位置此时有序区1乱序区-1 for(int i1;in-1;i)//控制循环趟数{minni; for(int ji1;jn;j)//控制乱序区去找最小的元素的位置{if(a[j]a[minn]){minnj;}}//把minn位置的元素放在乱序区的第一个位置即i位置if(minn!i){int ta[i];a[i]a[minn];a[minn]t; }} for(int i1;in;i){printf(%d ,a[i]);}printf(\n);return 0;
}
六、堆排序
堆-----完全二叉树-----数组存储
a[i]父亲a[i/2]
a[i]左孩子a[2*i]
a[i]右孩子a[2*i1]
1.建堆两种方法
1自我初始化在原数组的基础上进行初始化
从子树入手由小到大去调整每棵子树
对于每棵子树我们向下调整
让根节点和左右孩子节点作比较如果子树值小最小值和根节点交换继续向下调整子树
2通过插入来建堆
数组每多一个数据就调整一次。新插入的数据放在放在最后如果其比父亲大或者新插入的数据是根节点就不用调整否则就向上调整
堆排序
1建堆流程见上
2循环n次 每次输出最小的数----a[1],
删掉a[1]---让堆中最后一个节点来替换a[1]然后重新对a[1]向下调整
#includestdio.h
#includestdlib.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 nowi;int next;int t;while(now*2m){nextnow*2;//now的左孩子if(next1ma[next1]a[next]){nextnext1;//now的右孩子 }if(a[now]a[next]){break;} else{ta[now];a[now]a[next];a[next]t;nownext;}} }
void upAdjust(int a[],int n)
{//now是当前调整的节点next是now的父亲也是下一次要调整的节点int nown;int next; int t;while(now1){nextnow/2;// now的父亲if(a[next]a[now])//父亲节点比当前节点大 {break;}else{ta[now];a[now]a[next];a[next]t;nownext;}} } int main()
{int n;//元素个数int a[maxx];// scanf(%d,n);for(int i1;in;i){scanf(%d,a[i]);}
//把a数组初始化成小顶堆for(int in/2;i1;i--){downAdjust(a,i,n);}
//堆排序int mn;//数组最后一个元素下标 int t;for(int i1;in;i){printf(%d ,a[1]);ta[1];a[1]a[m];a[m]t;m--;downAdjust(a,1,m);} printf(\n);for(int i1;in;i){printf(%d ,a[i]);}printf(\n);
//在堆中插入一个元素n;scanf(%d,a[n]);upAdjust(a,n);return 0;
}//堆的应用--优先队列
七、归并排序
#includestdio.h
#includestdlib.h
#define maxx 100
void merge(int a[],int l,int mid,int r)
{//l~mid//mid1~rint t[maxx];int k0;//t数组的下标 int il;int jmid1;while(imidjr){if(a[i]a[j]){t[k]a[i]; k;i;}else{t[k]a[j];k;j;}}while(imid){t[k]a[i]; k;i;}while(jr){t[k]a[j]; k;j;}for(int i0;ik;i){a[li]t[i];}}void merge_sort(int a[],int l,int r)
{int mid;if(lr){mid(lr)/2;//l~midmerge_sort(a,l,mid);//mid1~rmerge_sort(a,mid1,r);merge(a,l,mid,r);}}
int main()
{int n;//元素个数int a[maxx];// scanf(%d,n);for(int i1;in;i){scanf(%d,a[i]);}merge_sort(a,1,n);for(int i1;in;i){printf(%d ,a[i]);}printf(\n);return 0;
}
八、基于统计的排序
1.计数排序
统计一下每个数出现的次数然后直接按次数输出即可以空间换时间的算法
缺点
a.无法对负整数进行排序偏移量优化
b.极其浪费内存空间
c.是一个不稳定排序可优化
2.桶排序
1、将代排序的序列部分分到若⼲个桶中每个桶内的元素再进⾏个别的排序。 2、时间复杂度最好可能是线性的On桶排序不是基于⽐较的排序
3.基数排序
略
