经典排序算法 – 冒泡排序

c/c++

浏览数:118

2019-9-15

AD:资源代下载服务

概述

冒泡排序的基本思想是,对相邻的元素进行两两比较,顺序相反则进行交换,这样,每一趟会将最小或最大的元素“浮”到顶端,最终达到完全有序。

特点:如果N个元素按照从小到大排序,每一轮(i)排序后,最大的元素会放到最后,后续新一轮只需要前N-i个元素互相比较。

题目:给出无需数组 [4,3,1,2],要求按照从小到大使用冒泡排序法排序。
输出样例:

1
2
3
4

排序过程:
1) 第1趟排序:

3,4,1,2
3,1,4,2
3,1,2,4

最大的元素拍到最后,后续无需拿出比较。
2) 第2趟排序:

1,3,2,4
1,2,3,4

3也冒泡到倒数第二的位置了。
3) 第3趟排序:

1,2,3,4

至此冒泡排序结束,共进行6次。

C语言实现

#include<stdio.h>

#define MAX 4
void bubble_sort(int *, int);
void bubble_sort2(int *, int);//优化的冒泡排序 

int main(){
    
    
    int arr[MAX] = {4,3,1,2};   
    bubble_sort2(arr, MAX);
    
    int i;
    for(i =0; i< MAX; i++){
        printf("%d\n", arr[i]);
    }
    
    return 0;
}

void bubble_sort(int *arr, int n){
    int i,j,temp;
    int c=0; //计数用,可忽略 
    for(i=0; i< n; i++){
        for(j=1; j< n-i; j++){//新一轮只需要比较到n-i 位置即可 
            if(arr[j-1] > arr[j]){
                temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
            }
            c++;
        }
    }
    printf("共排序%d次\n", c);
}

/**
* 优化的冒泡排序 
*/
void bubble_sort2(int *arr, int n){
    int i,j,temp;
    int c=0; 
    int flag = 1;//默认是需要进行新一轮冒泡的 
    for(i=0; i< n && flag; i++){
        flag = 0;//假设后续不需要进行新一轮冒泡
        for(j=1; j< n-i; j++){//新一轮只需要比较到n-i 位置即可 
            if(arr[j-1] > arr[j]){
                temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
                flag = 1;//由于存在元素交换,说明元素并未排序完成,准备新一轮冒泡
            }
            c++;
        }
    }
    printf("共排序%d次\n", c);
}

示例代码里提供了优化的冒泡排序。例如当数组是[1,2,3,4]时,只需要冒泡一趟,执行3次就行了;普通冒泡还会执行6次。

C++

#include<iostream>

using namespace std;

#define MAX 4
void bubble_sort(int *, int);
int main(){
    int arr[MAX] = {4,3,1,2};
    
    bubble_sort(arr, MAX);
    
    int i;
    for(i =0; i< MAX; i++){
        printf("%d\n", arr[i]);
    }
    
    return 0;
}

void bubble_sort(int *arr, int n){
    int i,j,temp;
    int c=0; 
    int flag = 1;
    for(i=0; i< n && flag; i++){
        flag = 0;
        for(j=1; j< n-i; j++){
            if(arr[j-1] > arr[j]){
                temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
                flag = 1;
            }
            c++;
        }
    }
    cout << "共排序" << c << "次\n";
}

PHP实现

$arr = [4,3,1,2];

function bubble_sort(&$arr){
    $len = count($arr);
    for($i=0; $i<$len; $i++){
        for($j=1; $j<$len-$i ; $j++){
            //从小到大
            if($arr[$j] < $arr[$j-1]){
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j-1];
                $arr[$j-1] = $tmp;
            }
        }
    }
}

function bubble_sort2($arr){
    $len = count($arr);
    $flag = 1;
    for($i=0; $i<$len && $flag; $i++){
        $flag = 0;
        for($j=1; $j<$len-$i ; $j++){
            //从小到大
            if($arr[$j] < $arr[$j-1]){
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j-1];
                $arr[$j-1] = $tmp;
                $flag=1;
            }
        }
    }
    return $arr;
}

bubble_sort($arr);
print_r($arr);

运行:

php -f main.php

Go实现

package main

import "fmt"

func main(){
    
    var arr = []int{4,3,1,2};//注意这里不是array,是slice切片。切片属于引用类型
   
    bubble_sort(arr);
    
    printArr(arr);
}

func bubble_sort(arr []int){
    var i,j int;
    //var temp int;
    n := len(arr);
    flag := 1;
    
    for i=0;i<n && flag == 1;i++ {
        flag = 0;
        for j=1;j<n-i;j++ {
            if arr[j-1] >= arr[j]{//swap
                //temp = arr[j-1];
                //arr[j-1] = arr[j];
                //arr[j] = temp;
                arr[j-1],arr[j] = arr[j],arr[j-1];
                flag = 1;
            }
        }
    }
}

func printArr(arr []int){
    var i int;
    
    for i=0;i<len(arr);i++ {
        fmt.Println(arr[i]);
    }
}

运行:

go run main.go

JavaScript

var arr = [4,3,1,2];

function bubble_sort(arr){
    var len = arr.length;
    var flag = 1;
    for(var i=0; i<len && flag; i++){
        flag = 0;
        for(var j=1; j<len-i ; j++){
            //从小到大
            if(arr[j] < arr[j-1]){
                tmp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = tmp;
                flag=1;
            }
        }
    }
    return arr;
}

arr = bubble_sort(arr);
console.log(arr);

Java实现

public class BubbleSort{
    
    public static void main(String[] args){
        int[] arr = {4,3,1,2};
        sort(arr);
        
        for(int i=0; i<arr.length; i++){
            System.out.println(arr[i]);
        }
    }
    
    public static void sort(int[] arr){
        int len = arr.length;
        int temp;
        int flag = 1;
        for(int i=0; i<len && flag==1; i++){
            flag = 0;
            for(int j=1;j<len-i; j++){
                if(arr[j-1] > arr[j]){
                    temp = arr[j-1];
                    arr[j-1] = arr[j];
                    arr[j] = temp;
                    flag = 1;
                }
            }
        }
    }
}

运行:

$ javac BubbleSort.java
$ java BubbleSort
1
2
3
4

Python3实现

#!/usr/bin/python3

def bubble_sort(arr):
    n = len(arr)
    flag = 1
    
    i=0
    while i < n :
        flag = 0
        j=1
        while j < n-i:
            if arr[j-1] >= arr[j]:
                temp = arr[j-1]
                arr[j-1] = arr[j]
                arr[j] = temp
                flag = 1
            j = j+1
        i = i+1
    
arr = [4,3,1,2]
bubble_sort(arr)
for x in arr:
    print(x)

运行:

python main.py

参考:
图解排序算法(一)之3种简单排序(选择,冒泡,直接插入) – dreamcatcher-cx – 博客园
http://www.cnblogs.com/chengxiao/p/6103002.html

作者:飞鸿影