冒泡排序法是如何排序的???

发布网友发布时间：2022-04-24 09:57

共9个回答

好二三四时间：2022-05-22 05:04

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

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

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

说并没有什么太大作用。

1. 算法步骤

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

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

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

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

2. 动图演示

3. 什么时候最快

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

4. 什么时候最慢

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

5. JavaScript 代码实现

实例

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 arr

7. 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 代码实现

实例

10. C 语言

实例

#include <stdio.h>
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, , 50, 37, 5, , 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 <iostream>
using namespace std;
template<typename T> //整数或浮点数皆可使用,若要使用类(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] << <<endl;
return 0;
}

12. C#

实例

static void BubbleSort(int[] intArray) {
int temp = 0;
bool swapped;
for (int i = 0; i < intArray.Length; i++)
{
swapped = false;
for (int j = 0; j < intArray.Length - 1 - i; j++)
if (intArray[j] > 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
end
end

puts [22, 34, 3, 32, 82, 55, , 50, 37, 5, , 35, 9, 70].bubble_sort!

14. Swift

实例

import Foundation

func bubbleSort (arr: inout [Int]) {
for i in 0..<arr.count - 1 {
for j in 0..<arr.count - 1 - i {
if arr[j] > 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 个相等键值的顺序和排序之前它们的顺序相同

热心网友时间：2022-05-22 02:12

冒泡排序算法的原理：

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

2、对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

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

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

扩展资料：

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

算法稳定性：

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

参考资料：百度百科-冒泡排序法

热心网友时间：2022-05-22 03:30

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

冒泡排序算法的原理如下：

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

对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

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

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

扩展资料：

举例：C语言

#include<stdio.h>

#define ARR_LEN 255/*数组长度上限*/

#define elemType int/*元素类型*/

/*冒泡排序*/

/*1.从当前元素起，向后依次比较每一对相邻元素，若逆序则交换*/

/*2.对所有元素均重复以上步骤，直至最后一个元素*/

/*elemType arr[]:排序目标数组;int len:元素个数*/

void bubbleSort(elemType arr[],int len){

elemType temp;

int i,j;

for(i=0;i<len-1;i++)/*外循环为排序趟数，len个数进行len-1趟*/

for(j=0;j<len-1-i;j++){/*内循环为每趟比较的次数，第i趟比较len-i次*/

if(arr[j]>arr[j+1]){/*相邻元素比较，若逆序则交换（升序为左大于右，降序反之）*/

temp=arr[j];

arr[j]=arr[j+1];

arr[j+1]=temp;

}

int main(void){

elemType arr[ARR_LEN]={3,5,1,-7,4,9,-6,8,10,4};

int len=10;

int i;

bubbleSort(arr,len);

for(i=0;i<len;i++)

printf("%d\t",arr<i>);

putchar('\n');

return 0;

}

参考资料：

百度百科——冒泡排序

热心网友时间：2022-05-22 05:04

扩展资料：

时间复杂度

若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数

和记录移动次数

次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：

热心网友时间：2022-05-22 06:56

其实很简单，就是一个一个进行对比如果a<b/a>b就把两个变量进行交换,使得最大/最小的排在前面。
2 4 3 5 1 五个数
2<4 交换成为 42351
2<3 成为 43251
2<5 成为 43521
2>1 不交换 43521
然后最小的1就一定会在最后
然后比较前4个数，4>3,3<5(交换),3>2;
成为45321，
前3个数4<5（交换）,4>3
就成为了54321
这是一个巧合的例子，程序应该还要比较前两个数
5>4
最后成为54321。
以下是样例程序。

#include<stdio.h>
int main()
{
int a[5]={2,4,3,5,1};
int i,j,t; //i,j是计数器，t用作交换
for(i=0;i<5;i++)
{
for(j=0;j<5-i-1;j++)
{
if(a[j]<a[j+1]) //如果后面的数字大于前面的数字
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t; //就把两个数交换
}
}
}
printf("%d %d %d %d %d\n",a[0],a[1],a[2],a[3],a[4]);
return 0; //程序正常结束
}

你懂了么？

热心网友时间：2022-05-22 09:04

比如有一组数为12,23,1,4,2,6。需要使用冒泡排序方法使这组数从小到大排列。首先12和23比较，12<23，则位置不变；接着23和1比较，因为23>1，所以交换23和1的位置，这组数这时是12 1 23 4 2 6；然后比较23和4，因为23>4，所以交换23和4，这组数变为12 1 4 23 2 6；然后比较23和2，23>2，再交换，变为12 1 4 2 23 6；然后比较23和6,23>6,再交换，最后为12 1 4 2 6 23。这就叫经过了一趟排序，即相邻两数比较，大的放在后面，经过一趟排序后，最大的数就冒泡到最后面了。然后再对前n-1个数进行第二趟排序，排序后第二大的数就放在了第n-1个位置；最后经过n-1趟排序后整个数组就有序了。

热心网友时间：2022-05-22 11:28

冒泡排序算法的原理如下：

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

对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

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

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

热心网友时间：2022-05-22 14:10

用两层循环，比较两个数大小，按要求，大数或者小数在前排序，注意二层循环中，J=i

热心网友时间：2022-05-22 17:24

冒泡就是大的数，比较之后放到最前面，一次类推

全部栏目