經典排序算法 - 冒泡排序 - 52fhy－IT工程師數位筆記本

文章出處

概述

冒泡排序的基本思想是，對相鄰的元素進行兩兩比較，順序相反則進行交換，這樣，每一趟會將最小或最大的元素“浮”到頂端，最終達到完全有序。

特點：如果N個元素按照從小到大排序，每一輪(i)排序后，最大的元素會放到最后，后續新一輪只需要前N-i個元素互相比較。

題目：給出無需數組 [4,3,1,2]，要求按照從小到大使用冒泡排序法排序。
輸出樣例：

排序過程：
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)