一法牲、冒泡排序
冒泡排序是一種交換排序，基本思想就是：兩兩比較相鄰記錄的關(guān)鍵字饮焦，如果反序則交換怕吴，直到?jīng)]有反序的記錄為止。
下面給出 3 種冒泡排序县踢，性能依次提升转绷。
- 1.最簡單的冒泡排序
從第一個開始不斷地和其他進行比較，如果大于其他的那么久互換數(shù)據(jù)硼啤，一輪下來第一個就會變成最小的一個议经。然后循環(huán)比較第二個，指導(dǎo)最后一個。這種事最簡單的冒泡排序，時間復(fù)雜度為 O(n^2)。性能有待提升帆竹。
show my code
/**
* 最簡單的冒泡算法筒饰，依次比較兩個記錄的大小
* 如果 i > j,則交換兩者，一輪下來，i 將是最小的。
* 但是這樣的效率很低，時間復(fù)雜度是 o(n^2)毯炮。
* @param data
*/
public static void bubbleSort(int[] data){
if(data == null || data.length <1){
System.out.println("輸入數(shù)據(jù)不合法");
return;
}
for(int i=0;i<data.length;i++){
//一輪下來 data[i] 將是最小的值
for(int j =i+1;j<data.length;j++){
if(data[i] > data[j]){
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
}
}
- 2.改進的冒泡排序
假如我們不從頭開始比較，然而從末尾開始比較耸黑，那么就能像冒泡那樣桃煎，將最小值從末位提到首位。那么會對我們下次比較有幫助大刊。
show my code
/**
* 改進版的冒泡排序方法
* 從數(shù)組后端開始比較为迈，將最小的數(shù)值從末端移到最前端
* 就像冒泡一樣
* @param data
*/
public static void betterBubbleSort(int[] data){
if(data == null || data.length <1){
System.out.println("輸入數(shù)據(jù)不合法");
return;
}
for(int i=0;i<data.length;i++){
for(int j = data.length -2;j >= i;j--){
//從末端開始比較，將最小的往上移動缺菌，就像冒泡過程
if(data[j] > data[j+1]){
int temp = data[j];
data[j] = data[j+1];
data[j+1] = temp;
}
}
}
}
- 3.性能最優(yōu)的冒泡排序
我們在改進版的冒泡排序的基礎(chǔ)上發(fā)現(xiàn)葫辐，其實從末端往前比較的時候，假如一直沒有發(fā)生交換伴郁，那么這個序列本身就是有序的耿战，我們就不需要重復(fù)做這么多比較工作了。所以我們在改進版的基礎(chǔ)上添加一個標(biāo)志位表示我們是否需要再比較一次焊傅。
show my code
/**
* 更好性能的冒泡排序剂陡，在改良版的冒泡排序中添加 flag 反映上一次從下往上
* 的比較是否已經(jīng)有序了
* @param data
*/
public static void bestBubbleSort(int[] data){
if(data == null || data.length <1){
System.out.println("輸入數(shù)據(jù)不合法");
return;
}
boolean notOrdered = true;
for(int i=0;i<data.length && notOrdered;i++){
//假如已經(jīng)有序
notOrdered = false;
for(int j = data.length -2;j >= i;j--){
//從末端開始比較，將最小的往上移動狐胎，就像冒泡過程
if(data[j] > data[j+1]){
int temp = data[j];
data[j] = data[j+1];
data[j+1] = temp;
//有交換就是無序鸭栖，需要繼續(xù)比較
notOrdered = true;
}
}
}
}
二、簡單選擇排序算法
簡單選擇排序的思想就是：每一趟在 n - i（i = 0,1,......n-1）個記錄中選出關(guān)鍵字最小的記錄握巢，并和第 i （i = 0,1,......n-1）個記錄作交換晕鹊。
時間復(fù)雜度和冒泡排序相同，都是 O(n^2)暴浦，但比冒泡排序減少了交換數(shù)據(jù)的操作溅话，性能要好一點。
show my code
/**
* 選擇排序
* @author innovator
*
*/
public class MySelectSort {
/**
* 選擇排序
* @param data
*/
public static void selectSort(int[] data){
if(data == null || data.length <1){
System.out.println("輸入數(shù)據(jù)不合法");
return;
}
//標(biāo)志最小記錄的位置
int min = 0;
for(int i=0;i<data.length;i++){
//假設(shè)最小的記錄位置是 i
min = i;
//找到剩下的 n - i 個記錄中最小元素的位置
//跟冒泡排序的區(qū)別就是 找到但不替換
for(int j = i+1;j<data.length;j++){
if(data[min] > data[j]){
min = j;
}
}
//找到之后和第 i 個進行比較肉渴，將最小的置為第 i 個
if( min != i){
int temp = data[i];
data[i] = data[min];
data[min] = temp;
}
}
}
public static void main(String[] args) throws Exception {
int[] data = {
2,4,3,6,9,1,5,7
};
for(int i:data){
System.out.printf(i+" ");
}
selectSort(data);
System.out.println("");
for(int i:data){
System.out.printf(i+" ");
}
}
}
結(jié)果
三公荧、直接插入排序
直接插入排序的思想就是：將一個記錄和已經(jīng)有序的序列進行比較，將有序的序列中大于此記錄的元素往后移同规，挪出一個合適的位置給待插入的記錄，最后插入該元素到合適的位置，這樣就能排好序了券勺。
時間復(fù)雜度和冒泡排序以及簡單選擇排序相同绪钥，都是 O(n^2)，但比冒泡排序和簡單選擇排序性能要好一點关炼。
show my code
/**
* 插入排序
* @author innovator
*
*/
public class MyInsertSort {
/**
* 插入排序
*
* 用一個臨時變量保存當(dāng)前比較位置的數(shù)值程腹，然后將這個位置之前的所有
* 元素都和這個臨時變量比較，如果大于這個這個臨時變量儒拂，
* 表示這個元素需要右移一位寸潦，一直比較到第 0 個，空出的位置正好插入這個臨時變量
* @param data
*/
public static void insertSort(int[] data){
if(data == null || data.length <1){
System.out.println("輸入數(shù)據(jù)不合法");
return;
}
int i = 0;
int j = 0;
//臨時變量保存當(dāng)前比較位置的值
int temp = -1;
//從 1 開始社痛，是假定第 0 個已經(jīng)是排序好了的
for(i = 1;i<data.length;i++){
j = i;
//保存當(dāng)前比較位置的值见转，為了以后插入到合適的位置
temp = data[i];
//比較 i 位置之前的元素和 i 位置的元素的大小，大的右移蒜哀，小的不動
while(j >0 && data[j-1] > temp){
data[j] = data[j-1];
//退出循環(huán)后斩箫，j 位置將是臨時變量應(yīng)該在的位置
j--;
}
//將臨時變量插進應(yīng)該在的位置
data[j] = temp;
}
}
public static void main(String[] args) throws Exception {
int[] data = {
2,4,3,6,9,1,5,7
};
for(int i:data){
System.out.printf(i+" ");
}
insertSort(data);
System.out.println("");
for(int i:data){
System.out.printf(i+" ");
}
}
}
結(jié)果
四、希爾排序
希爾排序基本原理是：現(xiàn)將待排序的數(shù)組元素分成多個子序列撵儿，使得每個子序列的元素個數(shù)相對較少乘客，然后對各個子序列分別進行直接插入排序，待整個待排序列“基本有序”后淀歇，最后在對所有元素進行一次直接插入排序易核。
因此，我們要采用跳躍分割的策略：將相距某個“增量”的記錄組成一個子序列浪默，這樣才能保證在子序列內(nèi)分別進行直接插入排序后得到的結(jié)果是基本有序而不是局部有序牡直。希爾排序是對直接插入排序算法的優(yōu)化和升級。
所謂的基本有序浴鸿，就是小的關(guān)鍵字基本在前面井氢，大的基本在后面，不大不小的基本在中間岳链，例如｛2,1,3,6,4,7,5,8,9｝就可以稱為基本有序了花竞。但像｛1,5,9,3,7,8,2,4,6｝這樣，9 在第三位掸哑，2 在倒數(shù)第三位就談不上基本有序约急。
希爾排序時間復(fù)雜度是 o(n^1.3)。
栗子
show my code
/**
* 希爾排序
* @author innovator
*
*/
public class MyShellSort {
/**
* 希爾排序
* 改進版的的直接插入排序苗分，通過將序列按照一個“增量”分成若干個序列厌蔽，
* 然后對若干個序列進行直接插入排序，不斷減小增量摔癣，直到 1奴饮，
* 最后對得到的序列進行插入排序就可以了
* @param data
*/
public static void shellSort(int[] data){
if(data == null || data.length < 1){
System.out.println("輸入數(shù)據(jù)不合法");
return;
}
//直接排序中用來保存當(dāng)前比較位置的元素的值
int temp = 0;
//增量
int increment = 0;
//設(shè)置增量為數(shù)組長度的一半纬向，這樣就能將第 0 個元素考慮進去了
//拆分成若干個序列進行插入排序
//最后的增量一定要是 1，因為最后要進行一次插入排序
for(increment = data.length/2;increment > 0;
increment = increment /2){
//下面就是直接插入排序的算法了
for(int i = increment;i<data.length;i++){
//保存當(dāng)前比較位置的元素的值
temp = data[i];
int j = 0;
// j -= increment 保證了按照增量對子序列進行插入排序
for(j=i-increment;j>=0; j -= increment){
//如果大于當(dāng)前的比較位置的值戴卜，那么就右移逾条，否則不動
if(data[j] > temp){
data[j+increment] = data[j];
}else {
//沒有挪動位置，因為前面已經(jīng)給有序了投剥，所以退出循環(huán)
break;
}
}
//因為上面減了 increment师脂，所以加上才是合適的插入位置
data[j+increment] = temp;
}
}
}
public static void main(String[] args) throws Exception {
int[] data = {
2,4,3,6,9,1,5,7
};
for(int i:data){
System.out.printf(i+" ");
}
shellSort(data);
System.out.println("");
for(int i:data){
System.out.printf(i+" ");
}
}
}
結(jié)果
五、堆排序
堆是具有如下性質(zhì)的完全二叉樹：每個結(jié)點的值都大于或者等于其左右孩子結(jié)點的值江锨，稱為大頂堆吃警；或者每個結(jié)點的值都小于或等于左右孩子結(jié)點的值，稱為小頂堆啄育。
堆排序的思路：將待排序的序列構(gòu)造成一個大頂堆酌心，此時整個序列的最大值就是堆頂?shù)母Y(jié)點，將它和堆數(shù)組的末尾元素交換灸撰，此時末尾元素就是最大值了谒府。然后將剩下的 n-1 個序列重新構(gòu)造成大頂堆，這樣就能得到 n 個元素中的次大值浮毯。反復(fù)執(zhí)行就能得到一個有序序列了完疫。
堆排序的時間復(fù)雜度比冒泡排序、簡單選擇排序和直接插入排序好很多债蓝，為 O(nlogn)壳鹤。
這里的難點就是：
如何由一個無序序列構(gòu)建成一個堆？
如何在輸出堆頂元素后饰迹，調(diào)整剩余元素成為一個新的堆芳誓？
show my code
/**
* 堆排序
* @author innovator
*
*/
public class MyHeapSort {
/**
* 堆排序
* 將 n 個元素構(gòu)造出一個大頂堆，然后將堆頂元素和末端元素互換啊鸭，
* 這樣末端元素就是最大值了锹淌。然后將剩下的 n-1 個元素同樣構(gòu)造成
* 大頂堆，再將堆頂元素和倒數(shù)第二個元素互換就得到了次大值元素赠制。
* 反復(fù)執(zhí)行赂摆，知道最后整個序列都有序。
* @param data
*/
public static void heapSort(int[] data) {
if(data == null || data.length < 1) {
System.out.println("輸入數(shù)據(jù)不合法");
return;
}
//從完全二叉樹的最下層的最右邊的非終端結(jié)點開始構(gòu)建
int i = data.length / 2;
//將 n 個元素構(gòu)造成大頂堆
for(; i>=0 ; i--) {
heapAdjust(data,i,data.length -1);
}
for(i = data.length -1;i>0;i--) {
//將堆頂元素（最大值）和 序列末端元素互換
swap(data,0,i);
//將剩下的 1..i-1 個元素再構(gòu)造成大頂堆钟些，然后重復(fù)這個操作
heapAdjust(data,0,i-1);
}
}
/**
* 構(gòu)造大頂堆
* 從完全二叉樹的最下層的最右非終端結(jié)點當(dāng)成根結(jié)點烟号，將其子樹調(diào)整成大頂堆。
* 然后遞歸到最頂層的根結(jié)點政恍。
* @param data
* @param startIndex 開始調(diào)整的根結(jié)點在數(shù)組中的位置
* @param endIndex 數(shù)組中最后一個元素的位置
*/
private static void heapAdjust(int[] data,int startIndex,int endIndex) {
int temp = data[startIndex];
int j;
//根據(jù)完全二叉樹的性質(zhì)汪拥，當(dāng)前結(jié)點序號為 j,其左孩子的序號一定是 2*j+1,右孩子為 2*j +2
for(j=2*startIndex+1; j <= endIndex ;j = j*2 +1) {
//循環(huán)遍歷其結(jié)點的孩子
//找到孩子中的較大值
if(j < endIndex && data[j] < data[j+1]) {
j++;
}
if(temp > data[j]) {
//根結(jié)點比孩子結(jié)點大，不需要更換值
break;
}
//將孩子結(jié)點的較大值和根結(jié)點的值互換篙耗，步驟一
data[startIndex] = data[j];
//將孩子結(jié)點的位置傳遞給 startIndex
startIndex = j;
}
//完成孩子結(jié)點值和根結(jié)點值的互換操作迫筑，步驟二
data[startIndex] = temp;
}
/**
* 互換兩個數(shù)組的值
* @param data
* @param i
* @param j
*/
private static void swap(int[] data,int i,int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
public static void main(String[] args) throws Exception {
int[] data = {
50,10,90,30,70,40,80,60,20
};
for(int i:data){
System.out.printf(i+" ");
}
heapSort(data);
System.out.println("");
for(int i:data){
System.out.printf(i+" ");
}
}
}
結(jié)果
這里最重要的是要懂得構(gòu)造最大堆宪赶，然后其他很自然就能寫出來了。
六铣焊、歸并排序
歸并排序思路：假設(shè)初始序列含有 n 個元素逊朽，可以看成 n 個有序的子序列罕伯，每個子序列長度為 1曲伊。然后兩兩合并，就得到了 ?n/2?（大于或等于 n/2 的最小整數(shù)） 個長度為 2 或者 1 的有序子序列追他，再兩兩合并坟募，循環(huán)執(zhí)行，直到得到一個長度為 n 的有序序列為止邑狸。
關(guān)鍵是要懂得如何分成兩個子序列懈糯，然后合并。
時間復(fù)雜度為 O(nlogn)单雾，是一個穩(wěn)定的排序赚哗。空間復(fù)雜度為 O(n+logn)硅堆。
show my code
/**
* 歸并排序屿储， 穩(wěn)定的排序
* @author innovator
*
*/
public class MyMergeSort {
/**
* 歸并排序
* 遞歸實現(xiàn)分序列，合并渐逃，排序
* @param data
* @param low 數(shù)組的起始位置
* @param high 數(shù)組的終點位置
*/
public static void mergeSort(int[] data,int low,int high) {
if(data == null || data.length < 1) {
System.out.println("輸入數(shù)據(jù)不合法");
return;
}
//取中間點作為分開序列的節(jié)點够掠，分成左右兩個子序列
int mid = low + (high - low) / 2;
//不能是等于，等于就說明這個子序列只有一個元素茄菊，不需要排序了
if(low < high) {
//遞歸排序左邊子序列
mergeSort(data, low, mid);
//遞歸排序右邊子序列
mergeSort(data, mid+1, high);
//將左右子序列合并為有序的序列
merge(data,low,mid,high);
}
}
/**
* 將左右子序列合并
*
* 用臨時變量將兩個子序列合并成一個子序列疯潭，然后塞進去原來數(shù)組的開始比較的位置
* @param data
* @param low 左邊子序列起點位置
* @param mid 左邊子序列終點位置
* @param high 右邊子序列終點位置
*/
public static void merge(int[] data,int low,int mid,int high) {
//用于臨時存放合并左右子序列的有序序列
int[] temp = new int[high - low +1];
//左子序列開始的位置,左指針
int i = low;
//右子序列開始的位置，右指針
int j = mid +1;
int k = 0;
//比較左右子序列面殖，將它們合并在臨時變量的數(shù)組中
while(i <= mid && j <= high) {
//左邊子序列的元素較小竖哩，將左邊的子序列的元素方法能夠進去
if(data[i] <= data[j]) {
temp[k] = data[i];
k++;
i++;
}else {
temp[k] = data[j];
k++;
j++;
}
}
// 把左子序列剩余的元素移入數(shù)組
while(i <= mid) {
temp[k] = data[i];
k++;
i++;
}
// 把右子序列剩余的元素移入數(shù)組
while(j <= high) {
temp[k] = data[j];
k++;
j++;
}
//將臨時變量中有序的序列填入原數(shù)組中開始排序的位置，所以要加 low 位移
for(int l=0;l<temp.length;l++) {
data[l+low] = temp[l];
}
}
public static void main(String[] args) {
int a[] = { 51, 46, 20, 51,18, 65, 97, 82, 30, 77, 50 };
System.out.println("排序前：" + Arrays.toString(a));
mergeSort(a, 0, a.length - 1);
System.out.println("排序結(jié)果：" + Arrays.toString(a));
}
}
結(jié)果
七脊僚、快速排序
快速排序思路：將一個序列通過一個樞軸分成兩個序列相叁，左邊的子序列小于樞軸，右邊的子序列大于樞軸吃挑，然后再重復(fù)此操作將左右兩個子序列排列钝荡。
關(guān)鍵是找樞軸的過程。
時間復(fù)雜度：O(nlogn)舶衬，空間復(fù)雜度：O(logn)埠通。不穩(wěn)定的排序。
show my code
public class MyQuickSort {
/**
* 快速排序
*
* 找出樞軸值逛犹，將序列分成兩半端辱，然后再快排
* @param data
* @param low
* @param high
*/
public static void quickSort(int[] data,int low,int high) {
if(data == null || data.length < 1) {
System.out.println("輸入數(shù)據(jù)不合法");
return;
}
//樞軸的位置
int pivot = 0;
if(low < high) {
//將序列根據(jù)樞軸分成兩個序列梁剔，得出樞軸值
pivot = getPivot(data,low,high);
//對低子表快速排序，pivot 樞軸已經(jīng)有序
quickSort(data, low,pivot-1);
//對高子表快速排序
quickSort(data, pivot+1, high);
}
}
/**
* 從一個序列中得到樞軸值舞蔽，并且將序列變成左邊的元素都小于或等于樞軸荣病，
* 右邊的元素都大于或等于樞軸值
* @param data
* @param low 起始位置
* @param high 末尾位置
* @return 樞軸的位置
*/
public static int getPivot(int[] data,int low,int high) {
//以起始位置為樞軸值
int pivotKey = data[low];
while(low < high) {
//將比樞軸小的記錄交換到左邊
while(low < high && data[high] >= pivotKey) {
high--;
}
if(low < high) {
//退出循環(huán)后，data[high] 是右邊小于等于樞軸的元素渗柿，應(yīng)該放在左邊
//這個 low 的位置就是剛好插入的位置
data[low] = data[high];
}
//將比樞軸大的記錄交換到右邊
while(low < high && data[low] <= pivotKey) {
low++;
}
if(low < high) {
//退出循環(huán)后个盆，data[low] 是左邊大于等于樞軸的元素，應(yīng)該放在右邊
//這個 high 的位置就是剛好插入的位置
data[high] = data[low];
}
}
//low 指針最后所在的地方就是樞軸的位置
data[low] = pivotKey;
return low;
}
public static void main(String[] args) throws Exception {
int[] data = {
2,4,3,6,9,1,5,7
};
for(int i:data){
System.out.printf(i+" ");
}
quickSort(data, 0, data.length-1);
System.out.println("");
for(int i:data){
System.out.printf(i+" ");
}
}
}
結(jié)果
八朵栖、總結(jié)
至此颊亮，我們已經(jīng)學(xué)完了常見的排序方法。下面對比一下各個排序方法的性能以及穩(wěn)定性陨溅。
| 排序算法 | 時間復(fù)雜度 | 空間復(fù)雜度 | 穩(wěn)定性 | 簡要介紹 |
|---|---|---|---|---|
| 快排 quickSort | O(nlogn) | O(logn) | 不穩(wěn)定舉例：1,2,3(A),3(B)=》1,2,3(B),3(A) | （小數(shù)终惑，基準(zhǔn)值，大數(shù)） |
| 歸并排序 mergeSort | O(nlogn) | O(n) | 穩(wěn)定 | 把數(shù)據(jù)分為 n 個有序段门扇，讓 n 個有序段來那個良合并雹有，從而合并成一個 n 個元素的有序序列。 |
| 堆排序 heapSort | O(nlogn) | O(1) | 不穩(wěn)定舉例：2(A),2(B),2(C)=》2(C),2(B),2(A) | 建立大頂堆臼寄，交換堆的第一個與最后一個元素霸奕，調(diào)整堆。 |
| 冒泡排序 bubbleSort | O(n^2) | O(1) | 穩(wěn)定 | 從末端開始找到最小的值一路比較冒泡到最前端脯厨。 |
| 選擇排序 selectionSort | ）O(n^2) | O(1) | 不穩(wěn)定舉例：2(A),2(B),1=》1,2(B),2(A) | 選出剩下的序列最小的元素的位置铅祸，然后和首位的元素比較，再決定是否交換值 |
| 插入排序 insertionSort | O(n^2) | O(1) | 穩(wěn)定 | （有序區(qū)合武，無序區(qū)）临梗。從左到右把無序區(qū)的第一個元素插入到有序區(qū)的合適的位置。比較得少稼跳，換得多盟庞。 |
| 希爾排序 shellSort | O(n^1.3) | O(1) | 不穩(wěn)定舉例：2(A),1(A),1(B),2(B)=》1(B),1(A),2(A),2(B) | 每一輪按照事先決定的間隔進行插入排序，間隔會依次縮小汤善，最后一次一定要是1什猖。 |
最后送給大家電影《當(dāng)幸福來敲門》中的一句話：
You got a dream gota protect it.People can't do something themselves,they wanna tell you you can't do it.If you want something,go get it.Period.
如果你有夢想的話，就要去捍衛(wèi)它红淡。當(dāng)別人做不到的時候不狮，他們想告訴你，你也不能在旱。如果你想要什么摇零，就得去努力爭取。就這樣桶蝎！
Go get it驻仅！
