用氣泡排序法求閏年

IT科技
關注：1.98W次

排序演算法是《資料結構與演算法》中最基本的演算法之一。排序演算法可以分為內部排序和外部排序，內部排序是資料記錄在記憶體中進行排序，而外部排序是因排序的資料很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內部排序演算法有：插入排序、希爾排序、選擇排序、氣泡排序、歸併排序、快速排序、堆排序、基數排序等。以下是氣泡排序演算法：

氣泡排序（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, 89, 50, 37, 5, 64, 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, 89, 50, 37, 5, 64, 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 listimport threadingfrom 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 個相等鍵值的順序和排序之前它們的順序相同

標籤：閏年氣泡排序法求

文章版權屬於文章作者所有，轉載請註明 https://shqsg.com/dianzi/9rgkyl.html

當前位置：生活全書館 >

IT科技