前言一、冒泡排序原理二、冒泡排序源码三、示例结果四、总结
前言
在此之前,我们介绍了简单的桶排序,虽然其简易上手,容易 *** 作。但具有较为严重的空间浪费,也难以键值对一一匹配,还有就是当数值是小数,就无法处理,毕竟数组没有小数吧。哈哈哈。
这里为了进一步解决其小坑,我们介绍了一种较为简单的冒泡排序。
一、冒泡排序原理 冒泡排序主要依靠对数组的双重循环,两两比较,对数值进行排序。
如数组a[0]-a[4]值为:13.5、64、32、99.9、66
第1轮两两比较:64、32、99.9、66、13.5
第2轮两两比较:64、99.9、66、32、13.5
第3轮两两比较:99.9、66、64、32、13.5
这里虽然已经排序完毕,但还需继续比较排序。因为这边只是凑巧,如果是其它值就不一定了哦。 第4轮两两比较:99.9、66、64、32、13.5
顺利排序完毕。
这里我们可以发现,n个数值只需遍历n-1次。
第1轮遍历,两两比较n-1次,可以将最小的数值扔至最后位。
第2轮遍历,两两比较n-2次,可以将第2小的数值扔至倒数第2位。
……
第n-1轮遍历,两两比较1次,可以将倒数第2小(第2大)的数值,扔到倒数倒数第2位(第2位)。
为什么是n-1次呢?因为到了最后,只剩下最后一个,肯定就是它最大了喽。 为什么两两比较是n-i次呢?因为每一次遍历都会将比较的最小是放到该比较序列的最后一位,下一次就不需要再次进行比较了。 二、冒泡排序源码
#include三、示例结果 四、总结 这边我们可以很容易看出,对数值进行二重循环下的冒泡排序的时间复杂度是O(n^2),其实这就已经是很糟糕的了。所以正如Donald E. Knuth所言,“冒泡排序除了它迷人的名字和导致了某些有趣的理论问题这一事实 之外,似乎没有什么值得推荐的。using namespace std; struct students { string name; int score; }; int main() { cout << "排序的数组长度:"; int n; cin >> n; students *a = new students[n]; cout << "输入学生的姓名和成绩:" << endl; for (int i = 0; i < n; i++) { cout << "第"<> a[i].name >> a[i].score; } int tempScore = 0; string tempName= ""; for (int i = 0; i < n-1; i++) { for (int j = 0; j < n - 1 - i; j++) { if (a[j].score < a[j+1].score) { tempScore = a[j].score; tempName = a[j].name; a[j].score = a[j + 1].score; a[j].name = a[j + 1].name; a[j + 1].score = tempScore; a[j + 1].name = tempName; } } } cout << "排序后的学生姓名和成绩(从高到低):" << endl; for (int i = 0; i < n; i++) { cout << a[i].name << " " << a[i].score<<" "; } delete[]a; return 0; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)