高陵网站建设,游戏云服务器租用,教育平台网站,wordpress 剪切板图片自动上传冒泡排序是初学C语言的噩梦#xff0c;也是数据结构中排序的重要组成部分#xff0c;本章内容我们一起探讨冒泡排序#xff0c;从理论到代码实现#xff0c;一步步深入了解冒泡排序。排序算法作为较简单的算法。它重复地走访过要排序的数列#xff0c;一次比较两个元素也是数据结构中排序的重要组成部分本章内容我们一起探讨冒泡排序从理论到代码实现一步步深入了解冒泡排序。排序算法作为较简单的算法。它重复地走访过要排序的数列一次比较两个元素如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢浮到数列的顶端。算法步骤比较相邻的元素。如果第一个比第二个大就交换他们两个。对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对。这步做完后最后的元素会是最大的数。针对所有的元素重复以上的步骤除了最后一个。持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较。动图演示可能大家对文字描述不敏感但是这副图完美的呈现了冒泡排序的实现过程。本图来源于网络时间复杂度什么时候最快这点不用想当输入的数据已经是正序时都已经是正序了我还要你冒泡排序有何用啊。什么时候最慢这个就与上文相对应肯定是反序的时候最慢。分析最好情况是一次搞定时间复杂度是O(N)最坏的情况就是反序时间复杂度是O(N^2);平均情况时间复杂度是O(N^2);代码实现代码实现原理图我们先做一个交换函数void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}实现代码我们先来一种常规的方法//冒泡函数
void Bubblesort(int* a, int n)
{for (int i 0; i n; i){for (int j 1; j n - i; j){if (a[j - 1] a[j]){Swap(a[j - 1], a[j]);}}}
}当然我们可以用”for“的方法实现也可以用“while”的方法实现。void Bubblesort(int* a, int n)
{ int end n;while ((end 0)){for (int i 1; i end; i){if (a[i - 1] a[i]){Swap(a[i - 1], a[i]);}}end--;}
}有些小伙伴可能会对两次“for”才能实现,初学者就会产生疑惑为什么会这样那我们可以先写一趟冒泡排序void Bubblesort(int* a, int n)
}
//一趟for (int i 0; i n - 1 - j; i){if (a[i] a[i 1]){Swap(a[i], a[i 1]);}}
}然后我们再来写整个冒泡排序void Bubblesort(int* a, int n)
}
//一趟for(int j 0; j n; j){for (int i 0; i n - 1 - j; i){if (a[i] a[i 1]){Swap(a[i], a[i 1]);}}}
}看到这里我们有些小伙伴可能对总数是“n”还是“n-1”有些疑问。其实这里我们如果用仔细看可以发现前者是以“j 1”开始后者是以“0”开始所以造成了不同。我们接着改一下提升一下效率。我们想一下假如我们在交换以后接下来的数组已经是有序的了那么我们就没必要交换了。void Bubblesort(int* a, int n)
{for (int j 0; j n - 1; j){int exchange 0;for (int i 0; i n - 1 - j; i){if (a[i] a[i 1]){Swap(a[i], a[i 1]);exchange 1;}}if (exchange 0){break;}}
}这样我们就完成了总结我们用C语言多种方式实现了冒泡排序冒泡排序实现本身不难大家多多体会尝试自己实现代码才能够真正的掌握这些参考代码希望能够给大家带来帮助。欢迎大家点赞和收藏。
