Java中的經典算法之選擇排序（SelectionSort）

本人免費整理了Java高級資料，涵蓋了Java、Redis、MongoDB、MySQL、Zookeeper、Spring Cloud、Dubbo高并發分布式等教程，一共30G，需要自己領取。
傳送門：https://mp.weixin.qq.com/s/JzddfH-7yNudmkjT0IRL8Q

a)?原理：每一趟從待排序的記錄中選出最小的元素，順序放在已排好序的序列最后，直到全部記錄排序完畢。

也就是：每一趟在n-i+1(i=1，2，…n-1)個記錄中選取關鍵字最小的記錄作為有序序列中第i個記錄?；诖怂枷氲乃惴ㄖ饕泻唵芜x擇排序、樹型選擇排序和堆排序。（這里只介紹常用的簡單選擇排序）

b)?簡單選擇排序的基本思想：給定數組：int[] arr={里面n個數據}；第1趟排序，在待排序數據arr[1]~arr[n]中選出最小的數據，將它與arrr[1]交換；第2趟，在待排序數據arr[2]~arr[n]中選出最小的數據，將它與r[2]交換；以此類推，第i趟在待排序數據arr[i]~arr[n]中選出最小的數據，將它與r[i]交換，直到全部排序完成。

c)?舉例：數組 int[] arr={5,2,8,4,9,1};

-------------------------------------------------------

第一趟排序： 原始數據：5 2 8 4 9 1

最小數據1，把1放在首位，也就是1和5互換位置，

排序結果：1 2 8 4 9 5

-------------------------------------------------------

第二趟排序： 第1以外的數據{2 8 4 9 5}進行比較，2最小，

排序結果：1 2 8 4 9 5

-------------------------------------------------------

第三趟排序： 除1、2以外的數據{8 4 9 5}進行比較，4最小，8和4交換

排序結果：1 2 4 8 9 5

-------------------------------------------------------

第四趟排序： 除第1、2、4以外的其他數據{8 9 5}進行比較，5最小，8和5交換

排序結果：1 2 4 5 9 8

-------------------------------------------------------

第五趟排序： 除第1、2、4、5以外的其他數據{9 8}進行比較，8最小，8和9交換

排序結果：1 2 4 5 8 9

-------------------------------------------------------

注：每一趟排序獲得最小數的方法：for循環進行比較，定義一個第三個變量temp，首先前兩個數比較，把較小的數放在temp中，然后用temp再去跟剩下的數據比較，如果出現比temp小的數據，就用它代替temp中原有的數據。

具體參照后面的代碼示例，相信你在學排序之前已經學過for循環語句了，這樣的話，這里理解起來就特別容易了。

代碼示例：

?//選擇排序public?class?SelectionSort?{
????public?static?void?main(String[]?args)?{
????????int[]?arr={1,3,2,45,65,33,12};
????????System.out.println("交換之前：");
????????for(int?num:arr){
????????????System.out.print(num+"?");
????????}????????
????????//選擇排序的優化????????for(int?i?=?0;?i?<?arr.length?-?1;?i++)?{//?做第i趟排序????????????int?k?=?i;
????????????for(int?j?=?k?+?1;?j?<?arr.length;?j++){//?選最小的記錄????????????????if(arr[j]?<?arr[k]){?
????????????????????k?=?j;?//記下目前找到的最小值所在的位置????????????????}
????????????}
????????????//在內層循環結束，也就是找到本輪循環的最小的數以后，再進行交換????????????if(i?!=?k){??//交換a[i]和a[k]????????????????int?temp?=?arr[i];
????????????????arr[i]?=?arr[k];
????????????????arr[k]?=?temp;
????????????}????
????????}
????????System.out.println();
????????System.out.println("交換后：");
????????for(int?num:arr){
????????????System.out.print(num+"?");
????????}
????}}

運行結果截圖：

選擇排序的時間復雜度：簡單選擇排序的比較次數與序列的初始排序無關。

假設待排序的序列有 N 個元素，則比較次數永遠都是N (N - 1) / 2。

而移動次數與序列的初始排序有關。

當序列正序時，移動次數最少，為 0。

當序列反序時，移動次數最多，為3N (N - 1) / 2。

所以，綜上，簡單排序的時間復雜度為 O(N2)。