如何識別排序算法的優(yōu)劣
??所有的排序都需要兩個過程；
- 比較大小 每個類型都有其對應的比較大小的方法
- 交換順序 兩個數(shù)交換位置需要用到中間臨時變量，就像一杯可樂和一杯雪碧如何將他們杯中的飲料互換，肯定要借用一個杯子，將可樂先放進去然后再把雪碧放入到可樂杯中，最后把借用杯子中的可樂倒入雪碧的杯中。從而實現(xiàn)了兩杯飲料的互換內容。
在數(shù)據結構和算法中有很多排序，比如冒泡排序、選擇排序、插入排序等。他們的實現(xiàn)都會經過比較大小和交換順序這兩個過程，無疑他們的思路不太一樣。那么他們如何比較優(yōu)劣呢？
從三點進行判斷
1.時間復雜度 ：使用大O法判斷即可，實際耗時的地方在于比較的次數(shù)，交換順序，在交換順序時需要用到中間變量，中間變量的多少也影響耗時。
2.空間復雜度 : 原來存儲數(shù)據的大小和排序之后的大小是否一致
3.穩(wěn)定性 ： 如果兩個數(shù)據相同，排序后他們的順序保持不變，則該排序算法為穩(wěn)定的。
下面從這個三個方面依次分析 冒泡排序、選擇排序、插入排序。
冒泡排序
??冒泡排序的實現(xiàn)思路是取第一個元素與后一個比較，如果大于后者，就與后者互換位置，不大于，就保持位置不變。再拿第二個元素與后者比較，如果大于后者，就與后者互換位置。一輪比較之后，最大的元素就移動到末尾。相當于最大的就冒出來了。再進行第二輪，第三輪，直到排序完畢。
??分析冒泡排序的時間復雜度：最好情況時間復雜度是O(n)。最好的情況本身就是有序的，比較了一輪，一次冒泡，不需要移動元素，排序完成。
??最壞情況時間復雜度是O(n2)。最壞情況剛好是反序的（結合本例，就是倒序），要進行（n-1）輪的比較，每輪比較都要進行（n-1）次的位置移動。
??平均情況時間復雜度也是為O(n2)。這個用加權平均算概率有點復雜。理論是，n個元素，排列方式就在有 n! 種，每種情況下，比較多少輪，每次多少數(shù)據移動都不一樣。有一點是確定的，上限是O(n2)，下限是o(n)。
這里，我們引入一個簡化的比較方式。
??有序度：滿足 a[m] > a[n]，且 m > n 的一對數(shù)，
??逆序度：滿足 a[m] > a[n]，且 m < n 的一對數(shù)，
??滿序度：有序度的最大值（或逆序度的最大值）。潢序度 = 有序度 + 逆序度
??對于冒泡排序，冒泡一次，有序度至少增加一，當達到滿度時，排序就結束。在 n! 種排列中，有序度最小值是0，最大值是(n-1)n/2，平均值就是(n-1)n/4。有序度可以評價冒泡排序的比較操作，移動元素的操作肯定比比較的操作少，那冒泡排序的平均情況時間復雜度是 (n-1)*n/4 至 最壞情況時間復雜度之間的值，不考慮系數(shù)，低階，得O(n2)。
??冒泡排序的空間復雜度是O(1)，數(shù)據移動需要一個臨時變量，屬于常量級別。
??冒泡排序是穩(wěn)定性算法，從實現(xiàn)的代碼，可以推知，當相同元素比對時，不會進行數(shù)據移動。
代碼實現(xiàn)
/**
* 冒泡排序 從小到大排序
*/
public void bubbleSort(Integer[] datas) {
this.compareTimes = 0;
this.exchangeTimes = 0;
for (int i = 0; i < datas.length - 1; i++) {
for (int j = 0; j < datas.length - i - 1; j++) {
this.compareTimes++;
if (datas[j] > datas[j + 1]) {
this.exchangeTimes++;
int flag = datas[j];
datas[j] = datas[j + 1];
datas[j + 1] = flag;
}
}
}
System.out.println("比較了"+this.compareTimes);
System.out.println("交換了"+this.exchangeTimes);
}
選擇排序
??實現(xiàn)思路：把所有數(shù)據分為已排序區(qū)間和未排序區(qū)間。每次從未排序區(qū)間中，選出最小值，之后將該值與未排序區(qū)間第一個元素互換位置，此時已排序區(qū)間元素個數(shù)多了一個，未排序區(qū)間內的元素少了一個。如此循環(huán)直到未排序區(qū)間沒有元素為止。
??選擇排序算法，最好情況時間復雜度與最壞情況時間復雜度，都是O(n2)，空間復雜度是O(1)，它是不穩(wěn)定的算法。相同元素，排序后，相對位置可能發(fā)生改變。
代碼實現(xiàn)
/**
* 選擇排序
* @param datas
*/
public void selectSort(Integer[] datas){
for (int i = 0; i < datas.length; i++) {
int index = 0;
int flag = datas[0];
for (int j = 1; j < datas.length - i; j++) {
this.compareTimes ++;
if (datas[j] > datas[index]){
flag = datas[j];
index = j;
}
}
this.exchangeTimes ++;
datas[index] = datas[datas.length-i-1];
datas[datas.length-i-1] = flag;
}
System.out.println("比較了"+this.compareTimes);
System.out.println("交換了"+this.exchangeTimes);
}
插入排序
??實現(xiàn)思路：把元素分為已排序的和未排序的。每次從未排序的元素取出第一個，與已排序的元素從尾到頭逐一比較，找到插入點，將之后的元素都往后移一位，騰出位置給該元素。
記得比較的時候從后往前比較
??插入排序，最好情況時間復雜度，如果已經是一個有序數(shù)組了，就不需要移動數(shù)據。只要查找到插入位置即可，每次只需要一次比較就可以找到插入位置，所以，這種情況下，最好情況時間復雜度為O(n)。
??如果數(shù)組是倒序的，每次插入都相當于在數(shù)組的第一個位置插入數(shù)據，有大量移動數(shù)據的操作，所以，最壞情況時間復雜度是O(n2)。
??數(shù)組中插入一個數(shù)據平均時間復雜度是O(n)，要進行n次操作，所以，平均情況時間復雜度是O(n2)。
??空間復雜度是O(1)。也是一種穩(wěn)定性算法。
代碼實現(xiàn)
/**
* 插入排序
* @param datas
*/
public void insertSort(Integer[] datas){
for (int i = 1; i < datas.length; i++) {
int flag = datas[i];
int j = i-1;
for (; j >= 0; j--) {
if (datas[j] > flag){
datas[j+1] = datas[j];
}else {
break;
}
}
datas[j+1] = flag;
}
}
那么三種排序方式，哪種更常用呢？肯定不是選擇排序，首先他不是穩(wěn)定的的算法。那么插入排序和冒泡排序哪個更好呢？答案是插入排序?？梢杂^察一下插入排序中的中間變量是在第一層循環(huán)中，而冒泡排序的中間變量在第二層循環(huán)中，可見在冒泡排序需要更多次創(chuàng)建臨時變量，所以他的消耗時間更長。
