选择邯郸网站建设,php网站源码架构,网站实名认证 备案,重庆营销型网站建设沛宣目录#xff1a;
一#xff0c;直接插入算法
二#xff0c;希尔排序算法
三#xff0c;选择排序
四#xff0c;堆排序
五#xff0c;冒泡排序算法 简介#xff1a; 排序算法目前是我们最常用的算法之一#xff0c;据研究表明#xff0c;目前排序占用计算机CPU的时…目录
一直接插入算法
二希尔排序算法
三选择排序
四堆排序
五冒泡排序算法 简介 排序算法目前是我们最常用的算法之一据研究表明目前排序占用计算机CPU的时间已高达百分之30到百分之50。可见高效率的排序算法是我们必须掌握的基本算法之一本篇博客就先跟大家介绍五种常用的排序算法直接插入算法希尔算法选择算法堆排序算法冒泡算法。
一直接插入算法 直接插入算法的原理与我们打扑克牌时进行不摸牌排序的效应一样。平常我们在打扑克牌时会不断的摸牌每当我们摸到一个牌时就会往里面插入使得我们手中的排有序。直接插入算法与之同理其基本思想是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列种直到所有的记录插入完为止得到一个新的有序序列即摸牌效应如下图是插入排序的示意图 明白以上原理后接下来要思考的是此算法的效率如何不难发现当为最好情况时即有序排列将一次性直接遍历整个数组时间复杂度为O(N)当为最坏情况是(即要跟排列的顺序相反)需要一直往首元素插入此时的时间复杂度为O(N^2)。具体代码如下
#include stdio.h
//直接插入算法
void InsertSort(int* a, int n) {for (int i 0; i n - 1; i) {// [0,end]有序把end1位置的插入到前序序列,控制[0,end1]有序int end i;int next a[i 1];// 升序排列while (end 0) {if (a[end] next) {a[end 1] a[end];}else {break;}end--;}a[end 1] next;}
}
int main() {int a[] { 5,9,7,3,0,1,4,2,6,8 };InsertSort(a, sizeof(a) / sizeof(int));for (int i 0; i sizeof(a) / sizeof(int); i) {fprintf(stdout, %d , a[i]);}puts();return 0;
}
运行图 二希尔排序算法 希尔排序是以插入排序为基础的排序。首先该算法要设置一个分组然后再用直接插入算法的思想进行预排序预排序是将数据分组排序每组数据之间有着一定的间距。如下图 上图中第一组数据9585。第二组数据176。第三组数据243。三组数据先分别用直接插入算法进行预排序排序后第一组数据为5589。第二组数据为167。第三组数据为234。经过这些预排序后整体的数据为5 1 2 5 6 3 8 7 4 9(不同颜色代表不同组中的数据可直观的看出)。 其中将数据进行预排序的目的是大的数据更快的到后面去小的数据更快的到前面去其中间距越大跳得越快越不接近有序间距越小跳得越慢越接近有序当间距为1时直接为有序因为当间距为1时就是直接插入排序。 希尔算法运用得原理就是给定一个间距值进行预排序当间距值大于1时进行的排序为预排序当间距值等于1时的排序就是直接插入排序即排序已完成。本算法的效率很高但时间复杂度很难计算出暂时先不研究这个代码实现具体如下
#include stdio.h
//希尔排序算法
void ShellSort(int* a, int n) {int grab n;//开始时设置间距grab n;//当grab 1时为直接插入算法当grab 1时为预排序while (grab ! 1) {//grab / 2;//不断的缩减grab的大小直到grab 1排序完成//由于grab一次性的缩减比较小导致算法效率较低以下的grab为改进算法提高算法效率grab grab / 3 1;//不断缩减间距grab的大小直到grab 1排序完成//以下是根据间距grab的大小来进行的插入排序for (int j 0; j grab; j) {for (int i j; i n - grab; i grab) {int end i;int x a[i grab];while (end 0) {if (a[end] x) {a[end grab] a[end];}else {break;}end - grab;}a[end grab] x;}}}
}
int main() {int a[] { 5,9,7,3,0,1,4,2,6,8 };ShellSort(a, sizeof(a) / sizeof(int));for (int i 0; i sizeof(a) / sizeof(int); i) {fprintf(stdout, %d , a[i]);}puts();return 0;
}
运行图 三选择排序
1选择排序的基本思想 每一次从待排序的数据元素中选出最小或最大的一个元素存放在系列的起始位置即进行一趟选择直到全部待排序的数据元素排完其中时间复杂度O(N^2)。空间复杂度O(1)。如下图 以上就是选择排序的基本套路但我们仔细思考下来其实这种方法还有优化空间当数据进行一趟选择时我们可直接选出最大数和最小数将其放在开头或末尾。然后再次进行遍历直到头尾遍历相遇为止。代码如下
#include stdio.h
//选择算法
void Swap(int* x1, int* x2) {int t *x1;*x1 *x2;*x2 t;
}
void SelectSort(int* a, int n) {int begin 0, end n - 1;while (begin end) {int max begin, min begin;//进行一趟遍历确定最小值和最大值的下标,当前面遍历等于end时排序就已排好for (size_t i begin 1; i end; i) {if (a[max] a[i]) {max i;}if (a[min] a[i]) {min i;}}Swap(a max, a end);//当min在最后时max与原先的end交换了位置所以这时的end的下标已经变了if (min end) {min max;}Swap(a min, a begin);//前面排好往后前进begin;//后面排好往前前进end--;}
}
int main() {int a[] { 5,9,7,3,0,1,4,2,6,8 };SelectSort(a, sizeof(a) / sizeof(int));for (int i 0; i sizeof(a) / sizeof(int); i) {fprintf(stdout, %d , a[i]);}puts();return 0;
}
运行图 四堆排序 堆排序跟二叉堆排序一模一样即先建立堆结构然后进行堆的调整使整体有序。要注意的是升序排列首选大堆降序排列首选小堆建立。(这一原理运用的是二叉树的知识如若感觉有困难就必须先把二叉树的堆结构再学习下。不建议直接上来搞这一块知识)。其中结构上是选择堆结构上的选择排序结构图如下 由于原理与之前的二插堆一样在这里就不做过多结构上的说明下面是代码的实现和讲解
#include stdio.h
void Swap(int* x1, int* x2) {int t *x1;*x1 *x2;*x2 t;
}
//归并算法
void Adjustdown(int* a, int n, int parent) {int child 2 * parent 1;while (child n) {if (child 1 n a[child] a[child 1]) {child;}if (a[child] a[parent]) {Swap(a child, a parent);parent child;child parent * 2 1;}else {break;}}
}
//以升序为例升序用建大堆思想
void HeapSort(int* a, int n) {//从最后一层走起因为要保证导入的parent往下都是有序的即大堆建立for (int i (n - 1 - 1) / 2; i 0; i--) {Adjustdown(a, n, i);}//大堆建立后根为最大数然后进行排序int end n - 1;while (end 0) {Swap(a, a end);//因为根为最大数要升序就要把最大数放入最后Adjustdown(a, end, 0);end--;}
}
int main() {//归并算法int a[] { 5,9,7,3,0,1,4,2,6,8 };HeapSort(a, sizeof(a) / sizeof(int));for (int i 0; i sizeof(a) / sizeof(int); i) {fprintf(stdout, %d , a[i]);}puts();return 0;
}
运行图 五冒泡排序算法 冒泡排序是一种交换排序所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置此种交换的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动其中时间复杂度O(N^2)空间复杂度O(1)。
冒泡排序的原理图 此种排序非常简单具体代码如下
#include stdio.h
void Swap(int* x1, int* x2) {int t *x1;*x1 *x2;*x2 t;
}
//冒泡排序算法
void BubbleSort(int* a, int n)
{for (size_t j 0; j n; j){//用x进行控制可提升算法的效率int x 0;for (size_t i 1; i n - j; i){//进行排序当没有进入此步时说明是有序的if (a[i - 1] a[i]){Swap(a[i - 1], a[i]);x 1;}}//当x 0时说明序列是有序的可直接跳出提升算法的效率if (x 0){break;}}
}
int main() {//冒泡算法int a[] { 5,9,7,3,0,1,4,2,6,8 };BubbleSort(a, sizeof(a) / sizeof(int));for (int i 0; i sizeof(a) / sizeof(int); i) {fprintf(stdout, %d , a[i]);}puts();return 0;
}
运行图 总在五种排序算法中效率最高的是希尔排序效率最低的是冒泡排序堆排序与希尔不相上下但堆排序实现起来比较麻烦因此个人建议首选希尔直接插入算法比选择排序算法和冒泡略高一筹但在进行大量数据排序时效率都不高因此在五大基本排序中希尔排序为最佳选择。
