寫(xiě)在前面
- 樓主整理經(jīng)典的排序算法
- 記錄學(xué)習(xí)
1. 冒泡排序(Bubble Sort)
1.1 概念
冒泡排序是一種簡(jiǎn)單的排序算法。它重復(fù)地走訪過(guò)要排序的數(shù)列福也，一次比較兩個(gè)元素局骤，如果它們的順序錯(cuò)誤就把它們交換過(guò)來(lái)。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換暴凑，也就是說(shuō)該數(shù)列已經(jīng)排序完成峦甩。這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。
1.2 算法描述
- 比較相鄰兩個(gè)元素现喳，如果第一個(gè)比第二個(gè)大凯傲，就交換位置
- 對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)嗦篱，最后的元素就是最大的數(shù)
- 針對(duì)所有的元素重復(fù)以上的步驟泣洞，除了最后一個(gè)
- 重復(fù)步驟1~3，直到排序完成
示意圖
1.3 代碼演示
package com.zhuang.algorithm;
/**
* @Classname BubbleSort
* @Description 冒泡排序
* @Date 2021/6/13 14:04
* @Created by dell
*/
public class BubbleSort {
public static void main(String[] args) {
int[] arr =new int[]{0,5,6,1,8,2};
bubbleSort(arr);
System.out.println(Arrays.toString(arr));//[0, 1, 2, 5, 6, 8]
}
public static void bubbleSort(int[] arr) {
int temp=0;
if (arr.length == 0) {
return;
}
//每次需要排序的長(zhǎng)度
for(int i=arr.length - 1; i >= 0; i--){
//從第一個(gè)元素到第i個(gè)元素
for (int j = 0; j < i; j++) {
if (arr[j]>arr[j+1]){
temp = arr[j];
arr[j]=arr[j+1];
arr[j+1] = temp;
}
}
}
}
}
1.4 算法分析
- 最佳情況：T(n) = O(n)
- 最差情況：T(n) = O(n2)
- 平均情況：T(n) = O(n2)
1.5 穩(wěn)定性
在相鄰元素相等時(shí)默色，它們并不會(huì)交換位置球凰，所以狮腿，冒泡排序是穩(wěn)定排序。
1.6 適用場(chǎng)景
冒泡排序思路簡(jiǎn)單呕诉，代碼也簡(jiǎn)單缘厢，特別適合小數(shù)據(jù)的排序。但是甩挫，由于算法復(fù)雜度較高贴硫，在數(shù)據(jù)量大的時(shí)候不適合使用。
