简单的冒泡算法,原来不简单

是不是觉得冒泡算法很简单?

是的,确实很简单,中心思想是两两交换。

那你能写出冒泡算法吗?

你能解释冒泡算法中的各层含义是什么吗?

你又能写出几种冒泡算法呢?

曾经在面试中,遇到过冒泡算法,我能模糊的写出,却纠结于参数边界值的控制。为了不再继续模糊下去,为了不至于被人鄙视----硕士毕业3年了,连这个小算法也搞不好。

于是趁此离职时期,好好的分析一下。

1冒泡排序各层循环的含义

1.1第一层循环

通常为

for (int i=0;i

For(int i=1;i

当然,如果你喜欢,你甚至可以定义i初始值为3、为4、为100等。不过我相信,没人会那么无聊的。

不过这却揭示了第一层循环与i的初始值无关,而只与循环了多少次有关。

因此,冒泡排序第一层循环的含义为:需要遍历多次数组,才能将这个数组排好序。

那到底需要遍历多少次数组,才能排好序呢?

第一次遍历,确定一个最值。

第二次遍历,确定第二个最值。

。。。

第num-1次遍历,确定第num-1最值。Num-1个最值都确定了,自然整个数组也就排好序了。

因此,第一层循环含义为:需要遍历num-1次数组,才能将数组排好序。

1.2第二层循环

通常定义为int j;  j是一个与i相关的变量,第2层循环需要用到第一层的i的值。

那第二层循环要解决的问题是什么?

不好想的话,我们反过来想,在第二层循环时,我们还要对已经排好序的位置进行遍历吗?

当然不需要作此无用功,在第二层遍历中,我们只需对未排好序的那些待排位置进行遍历即可,而首先,我们必须知道,哪些元素是已经拍过序的,哪些元素是待排序的。

所以,我们第二层循环要解决的问题便是:待排序区域的起始和结尾位置。

而要解决这个问题,

首先,第一个要解决的便是:在进行这个循环时,数组已经排好了几个值。

其次,第二个要解决的便是:在数组中,待排序区域的其实和末尾位置分别是什么。

第一个要解决的问题与第一层循环已经进行了多少次有关。

第二个要解决的问题则与排序时遍历的方向有关。

2冒泡排序算法

2.1  i=0

[cpp]view plaincopy

voidBubbleSortBtoS(intA[],intnum)// 从数组末尾向数组开始遍历

{

inttemp=0;

for(inti=0;i

{

for(intj=num-1;j>i;j--)//  待排的数据为i,i+1,...num-1    此处判断条件为j>i

{

if(A[j]

{

temp=A[j];

A[j]=A[j-1];

A[j-1]=temp;

}

}

}

}

[cpp]view plaincopy

voidBubbleSortStoB(intA[],intnum)// 从数组开始向数组末尾遍历

{

inttemp=0;

for(inti=0;i

{

for(intj=0;j

{

if(A[j]>A[j+1])

{

temp=A[j];

A[j]=A[j+1];

A[j+1]=temp;

}

}

}

}

2.2  i=1

好吧,总有人喜欢从i=1开始作为第一层循环的起始值,这是习惯问题,因此我们也分析下从1开始时的程序。

[cpp]view plaincopy

voidBubbleSortBtoS1(intA[],intnum)// 从数组末尾向数组开始遍历

{

inttemp=0;

for(inti=1;i

{

for(intj=num-1;j>=i;j--)//  待排的数据为i-1,i,i+1,...num-1   此处为j>=i

{

if(A[j]

{

temp=A[j];

A[j]=A[j-1];

A[j-1]=temp;

}

}

}

}

[cpp]view plaincopy

voidBubbleSortStoB1(intA[],intnum)// 从数组开始向数组末尾遍历

{

inttemp=0;

for(inti=1;i

{

for(intj=0;j<=num-i-1;j++)// 待排的数据为0,1,2,...,n-i-1,n-i    此处为j<=num-i-1

{

if(A[j]>A[j+1])

{

temp=A[j];

A[j]=A[j+1];

A[j+1]=temp;

}

}

}

}

3冒泡算法的小改进

3.1简化从前往后遍历

[cpp]view plaincopy

voidBubbleSortStoB_Tail(intA[],intnum)// tail参数记录末尾位置

{

inttemp=0;

inttail=num-1;

for(inti=0;i

{

for(intj=0;j

{

if(A[j]>A[j+1])

{

temp=A[j];

A[j]=A[j+1];

A[j+1]=temp;

}

}

tail--;

}

}

3.2增设是否有序标志

[cpp]view plaincopy

voidBubbleSortBtoS_Modify(intA[],intnum)// 从数组末尾向数组开始遍历

{

boolbSwap=false;

inttemp=0;

for(inti=0;i

{

for(intj=num-1;j>i;j--)//  待排的数据为i,i+1,...num-1    此处判断条件为j>i

{

if(A[j]

{

bSwap=true;

temp=A[j];

A[j]=A[j-1];

A[j-1]=temp;

}

}

if(!bSwap)//   设置是否交换标志以提前退出

{

break;

}

}

}

4鸡尾酒算法

[cpp]view plaincopy

voidCockTail(intA[],intnum)

{

inttail=num-1;

inttemp=0;

for(inti=0;i

{

for(intj=tail;j>i;j--)

{

if(A[j]

{

temp=A[j];

A[j]=A[j-1];

A[j-1]=temp;

}

}

i++;

for(intj=i;j

{

if(A[j]>A[j+1])

{

temp=A[j];

A[j]=A[j+1];

A[j+1]=temp;

}

}

tail--;

}

}

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 215,076评论 6 497
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,658评论 3 389
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 160,732评论 0 350
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,493评论 1 288
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,591评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,598评论 1 293
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,601评论 3 415
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,348评论 0 270
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,797评论 1 307
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,114评论 2 330
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,278评论 1 344
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,953评论 5 339
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,585评论 3 322
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,202评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,442评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,180评论 2 367
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,139评论 2 352

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,743评论 0 33
  • 概述:排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部...
    每天刷两次牙阅读 3,729评论 0 15
  • 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部...
    蚁前阅读 5,178评论 0 52
  • 一、 1、请用Java写一个冒泡排序方法 【参考答案】 public static void Bubble(int...
    独云阅读 1,361评论 0 6
  • 1.插入排序—直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到已排序好...
    依依玖玥阅读 1,250评论 0 2