有序度：陣列中具有有序關系的元素對的個數
有序元素對:a[i] <= a[j]，如果i < j，
完全有序的陣列，有序度就是 n * (n - 1) /2（滿有序度）
逆序度 = 滿有序度 - 有序度
- 冒泡排序
-
特性
- 原地
- 穩定
- O(n**2)（最少0次交換，最多n*(n-1)/2次交換）
-
冒泡排序每次比較相鄰兩數，若為逆序則交換，所以冒泡排序交換次數總是確定的，即為逆序度，
-
-
插入排序
-
特性
- 原地
- 穩定
- O(n**2)（將一個資料插入陣列（O(n)），重復n次）
-
插入排序將陣列分為兩個區間：已排序區間和未排序區間，初始已排序區間只有一個元素，就是陣列首元素，每次取未排序區間元素在已排序區間中找到合適的位置插入，直到未排序區間為空，插入排序移動操作的次數是固定的，等于逆序度，
-
-
兩種排序演算法比較
-
雖然兩種排序演算法相同，都是原地、穩定排序，但插入排序要比冒泡排序更優
-
冒泡排序交換次數和插入排序資料移動次數一樣，都等于逆序度
-
冒泡排序資料交換需要3個賦值操作，而插入排序資料移動只需要1個，
-
冒泡排序和插入排序Java實作
public class Sort {
/**
* 冒泡排序
*
* @param arr
* @param n
*/
public static void bubbleSort(int arr[], int n) {
if (n <= 1) return;
int count = 0;
//最多進行n - 1次冒泡
for (int i = 0; i < n; i++) {
boolean swaped = false;
for (int j = 0; j < n - i - 1; j++) {
//每次比較相鄰數 把較大的放在后面
if (arr[j] > arr[j + 1]) {
int temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
swaped = true;
}
}
count++;
if (!swaped) break;
}
System.out.println("進行了" + count + "次冒泡");
}
/**
* 插入排序
*
* @param arr
* @param n
*/
public static void inserctionSort(int arr[], int n) {
if (n <= 1) return;
//將陣列分為已排序部分和未排序部分
for(int i = 1; i < n; i++) {
int value = https://www.cnblogs.com/codespoon/p/arr[i];//未排序部分的第一個值
int j = i - 1;
//每次將未排序部分的第一個值插入已排序部分中
for(; j >= 0; j--){
//尋找插入點 arr[j]為第一個小于等于value的值
if(arr[j] > value)
arr[j + 1] = arr[j];
else
break;
}
//將value插入到j后面
arr[j + 1] = value;
}
}
public static void sortTest() {
int arr[] = {3, 5, 4, 1, 2, 6};
printArr(arr);
inserctionSort(arr, arr.length);
printArr(arr);
}
public static void printArr(int arr[]) {
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/31076.html
標籤：其他
上一篇：2.鏈表