实现优化的冒泡排序算法
本文最后更新于 479 天前,其中的信息可能已经有所发展或是发生改变。

最近在刷题啊,从最基本的东西学起,就譬如像冒泡排序:

冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端,故名。

————百度百科

其实还是挺形象的:可以发现,大的元素一直在向容器顶端走。

在这里对这个算法进行优化:

1.首先,我们不用每次在排序完了之后对整个数组进行检索,我们可以是指一个全局标志位,在每次排序过程中,其实已经对数组进行了遍历,如果对数组的两个键值进行了交换,便设置这个全局标志位,在循环开始时清除,在循环结束后检查。如果这个标志位没有被设置,那么说明数组已经排序完成,退出循环。

2.在我们已经排序过一遍之后,我们发现,后面的一部分元素顺序其实是已知的,我们不需要在对这部分进行遍历,于是我们每次都可以减少遍历空间,在这里可以控制遍历空间来达到算法优化的目的。

在分析完了之后,我们动手写代码,这里有一份我自己的版本,C实现,可以看一下:

这里我对一个最坏情况的10元数组(完全反序)进行排序

/* 这里是冒泡排序的算法 */
#include <stdio.h>
#include <stdlib.h>

int main(void){
    int Length = 10;
    int Limit = Length;
    int Array[10] = {10,9,8,7,6,5,4,3,2,1};
    int Now = 0;
    int Copy, Next;
    int Do = 0;
    int Count = 0;
    while (1){
        Next = Now + 1;
        if (Now == Length - 1){
            if (! Do){
                int Temp;
                for (Temp = 0; Temp < Limit; Temp++){
                    printf("%d ", Array[Temp]);
                }
                putchar('\n');
                break;
            }else{
                Length = Now;
                Do = 0;
                Now = 0;
            }
        }else{
            Count++;
            if (Array[Now] > Array[Next]){
                Copy = Array[Now];
                Array[Now] = Array[Next];
                Array[Next] = Copy;
                Do++;
            }
            Now++;
        }
    }
    printf("Total Scan : %d\n", Count);
    system("pause");
    return 0;
}

代码没有注释,大家谅解一下。

分析一下优化的程度:
1.我们在每一次循环都能减少一次对数组的遍历。
2.我们在循环的过程中的遍历空间一直在减少。

时间复杂度仍然是O(N^2),但是最差情况下,也能减少一半的运算量:
这是优化之前:

优化之后就是文章开头的那个,结果大家能看到,到一半的运算量。

为什么不用VS呢,因为它对我120G的固态盘本子压力比较大·····

暂无评论

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