冒泡排序

冒泡排序基本思想

---

 冒泡排序法是最经典，最基础的排序算法之一，该算法稳定性较好。

• 时间复杂度： O(n^2)
• 空间复杂度： O(1)

 通过依次对待排序序列从前至后(1)，依次对相邻两个元素的值进行比较，如果前者比后者大则交换，致使较大的元素逐渐移动至后部，如同水下气泡向上冒一样。

1. 从下标较小的元素开始

实现原理

原始数据

第一轮比较

• 第一轮比较后，数据[5，4，2，7，3] 变成了 [4，2，5，3，7]，并且将最大的数7移动到了该数据串的顶端。

第二轮比较

• 第二轮比较结束后，第二大的数字5，被移动到了7的后面。

第三轮比较

• 第三轮比较结束后，第三大的数字4，被移动到了5的后面。

第四轮比较

• 第四轮比较结束后，确定了所有数字的排序。

程序实现

---

C++Java

/*
*   Bubbling Sort to Java
*   Designers by JRNitre
* */
#include <iostream>
using namespace std;

// 数组大小
int max_number = 4;

// 输出打印数组
void OutPut_Array(int data[]){
    int Temp;
    cout << "[";
    for (Temp = 0; Temp < max_number; Temp++){
        cout << data[Temp] << ",";
    }
    cout << "]" << endl;
}

int main() {
    // 迭代变量
    int i,j;
    // 临时变量
    int Temp;
    // 待排序数组
    int Number_List[max_number] = {5, 4, 2, 7, 3};

    // 排序前数组输出
    cout << "Pre-Sort:" << endl;
    OutPut_Array(Number_List);

    // 两层for嵌套实现循环对比
    for (i = 0; i < max_number; i++){
        for (j = 0; j < max_number - i; j++){
            // 判断前后两数大小
            if(Number_List[j] > Number_List[j+1]){
                // 交换两数位置
                Temp = Number_List[j];
                Number_List[j] = Number_List[j+1];
                Number_List[j+1] = Temp;
            }
        }
    }

    // 排序后结果输出
    cout << "After-Sort:" << endl;
    OutPut_Array(Number_List);

    system("pause");
    return 0;
}

/*
*   Bubbling Sort to Java
*   Designers by JRNitre
* */

import static java.lang.System.*;
import java.util.Scanner;

public class BubblingSort {
    // Data Array Max
    public static final int MAXSIZE = 10;

    public static void main (String[] args) {
        // Iteration Var
        int i,j,temp;
        Scanner input = new Scanner(in);
        // Data Array
        int [] Array;
        Array = new int[MAXSIZE];

        // Loop Input
        out.println("Pleas input ArrayData: ");

        for (i = 0; i < MAXSIZE; i++){
            out.print("[" + i + "] = ");
            Array[i] = input.nextInt();
        }

        // Print BeforeSort Array
        out.println("Bef-Sort:");
        out.print("[");
        for (i = 0; i < MAXSIZE; i++){
            out.print(Array[i]);
            if (i+1 != MAXSIZE){
                out.print(", ");
            }
        }
        out.println("]");

        // Bubbling Sort
        for (i = 1; i < MAXSIZE; i++){
            for (j = 0; j < MAXSIZE - i; j++){
                if (Array[j] > Array[j+1]){
                    temp = Array[j];
                    Array[j] = Array[j+1];
                    Array[j+1] = temp;
                }
            }
        }

        // Print AfterSort Array
        out.println("\nAfter-Sort:");
        out.print("[");
        for (i = 0; i < MAXSIZE; i++){
            out.print(Array[i]);
            if (i+1 != MAXSIZE){
                out.print(", ");
            }
        }
        out.println("]");
    }
}

C++ 程序实现效果

• 若想实现从大到小排序，则仅需更改判断条件即可

    for (i = 0; i < max_number; i++){
        for (j = 0; j < max_number - i; j++){
            // 判断前后两数大小
            if(Number_List[j] < Number_List[j+1]){
                // 交换两数位置
                Temp = Number_List[j];
                Number_List[j] = Number_List[j+1];
                Number_List[j+1] = Temp;
            }
        }
    }

实现效果