【算法导论】冒泡排序法

冒泡排序法

时间复杂度:O(n*n)

基本思想:从数组最后一个元素开始,依次与前一个元素比较,若比前一个元素小,则与之交换位置,然后再与当前前一个元素比较,直到遇到比它大的元素为止。例如:假设数组为:a[5]={3,4,2,5,1};则运算过程为:首先1与5比较,由于1<5,从而交换位置,数组变为a[5]={3,4,2,1,5};然后1与当前前一个元素2比较,一直重复上述操作,经过一次循环后,数组变为a[5]={1,3,4,2,5};第二次循环从倒数第二个元素开始……,总共循环n-1次就可以得到正确结果。总的来说,首先将最小的元素放在数组前面,然后放次最小的元素,依此类推。上述过程的图解为:

3 4 2 5 1
3 4 2 1 5
3 4 1 2 5
3 1 4 2 5
1 3 4 2 5

注:这里的红色为要进行比较的元素。

具体实现如下:

#include<stdio.h>

void BubbleSort(int* arrayA,int n);

void main()
{
	int arrayA[]={2,3,5,6,2,7,1,5};
	int n=sizeof(arrayA)/sizeof(int);

	BubbleSort(arrayA,n);

	for(int i=0;i<n;i++)
		printf("%d ",arrayA[i]);
}

void BubbleSort(int* arrayA,int n)
{
	for(int i=0;i<n-1;i++)
	{
		for(int j=n-1;j>i;j--)//j>i即可是因为前面的元素已经排好了
		{
			int temp=0;
			if(arrayA[j]<arrayA[j-1])
			{
				temp=arrayA[j];
				arrayA[j]=arrayA[j-1];
				arrayA[j-1]=temp;
			}

		}
	}
}

注意:我是在vs2008上运行的,与vc 6.0有点区别,主要是循环体中的循环变量的作用域,出错体现在循环变量的重复定义上。例如:在vs2008或vs2010上,程序为:

#include<stdio.h>
void main()
{
int i=0;
for(int i=0;i<5;i++)
printf("%d ",i);
}

则在VC 6.0上需改为:

#include<stdio.h>
void main()
{
int i=0;
for(i=0;i<5;i++)
printf("%d ",i);
} 

原文:http://blog.csdn.net/tengweitw/article/details/9707525

作者:nineheadedbird

时间: 2024-10-03 22:19:33

【算法导论】冒泡排序法的相关文章

排序算法-关于冒泡排序法的疑惑

问题描述 关于冒泡排序法的疑惑 冒泡排序法的代码 int n=0; int temp = 0; for (int i = a.length - 1; i > 0; --i) { for (int j = 0; j < i; ++j) { if (a[j + 1] < a[j]) { temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; n++; } } } 由于我是菜鸟,我写的是这样的 int n = 0; int temp = 0; for (i

算法之【冒泡排序法】

冒泡排序法是一种较简单的数值大小排序的算法.主要逻辑是: 对于原始的一组线性数据,从头到尾依次两两比较,如果前者大于后者(或者相反)则交换两个数的位置.这样一遍做下来,数组最末端即是所有数中最大的(或最小的),接下来将除了最后一个数以外剩下的数据再进行一遍刚才的算法.以此类推,每一遍的数据都越来越少,直到最后只剩一个时结束,此时排序完成. Bubble Sort is a simple algorithm ofsequencing a pile of data, especially numer

【算法导论】插入排序法

插入排序法的时间复杂度为n的平方,对于较小的输入规模来说,插入排序法比合并排序法更快些.在最佳情况下,即输入数组已经排序好,则时间复杂度可表示为n,是一个线性函数:在最差情况下,即输入数组是逆序排列时,时间复杂度为.插入排序法的具体实现方法如下: 具体的c/c++语言实现如下: #include<iostream> #include<ctime> using namespace std; void InsectionSortAscend(int* arrayA,int Length

【算法导论】排序算法总结

排序算法总结         从六月初开始看算法导论,陆陆续续看了有2个月了,但实际看的时间只有半个月左右.这期间都忙着找导师.期末考试,同时还回家修养了十来天.真正专心的看算法是在离家返校后,由于没有考试和作业的烦恼,天天都沉浸在算法中,感觉效率较高.这段时间学到的东西较多,下面来总结一下:         学到的排序算法可以分为两类:比较排序.非比较排序.(这些排序算法的详细介绍及c程序实现在本文末都给出了链接,欢迎参考与指正!)         比较排序有:插入排序法.合并排序法.堆排序法

【算法导论】排序(一)

虽然久闻大名,但第一次接触算法导论,是看了网易公开课MIT的<算法导论>课,记得 第一集就讲到了 插入排序和归并排序. 几个星期前也买了算法导论这本书,准备慢慢啃~ 这星期主要在看前两 部分,除了对于讲渐进时间.递归式分析这些东西感到云里雾里的,其它的都就 感觉越看越有觉得入 迷,果然不愧是一本经典之作 好吧,开始.本文主要是用C++把书中的算法实现,以及一些笔记. 一.插入排序. 插入算法的设计使用的是增量(incremental)方法:在排好子数组A[1..j- 1]后,将 元素A[ j]

高效算法的常用技术(算法导论)

对于高效算法, 有些比较简单的技术, 如分治法, 随机化, 和递归求解技术. 这边介绍些更为复杂的技术, 动态规划, 贪心算法 当对于复杂问题设计算法时, 首先会想到使用分治法 来解决, 分而治之, 一个很有哲理性的思路, 再复杂的问题都可以不断分解到你可以轻松解决的粒度, 把所有简单问题都解决完后, 组合在一起就得到了复杂问题的解, 可以看出其中典型的递归求解的思路. 使用分治法的要求, 各个子问题是独立 的 (即不包含公共的子子问题,子问题不重叠 ). 如果子问题重叠, 用分治法就比较低效,

基本数据结构(算法导论)与python

Stack, Queue Stack是后进先出, LIFO, 队列为先进先出, FIFO 在python中两者, 都可以简单的用list实现, 进, 用append() 出, Stack用pop(), Queue用pop(0), pop的时候注意判断len(l)  对于优先队列, 要用到前面讲到的堆 链表和多重数组 这些数据结构在python中就没有存在的价值, 用list都能轻松实现 散列表 为了满足实时查询的需求而产生的数据结构, 查询复杂度的期望是O(1), 最差为O(n) 问题描述, 对

C语言冒泡排序法心得_C 语言

记得以前在大学里学习c语言的时候,刚开始是很吃力的. 入门级别的算法中有个叫冒泡排序法,也有称为气泡排序法.那时候刚接触它就对它的名字特别感兴趣,因为觉得很有意思.好了,废话不多说了,我们先一起简单回忆下这个冒泡排序法.  一.打印行和列一般是这样的一个简单代码,输出4行4列*: for(int i = 1,i < 5,i++){ for(int j = 1,j < 5,j++){ printf("*"); } printf("n\"); }  二.打印

用PHP写的一个冒泡排序法的函数简单实例_php实例

前几天遇到的一道关于算法的考题,要求用PHP语言实现对一个数组进行排序,我写了一个采用冒泡排序法的函数,和大家分享一下. <? //冒泡排序法 function bubble_sort($array) { $count = count($array); if($count <= 0) { return false; } for($i=0; $i<$count; $i++) { for($k=$count-1; $k>$i; $k--) { if($array[$k] < $a