引言
為什么想起來最近寫這一些列的文章钥平，因?yàn)樽罱粋€朋友吐槽面試的有6，7年工作經(jīng)驗(yàn)的員工疫剃，連基本的排序都不能實(shí)現(xiàn)钉疫，所以想了下，如果讓自己來做巢价，能不能講的清楚這一些列的排序牲阁。所以就動手寫了這一系列的文章，也算是自己了解鞏固下壤躲。
常用的排序算法
冒泡排序（Bubble Sort）
冒泡排序也稱為：沉降排序(SinkingSort)更耻，之所以有這兩個名字和他的實(shí)現(xiàn)方法有關(guān)，因?yàn)槊芭菖判虻膶?shí)現(xiàn)方式是將數(shù)據(jù)列表中的最小的數(shù)據(jù)往前移動捏膨，想水里面的氣泡一樣向上浮秧均。這樣也就對應(yīng)著最大的數(shù)據(jù)，逐漸往后移動号涯，對應(yīng)著上浮的就是下沉目胡。
冒泡排序每次只比較相鄰的兩個數(shù)字的大小，再將一個數(shù)字和后面數(shù)字繼續(xù)比較大小链快，一輪比較完成后在比較下一輪數(shù)據(jù)誉己。知道最終沒有數(shù)據(jù)可以比較位置，排序結(jié)束久又。
Java:
public static void main(String[] args) {
? ? int[] a =new int[]{9, 2, 7, 8, 5, 6, 3, 4, 1};
? ? for (int i =a.length -1; i >=1; i--) {
? ? ? ? for (int j =0; j < i; j++) {
? ? ? ? ? ? int temp1 =a[j];
? ? ? ? ? ? int temp2 =a[j +1];
? ? ? ? ? ? a[j] =temp1 >temp2 ?temp2 :temp1;
? ? ? ? ? ? a[j +1] =temp1 >temp2 ?temp1 :temp2;
? ? ? ? ? ? printArrays(a);
? ? ? ? }
}
}
private static void printArrays(int[] a) {
? ? for (int i =0; i
? ? ? ? System.out.print(a[i] +"、");
? ? }
? ? System.out.println();
}
Out:
2效五、9地消、7、8畏妖、5脉执、6、3戒劫、4半夷、1婆廊、
2、7巫橄、9淘邻、8、5湘换、6宾舅、3、4彩倚、1筹我、
2、7帆离、8蔬蕊、9、5哥谷、6岸夯、3、4呼巷、1囱修、
2、7王悍、8破镰、5、9压储、6鲜漩、3、4集惋、1孕似、
2、7刮刑、8喉祭、5、6雷绢、9泛烙、3、4翘紊、1蔽氨、
2、7、8鹉究、5宇立、6、3自赔、9妈嘹、4、1匿级、
2蟋滴、7、8痘绎、5津函、6、3孤页、4尔苦、9、1行施、
2允坚、7、8蛾号、5稠项、6、3鲜结、4展运、1、9精刷、
2拗胜、7、8怒允、5埂软、6、3纫事、4勘畔、1、9丽惶、
2炫七、7、8蚊夫、5诉字、6懦尝、3知纷、4壤圃、1、9琅轧、
2伍绳、7、5乍桂、8冲杀、6、3睹酌、4权谁、1、9憋沿、
2旺芽、7、5辐啄、6采章、8、3壶辜、4悯舟、1、9砸民、
2抵怎、7、5阱洪、6便贵、3、8冗荸、4承璃、1、9蚌本、
2盔粹、7、5程癌、6舷嗡、3、4嵌莉、8进萄、1、9、
2中鼠、7可婶、5、6援雇、3矛渴、4、1惫搏、8具温、9、
2筐赔、7铣猩、5、6茴丰、3剂习、4、1较沪、8鳞绕、9、
2尸曼、5们何、7、6控轿、3冤竹、4、1茬射、8鹦蠕、9、
2在抛、5钟病、6、7刚梭、3肠阱、4、1朴读、8屹徘、9、
2衅金、5噪伊、6簿煌、3、7鉴吹、4啦吧、1、8拙寡、9、
2琳水、5肆糕、6、3在孝、4诚啃、7、1私沮、8始赎、9、
2仔燕、5造垛、6、3晰搀、4五辽、1、7外恕、8杆逗、9、
2鳞疲、5罪郊、6、3尚洽、4悔橄、1、7腺毫、8橄维、9、
2拴曲、5愿汰、6、3漆枚、4棋嘲、1店溢、7、8委乌、9床牧、
2、5遭贸、3戈咳、6壕吹、4著蛙、1、7踏堡、8、9咒劲、
2顷蟆、5、3腐魂、4帐偎、6、1蛔屹、7肮街、8、9判导、
2嫉父、5、3眼刃、4绕辖、1、6擂红、7仪际、8、9昵骤、
2树碱、5、3变秦、4成榜、1、6蹦玫、7赎婚、8刘绣、9、
2挣输、3纬凤、5、4撩嚼、1停士、6、7完丽、8恋技、9、
2舰涌、3、4你稚、5瓷耙、1、6刁赖、7搁痛、8、9宇弛、
2鸡典、3、4枪芒、1彻况、5、6舅踪、7纽甘、8、9抽碌、
2悍赢、3、4货徙、1左权、5、6痴颊、7赏迟、8、9蠢棱、
2烹笔、3、4抛丽、1谤职、5、6亿鲜、7允蜈、8、9蒿柳、
2饶套、3、1垒探、4妓蛮、5、6圾叼、7蛤克、8、9夷蚊、
2构挤、3、1惕鼓、4筋现、5、6箱歧、7矾飞、8、9呀邢、
2凰慈、1、3驼鹅、4微谓、5、6输钩、7豺型、8、9买乃、
1姻氨、2、3剪验、4肴焊、5前联、6、7娶眷、8似嗤、9、
程序的實(shí)現(xiàn)邏輯很簡單届宠，變及數(shù)組烁落，依次將兩個數(shù)字做比較，如果小的在大的前面豌注，那么換一個位置伤塌，否則位置不換，繼續(xù)拿大的和后面的比較轧铁。重復(fù)實(shí)現(xiàn)邏輯每聪，為什么外面循環(huán)用i--,呢，因?yàn)槊看挝覀儗?shí)現(xiàn)一次排序齿风，總能得到一個最大值药薯，這個值，一定是排在了這個數(shù)組的最后一個聂宾，所以果善，最后面的一個我們是不需要比較的诊笤，這樣無形中也就減少了運(yùn)算系谐。
從代碼實(shí)現(xiàn)上來看，冒泡排序的時間復(fù)雜度為：O(n2);簡單的說執(zhí)行速度讨跟，取決于for循環(huán)的次數(shù)纪他，鏈表的大小。
選擇排序（Selection sort）
選擇排序是一種很直觀簡單暴力的排序算法晾匠，簡單的說茶袒，就是，先遍歷一遍數(shù)據(jù)凉馆，把最小的數(shù)據(jù)找出來薪寓，交換位置，放在第一位澜共，然后在從把后面的鏈表繼續(xù)遍歷向叉，找出最小數(shù)據(jù)，然后在嗦董，交換位置母谎，繼續(xù)遍歷后續(xù)鏈表。直到全部遍歷完成
private static void selectionSortOne(int a[]) {
? ? long first =System.currentTimeMillis();
? ? for (int i =0; i
? ? ? ? int min = i;
? ? ? ? for (int j = i; j
? ? ? ? ? ? if (a[min] >a[j]) {
? ? ? ? ? ? ? ? min = j;
? ? ? ? ? ? }
}
? ? ? ? int temp =a[i];
? ? ? ? a[i] =a[min];
? ? ? ? a[min] =temp;
? ? }
? ? long second =System.currentTimeMillis();
? ? System.out.println(second -first);
? ? printArrays(a);
}
從代碼實(shí)現(xiàn)上來看京革，選擇排序的時間復(fù)雜度為：O(n2);簡單的說執(zhí)行速度奇唤，取決于for循環(huán)的次數(shù)幸斥，鏈表的大小。
上面的排序咬扇，我們不難看出甲葬，每次排序，其實(shí)我們不僅可以找到最小值冗栗，還可以找到最大值演顾，這種情況，我們可以將排序算法變化下
private static void selectionSortTwo(int a[]) {
? ? long first =System.currentTimeMillis();
? ? for (int i =0; i
? ? ? ? int min = i;
? ? ? ? int max = i;
? ? ? ? for (int j = i; j
? ? ? ? ? ? if (a[min] >a[j]) {
? ? ? ? ? ? ? ? min = j;
? ? ? ? ? ? }
? ? ? ? ? ? if (a[max]
? ? ? ? ? ? ? ? max = j;
? ? ? ? ? ? }
}
? ? ? ? if (min != max) {
? ? ? ? ? ? int maxTemp =a[a.length - i -1];
? ? ? ? ? ? a[a.length - i -1] =a[max];
? ? ? ? ? ? a[max] =maxTemp;
? ? ? ? ? ? int temp =a[i];
? ? ? ? ? ? if (a[i] >a[min]) {
? ? ? ? ? ? ? ? a[i] =a[min];
? ? ? ? ? ? ? ? a[min] =temp;
? ? ? ? ? ? }
}
}
? ? long second =System.currentTimeMillis();
? ? System.out.println(second -first);
? ? printArrays(a);
}
每次排序同時將最小的放在最前面隅居，將最大的放在最右邊钠至，循環(huán)的時候，也不需要每次都循環(huán)到鏈表的最后段胎源，每次循環(huán)都踢掉鏈表的兩端棉钧，在進(jìn)行排序操作.
實(shí)際上這兩種寫法，在效率上相差并不大涕蚤，下面那種雖然在循環(huán)次數(shù)上變少了宪卿，但是循環(huán)類的操作變復(fù)雜了。之所以這樣寫万栅，只是說明下佑钾，我么并不是只能每次找最小的數(shù)，也可以按照需要烦粒，變換寫法休溶。
插入排序(Insertion Sort)
??插入排序是一種最簡單的排序算法，在數(shù)據(jù)量小的情況下扰她，是一種非常有效的排序方式兽掰，
他的核心思想，保證輪詢到的數(shù)據(jù)前面的鏈表部分是順序的徒役，將需要比較的數(shù)字和前面的排序完成的鏈表進(jìn)行比較孽尽，插入到一個合適的位置。
public static void main(String[] args) {
? ? int[] a =new int[20];
? ? for (int i =0; i <20; i++) {
? ? ? ? int random =(int) (Math.random() *10);
? ? ? ? a[i] =random;
? ? }
? ? for (int i =1; i
? ? ? ? int current =a[i];
? ? ? ? int seq = i;
? ? ? ? while (seq >0) {
? ? ? ? ? ? int temp =a[seq -1];
? ? ? ? ? ? if (current >=temp) {
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? a[seq -1] =current;
? ? ? ? ? ? ? ? a[seq] =temp;
? ? ? ? ? ? }
? ? ? ? ? ? seq--;
? ? ? ? }
}
? ? printArrays(a);
}
插入排序比較適合.屬于穩(wěn)定的排序忧勿，適合于數(shù)據(jù)量小杉女，部分?jǐn)?shù)據(jù)有序的情況排序。他比較依賴于原鏈表的混亂程度鸳吸。
當(dāng)鏈表是有序的熏挎，也就是最優(yōu)情況下，每個數(shù)只要和前面的一個數(shù)想比較层释，就可以了婆瓜。這時候的時間復(fù)雜度是O(n);
當(dāng)然逆向來說，如果鏈表是有序的，但是和我們需要排序的規(guī)則是相反的廉白，那么每個數(shù)字都要和前面的所有數(shù)字比較个初。這個時候，時間復(fù)雜度就變成了O(n2)
個人博客>>>常見排序算法（一）
