经典排序算法 - 冒泡排序

@date:2017-07-22 21:52:00

概述 #

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

特点:如果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

Build by Loppo 0.6.14