冒泡排序
冒泡排序算法運行起來非常慢，但在概念上它是排序算法中最簡單的，因此冒泡排序算法在剛開始研究排序技術(shù)時是一個非常好的算法。
冒泡排序原理即：從數(shù)組下標(biāo)為0的位置開始，比較下標(biāo)位置為0和1的數(shù)據(jù)，如果0號位置的大，則交換位置，如果1號位置大，則什么也不做，然后右移一個位置，比較1號和2號的數(shù)據(jù)，和剛才的一樣，如果1號的大，則交換位置，以此類推直至最后一個位置結(jié)束，到此數(shù)組中最大的元素就被排到了最后，之后再根據(jù)之前的步驟開始排前面的數(shù)據(jù)，直至全部數(shù)據(jù)都排序完成。
冒泡排序代碼
package com.java.demo;
import java.util.Random;
/*
* 數(shù)組排序冒泡排序：
*/
public class ArrayTest1 {
public static void main(String[] args) {
//創(chuàng)建一個數(shù)組
int[] arr = new int[5];
//創(chuàng)建隨機(jī)數(shù)對象
Random rd = new Random();
for (int i = 0; i < arr.length; i++) {
//獲取1-10的隨機(jī)數(shù)
int num = rd.nextInt(10)+1;
//對數(shù)組進(jìn)行賦值
arr[i] = num;
}
System.out.println("數(shù)組排序前：");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
//對數(shù)組進(jìn)行排序，冒泡排序
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length-1-i; j++) {
//進(jìn)行判斷，如果前面的大于后面是不是進(jìn)行互換，這里要用到中間變量
if (arr[j]>arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
System.out.println();
System.out.println("數(shù)組排序后：");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
}
}
冒泡排序原理圖
選擇排序
選擇排序原理即：在選擇排序中，不再只比較兩個相鄰的數(shù)據(jù)。因此需要記錄下某一個數(shù)據(jù)的下標(biāo)，進(jìn)行選擇排序就是把所有的數(shù)據(jù)掃描一遍，從中挑出（按從小到大排序）最小的一個數(shù)據(jù)，這個最小的數(shù)據(jù)和最左端下標(biāo)為0的數(shù)據(jù)交換位置。之后再次掃描數(shù)據(jù)，從下標(biāo)為1開始，還是挑出最小的然后和1號位置進(jìn)行交換，這個過程一直持續(xù)到所有的數(shù)據(jù)都排定。而程序中需要有一個標(biāo)識變量來標(biāo)識每次挑出最小數(shù)據(jù)的下標(biāo)。
選擇排序代碼
package com.java.demo;
import java.util.Random;
/*
* 數(shù)組排序選擇排序：
*/
public class ArrayTest2 {
public static void main(String[] args) {
// 定義一個數(shù)，動態(tài)初始化
int[] arr = new int[5];
// 創(chuàng)建生成隨機(jī)數(shù)的對象
Random rd = new Random();
// 對數(shù)組進(jìn)行賦值
for (int i = 0; i < arr.length; i++) {
// 獲取1-100的隨機(jī)數(shù)
int num = rd.nextInt(100) + 1;
arr[i] = num;
}
// 打印
System.out.println("數(shù)組未排序前：");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
// 對數(shù)組進(jìn)行排序，選擇排序
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
// 判斷
if (arr[i] > arr[j]) {
// 進(jìn)行互換
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
System.out.println();
// 打印
System.out.println("數(shù)組排序后：");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
選擇排序原理圖
冒泡排序和選擇排序效率
一般來說選擇排序效率比較高，因為只要交換一次，但是冒泡也可以只記錄坐標(biāo)然后做一次性變換，只是犧牲空間復(fù)雜度。但是冒泡有個很大的優(yōu)點就是它可以檢測整個數(shù)組是否已經(jīng)有序，當(dāng)某次遍歷沒有發(fā)生任何交換的時候你就可以提前終止了。也算是個小優(yōu)化吧。
