十大經典排序演算法(2022年11月12日更新)
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) - 穩定情況：
不穩定，
3、插入排序
插入排序的演算法描述是一種簡單直觀的排序演算法，
3.1 方法描述
大致排序方法與選擇排序方法相似，仍然是把將排序的陣列分為兩個區，無序區和有序區，先把第一個元素列為有序區，拿出無序區第一個元素與有序區的元素進行比較，若小于(大于)有序區的元素，則將它插入該元素的后一個位置，所以，每進行一次操作，無序區減少一個元素，而有序區增加一個元素，回圈上面的操作，直到無序區元素為空，則停止該操作，輸出有序陣列，
3.2 演算法描述
- 從第一個元素開始，該元素默認為有序區，
- 取出下一個元素，在有序區從后向前掃描，
- 如果有序區的元素大于(小于)新元素，將該元素移到下一個位置，
- 重復上述三步，直到無序區為空為止，輸出有序陣列，
3.3 動圖描述
3.4 代碼實作(Java語言)
package Sort;
import java.util.Scanner;
public class InsertSort {
public static int[] InsertSort(int[] array) {
if (array.length == 0){
return array;
}
int current ; // 臨時變數 插入的數
for (int i = 0; i < array.length - 1; i++){
current = array[i+1]; // 每次回圈 將無序區的第一個元素當作插入的數，也就是賦值給current 當作臨時變數
int perIndex = i; // 有序區的最后一個元素的索引值
// 若有序區的最后一個元素的索引值大于等于0 且要插入的數小于有序區的最后一個元素的索引值，就進入這個while回圈，這個回圈的目的是為了保持current可以從后向前依次比較，執行第一次while回圈，說明current的值一定小于有序區的最后一個元素，所以將最后一個元素賦值給后一個元素，將preIndex的值減一，再次進行while回圈的判斷，
while (perIndex >= 0 && current < array[perIndex]){
// 這步操作是為了保證有空余的地方給元素插入，且有序區的最后一個元素仍然是最后一個元素，但是插入元素后，索引值會加一，
array[perIndex + 1] = array[perIndex];
perIndex--;
}
/**
*跳出while回圈后，有兩種情況：
* 1、有序區的所有值都比較完成，則perIndex為-1，則將
*current的值直接插入有序區的第一個位置，也就是索引為0，故
*(-1+1).
* 2、有序區的所有值沒有比較結束，在中途發現了不滿足條件的，
*跳出回圈，那就之間將current插入比較完成的索引的后面位置，故
*(preIndex+1).
*/
array[perIndex + 1] = current;
}
//for回圈結束，陣列排序完成，回傳結果，
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[] insertSort = InsertSort(arr);
System.out.println("從小到大排序為：");
for (int i:insertSort) {
System.out.print(i+" ");
}
}
}
3.5 演算法分析
- 最佳情況:
O(n) - 最壞情況：
O(n2) - 平均情況：
O(n2)
4、希爾排序
希爾排序也是一種插入排序，它是簡單插入排序經過改進之后的一個更高效的版本，也可以稱為縮小增量排序，
4.1 方法描述
首先確定增量序列，在希爾排序中建議一種增量序列，在大多數的希爾排序中，通常使用該種增量序列，故稱為希爾增量，但這個增量并不是最優的，希爾增量：gap = length / 2，縮小增量繼續以 gap = length / 2的方式，故增量序串列示為 {n/2，(n/2)/2，……，1}.每一次排序，按照gap的數字來分組，對每組使用直接插入排序演算法排序，隨著增量的逐漸減少，每組包含的元素就越多，當增量降至一時，每個元素全部被分為一組，演算法終止，
4.2 演算法描述
- 確定增量序列，{n/2，(n/2)/2，……，1}.
- 按增量序列，對序列進行排序，
- 每趟排序，根據對應的增量，將待排序列分割成若干長度的子序列，分別對各子序列進行直接插入排序，僅增量為1時，整個序列作為一個子序列來處理，
4.3 動圖描述
4.4 代碼實作
package Sort;
import java.util.Scanner;
public class ShellSort {
public static int[] ShellSort(int[] array) {
int len = array.length; // 陣列長度
int temp = 0; // 中間值，臨時變數
int gap = len / 2; // 希爾增量
while (gap > 0){
// 未排序的陣列每一個元素都要依次被放到子序列中，進行排序
for (int i = gap; i < len; i++){
temp = array[i]; //將每個子序列中的元素賦值給臨時變數，執行插入排序，
int preIndex = i - gap; // 子序列中temp前面的那個元素的索引
// 子序列進行插入排序，程序于插入排序相似，具體可以看上面插入排序詳解，
while (preIndex >= 0 && array[preIndex] > temp){
array[preIndex + gap] = array[preIndex];
preIndex -= gap;
}
array[preIndex + gap] = temp;
}
// 增量除2，進行下次回圈，
gap /= 2;
}
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[] ints = ShellSort(arr);
for (int i:ints) {
System.out.print(i + " ");
}
}
}
4.5 演算法分析
-
最佳情況：
O(nlog2 n) -
最壞情況：
O(nlog2 n)
-
平均情況：
O(nlog2 n)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/531925.html
標籤：其他