目錄
一、如何分析一個排序算法？
1、算法的執行效率
2、排序算法的記憶體消耗
3、排序算法的穩定性
二、冒泡排序
一、冒泡排序原理
二、性能分析
三 、代碼實作
三、插入排序
一、排序原理
二、性能分析
三、代碼實作
四、選擇排序
一、排序原理
二、性能分析
三、代碼實作
問題：插入和冒泡複雜度都是O(n2)，為什麼實際開發中更傾向與插入算法呢？
一、如何分析一個排序算法？
1、算法的執行效率
- 最好情況，最壞情況，平均時間複雜度
- 時間複雜度的系數，常數，低階。在實際開發中有能資料規模很小，是以在對同一階時間複雜度的排序算法分析時，就要考慮到 系數，常數，低階
- 比較次數和交換次數
2、排序算法的記憶體消耗
原地排序算法：特指空間複雜度是O(1)的排序算法。如，冒泡，插入，選擇
3、排序算法的穩定性
穩定性：如果待排序的序列中存在值相等的元素，經過排序之後，相等元素之間的先後位置順序不變
相同值元素，哪個在前在後什麼關系，為什麼考慮算法的穩定性？
實際開發中，要排序的往往是一組對象，需要按照對象的key來排序
例如:
先按照下單時間給訂單排序，排序完成後用穩定排序算法按照訂單金額重新排序。保證了相同值的資料按照下單時間排序
二、冒泡排序
一、冒泡排序原理
1、冒泡排序隻操作相鄰兩個資料
2、對相鄰資料進行比較，看關系是否滿足要求，不滿足則交換
3、一次冒泡排序至少讓一個元素到它應在的位置，重複n次，就完成了排序
4、排序優化，如果某次冒泡不存在資料交換，則說明已經達到完全有序，是以終止冒泡
如果按照從小到大排序，每一次冒泡都比較相鄰的資料，如果前者大于後者就互相交換，一次冒泡結束，最大的值就到了最後。第二次冒泡将第二大的值移動到最後倒數第二位，重複數組長度-1次，就可以達到有序
二、性能分析
冒泡排序是原地排序算法：冒泡的過程隻涉及到資料的交換，隻需要常量級的臨時空間，是以空間複雜度為O(1)
冒泡排序是穩定的排序算法：相同大小的資料不進行交換，不改變順序
冒泡排序的時間複雜度：
- 最好時間複雜度 ：O(n) 1次冒泡
- 最壞時間複雜度：O(n2) 6次冒泡
平均時間複雜度O(n2)分析：
1、有序度：有序元素對：a[i] <= a[j], 如果 i < j。
倒序的數組有序度為0。完全有序的數組 1，2，3，4，5，6，有序度為n*(n-1)/2,就是15 。這種完全有序的數組的有序度叫滿有序度
2、逆序度：逆序元素對：a[i] > a[j], 如果 i < j。
公式：逆序度 = 滿有序度 - 有序度 排序的過程就是增加有序度，減少逆序度的過程，最好達到滿有序度，說明排序完成
例如：
4，5，6，3，2，1 滿有序度為15，初始有序度為3.每交換一次資料有序度+1.需要交換的次數一定的,為逆序度 15-3=12 進行12次交換資料
對于n個資料進行冒泡排序，平均交換次數？
最好情況，初始有序度為n*(n-1)/2，不需要交換資料，最壞情況，初始有序度為0，需要交換n*(n-1)/2次資料。我們取平均值為n*(n-1)/4
比較操作肯定要比交換操作多，而複雜度的上限是 O(n2)，是以平均時間複雜度為O(n2)
三 、代碼實作
/**
* 冒泡排序
* @author chao
*/
public class Bubble_Sort {
public static void main(String[] args) {
int[] arrays = {3,5,4,1,2,6};
Bubble_Sort.sort(arrays, arrays.length);
System.out.println(Arrays.toString(arrays));
}
public static void sort(int[] arrays,int n) {
for (int i = 0; i < n-1 ; i++) {
boolean flag= false; //用來判斷有木有交換資料
for (int j = 0; j < n-i-1; j++) {
if(arrays[j+1] < arrays[j]) {
int temp = arrays[j];
arrays[j]=arrays[j+1];
arrays[j+1]=temp;
flag=true;
}
}
//如果沒有交換資料就跳出循環
if(!flag){
break;
}
}
//嚴蔚民書上的僞代碼實作
// boolean flag = true;
// for (int i = n-1; i >0 && flag; i--) {
// flag=false;
// for (int j = 0; j < i; j++) {
// if(arrays[j+1] < arrays[j]) {
// int temp = arrays[j];
// arrays[j]=arrays[j+1];
// arrays[j+1]=temp;
// flag=true;
// }
// }
//
// }
}
}
/**
* 向下冒泡排序
* @author chao
*/
public class Bubble_Sort2 {
public static void main(String[] args) {
int[] arrays = { 3, 2, 6, 4, 5, 1 };
Bubble_Sort2.sort(arrays, arrays.length);
System.out.println(Arrays.toString(arrays));
}
/**
* 向下冒泡。可能比冒泡更易懂？
*
* 算法概要：
* 從0開始，用這個元素去跟後面的所有元素比較，如果發現這個元素大于後面的某個元素，則交換。
* 3 2 6 4 5 1
* 第一趟是從 index=0 也就是 3， 開始跟index=1及其後面的數字比較
* 3 大于 2，交換，變為 2 3 6 4 5 1，此時index=0的位置變為了2
* 接下來将用2跟index=2比較
* 2 不大于 6 不交換
* 2 不大于 4 不交換
* 2 不大于 5 不交換
* 2 大于 1，交換，變為 1 3 6 4 5 2，第一趟排序完成。
*
* 第二趟是從 index=1 也就是 3，開始跟index=2及其後面的數字比較
* 3 不大于 6 不交換
* 3 不大于 4 不交換
* 3 不大于 5 不交換
* 3 大于 2，交換，變為 1 2 6 4 5 3，第二趟排序完成。
*
* 第三趟是從 index=2 也就是 6，開始跟index=3及其後面的數字比較
* 6 大于 4，交換，變為 1 2 4 6 5 3, 此時 index = 2 的位置變為了4
* 接下來将用4跟index=4比較
* 4 不大于 5 不交換
* 4 大于 3，交換，變為 1 2 3 6 5 4，第三趟排序完成。
*
* 第四趟是從 index=3 也就是 6，開始跟index=4及其後面的數字比較
* 6 大于 5，交換，變為 1 2 3 5 6 4, 此時 index = 3 的位置變為了5
* 接下來将用5跟index=5比較
* 5 大于 4，交換，變為 1 2 3 4 6 5, 第四趟排序完成。
*
* 第五趟是從 index=4 也就是 6，開始跟index=5及其後面的數字比較
* 6 大于 5，交換，變為 1 2 3 4 5 6, 此時 index = 4 的位置變為了5
* 接下來将用5跟index=6比較
* index = 6 已經不滿足 index < length 的條件，整個排序完成。
*/
public static void sort(int[] arrays, int n) {
if (arrays.length == 1)
return;
for (int i = 0; i < arrays.length - 1; i++) {
for (int j = i + 1; j < arrays.length; j++) {
if (arrays[i] > arrays[j]) {
int temp = arrays[i];
arrays[i] = arrays[j];
arrays[j] = temp;
}
}
}
}
}
三、插入排序
一、排序原理
首先，我們将數組中的資料分為2個區間，即已排序區間和未排序區間。初始已排序區間隻有一個元素，就是數組的第一個元素。插入算法的核心思想就是取未排序區間中的元素，在已排序區間中找到合适的插入位置将其插入，并保證已排序區間中的元素一直有序。重複這個過程，直到未排序中元素為空，算法結束
如上圖，左側為已排序區間，右邊為未排序區間。每次取未排序區間的元素，如取圖中1，和左側進行一一比較尋找合适的位置，将前面的元素依次後移給 1 騰出空間。
移動次數等于逆序度: 例如上圖 初始有序度為5，滿有序度為15，逆有序度為10=3+3+4
二、性能分析
原地排序算法：不需要額外的存儲空間
穩定排序算法：值相同的元素，将後面出現的元素，插入到前面出現元素的後面，保持原有前後順序不變
插入排序的時間複雜度：
- 最好時間複雜度 ：O(n) 從頭到尾周遊已有序資料
- 最壞時間複雜度：O(n2) 每次 插入相等于在數組的第一位插入新資料，是以要移動大量資料
- 平均時間複雜度: O(n2)
三、代碼實作
/**
* 插入排序
* @author chao
*/
public class Insert_Sort {
public static void main(String[] args) {
int[] arrs = { 5, 4, 2, 7, 8 };
Insert_Sort.InsertSort(arrs, arrs.length);
System.out.println(Arrays.toString(arrs));
}
public static void InsertSort(int[] arrays, int n) {
for (int i = 1; i < n; i++) {
int value = arrays[i];
int j = i - 1;
for (; j >= 0; --j) {
// 找到自己的插入位置
if (arrays[j] > value) {
// 如果前面的元素比自己大就移動元素
arrays[j + 1] = arrays[j];
} else {
// 否則跳出循環
break;
}
}
// 在需要插入的位置插入資料
arrays[j + 1] = value;
}
}
}
四、選擇排序
一、排序原理
類似插入排序，也分已排序區間和未排序區間。但是選擇排序每次會從未排序區間找到最小的元素，将其放到已排序區間的末尾
二、性能分析
空間複雜度：選擇排序是原地排序算法。
穩定性：選擇排序不是穩定的排序算法。比如5，8，5，2，9 找到最小元素是2和5交換就不穩定了
時間複雜度：都是O(n^2)
1. 最好情況：O(n^2)。
2. 最壞情況：O(n^2)。
3. 平均情況：O(n^2)。
三、代碼實作
/*
* 選擇排序
*/
public class Selection_Sort {
public static void main(String[] args) {
int[] arrs = { 5, 4, 2, 7, 8, 1 };
Selection_Sort.selectSort(arrs, arrs.length);
System.out.println(Arrays.toString(arrs));
}
public static void selectSort(int arrs[], int n) {
for (int i = 0; i < n; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
// 尋找到最小數的下标
if (arrs[minIndex] > arrs[j]) {
minIndex = j;
}
}
// 交換資料
int minValue = arrs[i];
arrs[i] = arrs[minIndex];
arrs[minIndex] = minValue;
}
}
}
問題：插入和冒泡複雜度都是O(n2)，為什麼實際開發中更傾向與插入算法呢？
我們前面分析冒泡排序和插入排序的時候講到，冒泡排序不管怎麼優化，元素交換的次數是一個固定值，是原始資料的逆序度。插入排序是同樣的，不管怎麼優化，元素移動的次數也等于原始資料的逆序度。
但是，從代碼實作上來看，冒泡排序的資料交換要比插入排序的資料移動要複雜，冒泡排序需要 3 個指派操作，而插入排序隻需要 一個
//冒泡排序中資料的交換操作：
if (a[j] > a[j+1]) { // 交換
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = true;
}
//插入排序中資料的移動操作：
if (a[j] > value) {
a[j+1] = a[j]; // 資料移動
} else {
break;
}