摘要:需要注意的是排升序要建大堆,排降序建小堆。應用場景需要前個最大或最小元素時,或者與其他排序一塊使用五冒泡排序排序思想大的元素向下沉,小的元素向上浮。
目錄
就是將待排序的數字插入到已經排序好的指定位置即可,直到所有需要排序的數字都插入到序列即可,從而得到一個有序的序列。(相當于我們平常玩撲克牌時將接到的牌插入到指定的位置)
(1)控制排序的次數,保存需要插入的值。
(2)將大的元素向后移,找到合適的位置。
(3)將元素插入指定位置,然后繼續執行上述操作。
(4)這里需要注意在找的時候可能會到最前面,需要注意數組越界問題。
代碼實現:
//插入排序(升序) public static void insertSort(int[] arr){ //排序的次數 for(int i=1;i=0 && arr[k]>end){//尋找需要插入的位置 arr[k+1]=arr[k]; k--; } arr[k+1]=end;//將元素是插入到指定的位置 } }
(1)時間復雜度:O(N^2)
?(2)空間復雜度:O(1)
執行過程中沒有借助輔助空間。
(3)什么是穩定性
(4)穩定性:穩定?? ? ??
適合于基本有序的數組或者數據量特別小的數組,因為基本有序,那么中間進行比較的次數就會減少。
如果需要排序的數字量特別多而且比較凌亂,而且還需要使用插入排序,這時候就有了希爾排序。
先選定一個合適的距離,然后以該距離為分割長度,依次對該距離的所有元素進行插入排序,然后再縮小這個距離,直到距離為1時結束。
?
這里每次對于gap間距的值為gap=gap/3+1來處理
public static void shellSort(int[] arr){ int gap=arr.length; while(gap>1){ gap= gap/3+1; for(int i=gap;i=0 && arr[k]>end){ arr[k+gap]=arr[k]; k-=gap; } arr[k+gap]=end; } } }
(1)時間復雜度
如果gap選取的不同,則時間復雜度就,對于希爾排序,時間復雜度沒有一個確定的值,當前增量法的時間復雜度大致為O(N^1.25)到O(1.6N^1.25)之間。
(2)空間復雜度????????
????????O(1)
(3)穩定性分析
由于每次都時間隔排序,所以不穩定
對于數據量特別大,數字比較凌亂的情況下,而且還需要使用插入排序的情況下,可以使用希爾排序來進行處理。
每次選擇一個最大的數放在數組的末尾(或者每次選擇一個最下的放在數組頭,起始位置后移),然后數組長度-1,接著使用該方法,直到所有的元素排序完成即可。
//選擇排序(每次選最大的元素放在數組末尾) public static void selectSort(int[] arr){ for(int i=0;i
(1)時間復雜度
每一個元素都與前n-i-1個元素進行比較,所以時間復雜度為O(N^2)
(2)空間復雜度
沒有額外空間的開辟,所以空間復雜度為O(1)
(3)穩定性
由于每次都是間隔進行交換,所以相同的元素最后位置可能會改變,所以不穩定。
由于時間復雜度不好,平時應應用的比較少。
堆排序)是指利用堆積樹(堆)這種數據結構所設計的一種排序算法,它是選擇排序的一種。它是通過堆來進行選擇數據。需要注意的是排升序要建大堆,排降序建小堆。
?
(1)時間復雜度
因為堆排序相當于刪除元素,所以刪除需要N次,然后每次向下調整最壞為二叉樹的層數為,
所以時間復雜度為O(N*)
(2)空間復雜度
????????O(1)
(3)穩定性
?由于間隔進行交換,所以不穩定。
需要前k個最大或最小元素時,或者與其他排序一塊使用
大的元素向下沉,小的元素向上浮。
//冒泡排序 public static void bubbleSort(int[] arr){ //冒泡的趟數 for(int i=0;iarr[j+1]){ swap(arr,j,j+1);//交換2個元素 flag=true; } } //沒有再進行交換則退出 if(!flag){ return; } } } public static void swap(int[] arr,int left,int right){ int tmp=arr[left]; arr[left]=arr[right]; arr[right]=tmp; }
(1)時間復雜度
O(N^2)
(2)空間復雜度
O(1)
(3)穩定性
沒有間隔進行交換,所以穩定
基本不使用
任取待排序元素序列中的某元素作為基準值,按照該排序碼將待排序集合分割成兩子序列,左子序列中所有元素均小于基準值,右子序列中所有元素均大于基準值,然后最左右子序列重復該過程,直到所有元素都排列在相應位置上為止。
原理:以基準值為中心,將區間劃分為左邊的值都小于基準值,右邊的值都大于基準值,直到所有元素有序即可。
?
?
?4.代碼實現
如果遞歸深度過深,我們可以對遞歸到小區間的時候使用插入排序,這樣可以提高排序速度,這樣也是對快排進行優化。
//使用三數取中法選擇合適基準值,對快排優化 public static int midDiv(int[] arr,int left,int right){ int mid = left+(right-left)>>1; //在左右值比較后然后中間值與左右進行比較 if(arr[left]arr[right-1]){ return right-1; }else{ return mid; } }else {//左大右小 if(arr[mid]arr[left]){ return left; }else { return mid; } } }//前后指針法,劃分區間,得到基準值 public static int partiton(int[] arr,int left,int right){ int prev=left-1; int cur = left; int midDiv=midDiv(arr,left,right);//找合適基準值的位置 swap(arr,midDiv,right-1);//基準值位置與最后元素交換 int div = arr[right-1]; while(cur1){ int div = partiton(arr,left,right);//找基準值劃分區間 //左[left,val) quickSort(arr,left,div); //右[val+1,right) quickSort(arr,div+1,right); }
(1)時間復雜度
注意:對于未選擇三數取中的方法時,最壞的時間復雜度為O(N^2),這是因為可能每次劃分的時候左邊的都比最后一個小,相當于每次只能排好一個,每一個需要的時間大概為N,共有N個元素,所以為O(N^2),但是當每次最后一個數都為中間值的時候,時間復雜度就變為O(*N),為遞歸的深度。
通過優化后最終得到的時間復雜度為O(*N)
(2)空間復雜度
在遞歸的時候借助了輔助空間,空間復雜度為遞歸的深度,所以空間復雜度為O()。
(3)穩定性
間隔進行了交換,所以不穩定。
在數據特別隨機的時候使用快排比較高效
該算法是采用分治法(Divide andConquer)的一個非常典型的應用。將已有序的子序列合并,得到完全有序的序列;即先使每個子序列有序,再使子序列段間有序。若將兩個有序表合并成一個有序表,稱為二路歸并。
·
?
?
public static void mergeSort(int[] arr,int left,int right,int[] temp){ if(right-left>1){ int mid = left+((right-left)>>1);//注意優先級問題,否則會出現棧溢出 //分區間 mergeSort(arr,left,mid,temp); mergeSort(arr,mid,right,temp); //(合區間)將劃分好的區間進行有序合并 mergeData(arr,left,mid,right,temp); //將合并好的區間拷貝的原數組中 System.arraycopy(temp,left,arr,left,right-left); } } //負責將劃分好的區間進行合并 public static void mergeData(int[] arr,int left,int mid,int right,int[] temp){ int leftT=left; int midT = mid; int index=left; while(leftT
5.時間復雜度,空間復雜度及穩定性分析
(1)時間復雜度
O(*N)
(2)空間復雜度
這里分析空間復雜度的時候不能按照遞歸深度*合并次數來進行計算,因為每次遞歸合并后,就將之前的空間釋放掉了,所以借助的空間只有之前的輔助空間用來存儲合并有序的數,最終空間復雜度為O(N)
(3)穩定性
在進行歸并的時候沒有間隔,所以穩定。
6.應用場景
應用于外部排序。
統計相同元素出現的次數,然后根據統計的次數回收到原來的數組中即可。
對于數據特別集中在某個范圍內時,效率是很高的。
?
public static void countSort(int[] arr){ int size=arr.length; if(size==0){ return; } int max=arr[0]; int min=arr[0]; //獲取最大最小值 for(int i=1;imax){ max=arr[i]; } if(arr[i]
(1)時間復雜度
時間復雜度為:O(N),為元素的個數
(2)空間復雜度
空間復雜度為:O(Max-Min)
(3)穩定性
沒有間隔交換穩定
對于數字比較集中在某個區間范圍內時排序效率比較高。
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/124498.html
摘要:今天,一條就帶大家徹底跨過排序算法這道坎,保姆級教程建議收藏。利用遞歸算法,對分治后的子數組進行排序。基本思想堆排序是利用堆這種數據結構而設計的一種排序算法,堆排序是一種選擇排序,它的最壞,最好,平均時間復雜度均為,它也是不穩定排序。 ...
摘要:技術之類加載機制掘金類加載機制是語言的一大亮點,使得類可以被動態加載到虛擬機中。玩轉仿探探卡片式滑動效果掘金講起本篇博客的歷史起源,估計有一段歷史了。 Java 技術之類加載機制 - Android - 掘金類加載機制是 Java 語言的一大亮點,使得 Java 類可以被動態加載到 Java 虛擬機中。 這次我們拋開術語和概念,從例子入手,由淺入深地講解 Java 的類加載機制。 本文...
閱讀 3455·2023-04-26 02:31
閱讀 3620·2021-11-23 09:51
閱讀 1285·2021-11-17 09:33
閱讀 2434·2021-11-16 11:45
閱讀 2566·2021-10-11 11:12
閱讀 2406·2021-09-22 15:22
閱讀 2711·2021-09-04 16:40
閱讀 2568·2021-07-30 15:30