更多精彩内容,欢迎关注:

视频号
视频号

抖音
抖音

快手
快手

微博
微博

冒泡排序算法

文档

冒泡排序算法

冒泡排序(Bubble Sort)也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。
推荐度:
导读冒泡排序(Bubble Sort)也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。
.example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}.example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:0 0 5px 0;padding:5px;border:1px solid #d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc 100px);background-image:linear-gradient(#fff,#e5eecc 100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1px solid #d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1px solid #d4d4d4;width:98%}div.code{width:98%;border:1px solid #d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.code div{font-size:110%}div.code div,div.code p,div.example_code p{font-family:"courier new"}pre{margin:15px auto;font:12px/20px Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1px solid #ddd;border-left-width:4px;padding:10px 15px}

排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。以下是冒泡排序算法:

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

作为最简单的排序算法之一,冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样,每次都在第一页第一位,所以最熟悉。冒泡排序还有一种优化算法,就是立一个 flag,当在一趟序列遍历中元素没有发生交换,则证明该序列已经有序。但这种改进对于提升性能来

说并没有什么太大作用。1. 算法步骤

比较相邻的元素。如果第一个比第二个大,就交换他们两个。

对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。

针对所有的元素重复以上的步骤,除了最后一个。

持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

2. 动图演示

3. 什么时候最快

当输入的数据已经是正序时(都已经是正序了,我还要你冒泡排序有何用啊)。

4. 什么时候最慢

当输入的数据是反序时(写一个 for 循环反序输出数据不就行了,干嘛要用你冒泡排序呢,我是闲的吗)。

