十大經典排序演算法(2022年11月11日更新)
1、冒泡排序
冒泡排序是接下來的十大排序中最簡單的排序，
1.1 方法描述
簡單來說，排序方法就是重復地走過要排序的數列，一次比較相鄰的兩個元素，如果順序不滿足從小到大(從大到小)，就將這兩個元素交換，重復地進行，知道沒有再需要交換，排序方式：In-place（需要申請額外空間-臨時變數）
1.2 演算法描述
- 從第一個元素開始比較，比較相鄰的元素，如果第一個比第二個大(小)，就交換他們兩個，
- 對每一對相鄰元素做同樣的作業，不斷重復，直到排序完成，
1.3 動圖描述
1.4 代碼實作(Java語言)
- 從小到大排序：
package Sort; // 自己定義的包
import java.util.Scanner; // 匯入的外部jar包
public class BubbleSort {
public static void main(String[] args) {
/**
* 從小到大排序：
*/
System.out.println("請輸入十個數：");
Scanner sc = new Scanner(System .in);
int [] arr = new int[10];
// 陣列輸入方法:(for回圈)
for (int i = 0;i < arr.length;i++){
arr[i] = sc.nextInt();
}
// 雙層for回圈，第一層回圈為每個數除了最后一個數，都要進行黨的的一遍回圈，故回圈次數為（arr.length - 1）次.
for (int i = 0; i <arr.length;i++){
for (int j = 0;j<arr.length-i-1;j++){
// 若兩數相比，前數比后數大，因為從小到大排序，故將兩個數進行交換，交換需要一個臨時變數，用來當中介，進行交換，
if (arr[j+1] < arr[j]){
int temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
System.out.println("從小到大排序為：");
// 使用foreach回圈進行輸出已排序好的陣列，
for (int i:arr) {
System.out.print(i+" ");
}
}
}
- 從大到小排序：
package Sort; // 自己定義的包
import java.util.Scanner; // 匯入的外部jar包
public class BubbleSort {
public static void main(String[] args) {
/**
* 從大到小：
*/
System.out.println("請輸入十個數：");
Scanner scanner = new Scanner(System.in);
int [] arr = new int[10];
for(int i = 0;i <arr.length;i++){
arr[i] = scanner.nextInt();
}
for (int i = 0;i < arr.length; i++){
for (int j = 0; j < arr.length - i - 1; j++){
// 從大到小和從小到大排序基本相同，只有接下來交換的部分，當兩數進行比較時，后數大于前數時，進行交換，
if (arr[j+1] > arr[j]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
System.out.println("從大到小為：");
for (int i:arr ) {
System.out.print(i+" ");
}
}
1.5 演算法分析
- 最好情況-- O(n)：
初始陣列就為從大到小(從小到大)，只需要比較 O(n)，n為陣列的元素， - 最壞情況--O(n2)：
若需要陣列為從小到大排序，初始陣列為從大到小，最壞的情況就是初始陣列為倒序排序，故最壞情況為 O(n2)，所以復雜度為 O(n2) - 穩定性：
穩定，
2、選擇排序
選擇排序是表現最穩定的排序演算法之一，
2.1 方法描述
首先在未排序的序列中找到最小(大)元素，存放到排序序列中的起始位置，然后，再從剩余未排序的元素中繼續找最小(大)元素，然后存放到已排序序列的末尾，一次類推，直到所有元素均排序完成，
2.2 演算法描述
n個元素的通過直接選擇排序經過n-1次選擇排序得到有序結果，
- 將陣列分為無序區和有序區，初始無序區為所有未排數，有序區為空，
- 第 i 趟排序開始時，當前有序區為[1~i-1]，無序區為[i ~ n]，每趟排序從當前無序區找出最小(最大)元素，將他與 無序區的第一個元素交換，每一趟排序，無序區減少一個元素，而有序區增加一個元素，
- n-1趟結束，陣列排序結束，
2.3 動圖描述
2.4 代碼實作(Java語言)
package Sort;
import java.util.Scanner;
public class SelectionSort {
public static int[] SelectionSort(int[] array) {
if (array.length == 0){
return array;
}
for (int i = 0;i < array.length; i++){
int minIndex = i;
for (int j = i; j < array.length; j++){
if (array[j] < array[minIndex]){ // 找到最小的數
minIndex = j; // 將最小的數的索引保存
}
}
// 將找到的最小數與無序區的第一個數進行交換
int temp = array[minIndex];
array[minIndex] = array[i];
array[i] = temp;
}
return array;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("請輸入十個數：");
int [] arr = new int[10];
for (int i = 0;i < arr.length; i++){
arr[i] = scanner.nextInt();
}
int[] sort = SelectionSort(arr);
System.out.println("從小到大排序為：");
for (int i:sort) {
System.out.print(i+" ");
}
}
}
2.5 演算法分析
- 最佳情況：
O(n2) - 最壞情況：
O(n2) - 穩定情況：
不穩定，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/531822.html
標籤：其他
上一篇：Python第十章實驗報告
下一篇：回溯演算法解數獨問題