摘要:基本介紹選擇式排序也屬于內部排序法,是從欲排序的數據中,按指定的規則選出某一元素,再依規定交換位置后達到排序的目的。而移動次數與序列的初始排序有關。空間復雜度簡單選擇排序需要占用個臨時空間,在交換數值時使用。
1. 基本介紹
選擇式排序(select sorting)也屬于內部排序法,是從欲排序的數據中,按指定的規則選出某一元素,再依規定交換位置后達到排序的目的。
2. 選擇排序思想基本思想是:第一次從 arr[0]~arr[n-1]中選取最小值,與 arr[0]交換,第二次從 arr[1]~arr[n-1]中選取最小值,與 arr[1]交換,第三次從 arr[2]~arr[n-1]中選取最小值,與 arr[2]交換,…,第 i 次從 arr[i-1]~arr[n-1]中選取最小值,與 arr[i-1]交換,…, 第 n-1 次從 arr[n-2]~arr[n-1]中選取最小值,與 arr[n-2]交換,總共通過 n-1 次,得到一個按排序碼從小到大排列的有序序列。
3. 選擇排序理解 3.1 選擇排序圖解1.選擇排序一共有數組大小-1 次排序
2.每一次排序,又是一個循環,循環規則如下
2.1 先假定當前這個數是最小數
2.2 然后和后面的每個數進行比較,如果發現有比當前數更小的數,就重新確定最小數,并得到下標
2.3 當遍歷到數組的最后時,就得到本輪最小數和小標
2.4 交換代碼,再繼續
/** * @author: Coder編程 * @create: 2019-6-20 22:06 * @description: 選擇排序 **/ public class SelectionSort { /** * 選擇排序 * @param arr 待排序數組 */ public void selectionSort(Integer[] arr) { // 需要遍歷獲得最小值的次數 // 要注意一點,當要排序 N 個數,已經經過 N-1 次遍歷后,已經是有序數列 for (int i = 0; i < arr.length - 1; i++) { int minindex = i; // 用來保存最小值得索引 int min = arr[i]; // 用來保存最小值 for (int j = i + 1; j < arr.length; j++) { if (min > arr[j]) {// 說明假定的最小值,并不是最小 min = arr[j]; // 重置 min minindex = j; // 重置 minIndex } } // 如果假定最小值的索引發生了改變,則進行交換 if(minindex != i){ arr[minindex] = arr[i]; //此時minindex為j,因此i與j交換 arr[i] = min; //最小值給下標i } System.out.format(" 第 %d 趟: ", i + 1); Arrays.asList(arr).stream().forEach(x -> System.out.print(x + " ")); } } public static void main(String[] args) { //初始數組 Integer arrays[] = {2,9,7,5,3}; // 調用選擇排序方法 SelectionSort selection = new SelectionSort(); System.out.print("歡迎個人公眾號Coder編程:選擇排序前: "); Arrays.asList(arrays).stream().forEach(x -> System.out.print(x + " ")); selection.selectionSort(arrays); System.out.print(" 歡迎個人公眾號Coder編程:選擇排序后: "); Arrays.asList(arrays).stream().forEach(x -> System.out.print(x + " ")); } }
打印結果
如果還有什么不理解的,可以把代碼Debug拋一遍就明白了。
5. 選擇排序性能分析 5.1 時間復雜度簡單選擇排序的比較次數與序列的初始排序無關。 假設待排序的序列有n個元素,則比較次數總是n(n - 1) / 2。
而移動次數與序列的初始排序有關。當序列正序時,移動次數最少,為 0.
當序列反序時,移動次數最多,為3n (n- 1) / 2。
所以,綜合以上,簡單排序的時間復雜度為 O(n^2)。
簡單選擇排序需要占用 1 個臨時空間,在交換數值時使用。
6. 選擇排序擴展閱讀 6.1 C語言版#include6.2 Python版int main() { int i,j,t,a[11]; //定義變量及數組為基本整型 printf("請輸入10個數: "); for(i=1;i<11;i++) scanf("%d",&a[i]); //從鍵盤中輸入要排序的10個數字 for(i=1;i<=9;i++) for (j=i+1;j<=10;j++) if(a[i]>a[j]) //如果前一個數比后一個數大,則利用中間變量t實現兩值互換 { t=a[i]; a[i]=a[j]; a[j]=t; } printf("排序后的順序是: "); for(i=1;i<=10;i++) printf("%5d", a[i]); //輸出排序后的數組 printf(" "); return 0; }
def selectedSort(myList): length = len(myList) for i in range(0,length-1): smallest = i for j in range(i+1,length): if myList[j]6.3 JS版 var example=[2,9,7,5,3]; function selectSort(arr){ var len=arr.length; var minIndex,temp; console.time("選擇排序耗時"); for(i=0;i文末 歡迎關注個人微信公眾號:Coder編程
獲取最新原創技術文章和免費學習資料,更有大量精品思維導圖、面試資料、PMP備考資料等你來領,方便你隨時隨地學習技術知識!
新建了一下qq群:315211365,歡迎大家進群交流一起學習。謝謝了!也可以介紹給身邊有需要的朋友。
文章收錄至
Github: https://github.com/CoderMerli...
Gitee: https://gitee.com/573059382/c...
參考文章:
https://blog.csdn.net/qq_3624...
https://www.cnblogs.com/shen-...
推薦文章:
帶你了解時間復雜度和空間復雜度到底是什么?
帶你讀懂冒泡排序(Bubble Sorting)
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/75006.html
摘要:經過一次冒泡排序,最終在無序表中找到一個最大值,第一次冒泡結束。也是我們后面要說的冒泡排序的優化。冒泡排序只執行第一層循環,而不會執行第二層循環。因此冒泡排序的時間復雜度是。 showImg(https://user-gold-cdn.xitu.io/2019/6/19/16b6f986df6880f9?w=640&h=142&f=gif&s=17175);showImg(https:...
摘要:的選擇器允許單個線程監視多個輸入通道。一旦執行的線程已經超過讀取代碼中的某個數據片段,該線程就不會在數據中向后移動通常不會。 1、引言 很多初涉網絡編程的程序員,在研究Java NIO(即異步IO)和經典IO(也就是常說的阻塞式IO)的API時,很快就會發現一個問題:我什么時候應該使用經典IO,什么時候應該使用NIO? 在本文中,將嘗試用簡明扼要的文字,闡明Java NIO和經典IO之...
閱讀 3297·2021-11-16 11:45
閱讀 2655·2021-09-22 15:23
閱讀 564·2021-07-30 14:58
閱讀 459·2019-08-30 15:54
閱讀 2235·2019-08-29 16:19
閱讀 3016·2019-08-29 12:45
閱讀 935·2019-08-23 17:57
閱讀 1788·2019-08-23 17:54