Java排序算法中的選擇排序算法實現(xiàn)
Java選擇排序算法
1、排序原理
選擇排序算法的實現(xiàn)思路類似插入排序,分已排序區(qū)間和未排序區(qū)間。選擇排序每次會從未排序區(qū)間中找到最小(大)的元素,將其放到已排序區(qū)間的末尾。
排序原理的基本思想是:
- 第一次從 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 次, 得到一個按排序碼從小到大排列的有序序列。
通過一張動態(tài)圖,來直觀感受一下,要排序的數(shù)組為:[4,5,6,1,3,2],正序排序
偽代碼實現(xiàn):
循環(huán)(元素個數(shù)-1)次
把第一個沒有排序過的元素設置為最小值
循環(huán)(每個沒有排序過的元素)
如果元素 < 現(xiàn)在的最小值
將此元素設置成為新的最小值
將最小值和第一個沒有排序過的位置交換
2、代碼實現(xiàn)
/** * 選擇排序 * @param array * @return */ public static int[] selectionSort(int[] array) { if (array.length == 0) return array; for (int i = 0; i < array.length; i++) { //初始最小值默認為第一個數(shù)據(jù) int minIndex = i; for (int j = i+1; j < array.length; j++) { //找到最小的數(shù) if (array[j] < array[minIndex]) minIndex = j; //將最小數(shù)的索引保存 } int temp = array[minIndex]; array[minIndex] = array[i]; array[i] = temp; } return array; }
3、算法分析
3.1、時間復雜度
- 最好情況:T(n)=O(n^2)
- 最壞情況:T(n)=O(n^2)
- 平均情況:T(n)=O(n^2)
3.2、是否穩(wěn)定
選擇排序是一種不穩(wěn)定的排序算法。選擇排序每次都要找剩余未排序元素中的最小值,并和前面的元素交換位置,這樣破壞了穩(wěn)定性。
到此這篇關于Java排序算法中的選擇排序算法實現(xiàn)的文章就介紹到這了,更多相關Java選擇排序算法內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
mybatis攔截器實現(xiàn)數(shù)據(jù)庫數(shù)據(jù)權限隔離方式
通過Mybatis攔截器,在執(zhí)行SQL前添加條件實現(xiàn)數(shù)據(jù)權限隔離,特別是對于存在用戶ID區(qū)分的表,攔截器會自動添加如user_id=#{userId}的條件,確保SQL在執(zhí)行時只能操作指定用戶的數(shù)據(jù),此方法主要應用于Mybatis的四個階段2024-11-11SpringMVC的組件之HandlerExceptionResolver詳解
這篇文章主要介紹了SpringMVC的組件之HandlerExceptionResolver詳解,不管是在處理請求映射(HandlerMapping),還是在請求被處理(Handler)時拋出的異常,DispatcherServlet都會委托給HandlerExceptionResolver進行異常處理,該接口只有一個方法,需要的朋友可以參考下2023-10-10