5. JavaScript 代码实现实例 function bubbleSort(arr) {    var len = arr.length;    for (var i = 0; i < len - 1; i++) {        for (var j = 0; j < len - 1 - i; j++) {            if (arr[j] > arr[j+1]) {        // 相邻元素两两对比                var temp = arr[j+1];        // 元素交换                arr[j+1] = arr[j];                arr[j] = temp;            }        }    }    return arr;}6. Python 代码实现实例 def bubbleSort(arr):    for i in range(1, len(arr)):        for j in range(0, len(arr)-i):            if arr[j] > arr[j+1]:                arr[j], arr[j + 1] = arr[j + 1], arr[j]    return arr7. Go 代码实现实例 func bubbleSort(arr []int) []int {        length := len(arr)        for i := 0; i < length; i++ {                for j := 0; j < length-1-i; j++ {                        if arr[j] > arr[j+1] {                                arr[j], arr[j+1] = arr[j+1], arr[j]                        }                }        }        return arr}8. Java 代码实现实例 public class BubbleSort implements IArraySort {    @Override    public int[] sort(int[] sourceArray) throws Exception {        // 对 arr 进行拷贝,不改变参数内容        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);        for (int i = 1; i < arr.length; i++) {            // 设定一个标记,若为true,则表示此次循环没有进行交换,也就是待排序列已经有序,排序已经完成。            boolean flag = true;            for (int j = 0; j < arr.length - i; j++) {                if (arr[j] > arr[j + 1]) {                    int tmp = arr[j];                    arr[j] = arr[j + 1];                    arr[j + 1] = tmp;                    flag = false;                }            }            if (flag) {                break;            }        }        return arr;    }}9. PHP 代码实现实例 function bubbleSort($arr){    $len = count($arr);    for ($i = 0; $i < $len - 1; $i++) {        for ($j = 0; $j < $len - 1 - $i; $j++) {            if ($arr[$j] > $arr[$j+1]) {                $tmp = $arr[$j];                $arr[$j] = $arr[$j+1];                $arr[$j+1] = $tmp;            }        }    }    return $arr;}10. C 语言实例 #include void bubble_sort(int arr[], int len) {        int i, j, temp;        for (i = 0; i < len - 1; i++)                for (j = 0; j < len - 1 - i; j++)                        if (arr[j] > arr[j + 1]) {                                temp = arr[j];                                arr[j] = arr[j + 1];                                arr[j + 1] = temp;                        }}int main() {        int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };        int len = (int) sizeof(arr) / sizeof(*arr);        bubble_sort(arr, len);        int i;        for (i = 0; i < len; i++)                printf("%d ", arr[i]);        return 0;}11. C++ 语言实例 #include using namespace std;template //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符void bubble_sort(T arr[], int len) {        int i, j;        for (i = 0; i < len - 1; i++)                for (j = 0; j < len - 1 - i; j++)                        if (arr[j] > arr[j + 1])                                swap(arr[j], arr[j + 1]);}int main() {        int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };        int len = (int) sizeof(arr) / sizeof(*arr);        bubble_sort(arr, len);        for (int i = 0; i < len; i++)                cout << arr[i] << ' ';        cout << endl;        float arrf[] = { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 };        len = (float) sizeof(arrf) / sizeof(*arrf);        bubble_sort(arrf, len);        for (int i = 0; i < len; i++)                cout << arrf[i] << ' '< intArray[j + 1])            {                temp = intArray[j];                intArray[j] = intArray[j + 1];                intArray[j + 1] = temp;                if (!swapped)                    swapped = true;            }        if (!swapped)            return;    }}13. Ruby实例 class Array  def bubble_sort!    for i in 0...(size - 1)      for j in 0...(size - i - 1)        self[j], self[j + 1] = self[j + 1], self[j] if self[j] > self[j + 1]      end    end    self  endendputs [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70].bubble_sort!14. Swift实例 import Foundationfunc bubbleSort (arr: inout [Int]) {    for i in 0.. arr[j+1] {                arr.swapAt(j, j+1)            }        }    }}// 测试调用func testSort () {    // 生成随机数数组进行排序操作    var list:[Int] = []    for _ in 0...99 {        list.append(Int(arc4random_uniform(100)))    }    print("(list)")    bubbleSort(arr:&list)    print("(list)")}

原文地址:https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/1.bubbleSort.md

参考地址:https://zh.wikipedia.org/wiki/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F

以下是热心网友对冒泡排序算法的补充,仅供参考:

热心网友提供的补充1:

改进版冒泡排序

冒泡排序第1次遍历后会将最大值放到最右边,这个最大值也是全局最大值。标准冒泡排序的每一次遍历都会比较全部的元素,虽然最右侧的值已经是最大值了。改进之后,每次遍历后的最大值,次大值,等等会固定在右侧,避免了重复比较。

Python 实现:

def bubbleSort(arr):
    for i in range(len(arr) - 1, 0, -1):  # 反向遍历
        for j in range(0, i):  # 由于最右侧的值已经有序,不再比较,每次都减少遍历次数
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

Go 实现:

func bubbleSort(arr []int) []int {
    for i := len(arr) - 1; i > 0;i-- { // 反向遍历
        for j := 0; j < i; j++ {
            if arr[j] > arr[j + 1]{
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
            }
        }
    }
    return arr
}

热心网友提供的补充2:

啦~~~只是多了一个哪里已经有序的下表而已呀~~~性能提升了不少呢~~~

def bubble_sort(list):
    k = len(list) - 1
    pos = 0
    for i in range(len(list) - 1):
        flag = False
        for j in range(k):
            if list[j] > list[j + 1]:
                tmp = list[j]
                list[j] = list[j + 1]
                list[j + 1] = tmp
                flag = True
                pos = j
        k = pos
        if flag == False:
            break
    return list
import threading
from random import *
from time import *

class Thread(threading.Thread):   
    def __init__(self,f):
        threading.Thread.__init__(self)
        self.input = None
        self.returnval = None
        self.f = f
    def run(self):                   
        if self.input != None:
            self.returnval = self.f(self.input)
        else:
            self.returnval = self.f()

再来开个多线程~~~顺便加个条件才开多线程~~~性能提升的不是一点点呢~~~

以上为冒泡排序算法详细介绍,插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等排序算法各有优缺点,用一张图概括:

关于时间复杂度

平方阶 (O(n2)) 排序 各类简单排序:直接插入、直接选择和冒泡排序。

线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序;

O(n1+§)) 排序,§ 是介于 0 和 1 之间的常数。 希尔排序

线性阶 (O(n)) 排序 基数排序,此外还有桶、箱排序。

关于稳定性

稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序。

不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序。

名词解释:

n:数据规模

k:"桶"的个数

In-place:占用常数内存,不占用额外内存

Out-place:占用额外内存

稳定性:排序后 2 个相等键值的顺序和排序之前它们的顺序相同

文档

冒泡排序算法

冒泡排序(Bubble Sort)也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。
推荐度:
为你推荐
资讯专栏
热门视频
相关推荐
选择排序算法 插入排序算法 希尔排序算法 归并排序算法 快速排序算法 堆排序算法 计数排序算法 桶排序算法 基数排序算法 排序算法 助人为乐的谚语和名言 春天的谚语 春分的谚语 团结的谚语 帮助人的谚语 谚语的意思 关于关爱的谚语 学习的名言 关于学习的名人名言 关于爱国的名言 清明的谚语 关于清明的谚语 清明节的谚语 珍惜时间的名言 愁的诗句 含雁的诗句 想念的诗句 牡丹花的诗句 带马字的诗句 关于思念的诗句 描写春天花朵的诗句 js中toString方法3个作用 python绘图中的四个绘图技巧 图像检索之基于vlfeat实现SIFT特征 Python按键或值对字典进行排序 提升Python运行速度的5个小技巧 学习python的while循环嵌套 分享15个超级好用得Python实用技巧 Python实现消消乐小游戏 python实现新年倒计时实例代码
Top