算法练习day5——190322(快排、建堆、调整堆)
1.快速排序
1.1 非經(jīng)典:
- 每次選取數(shù)組的最后一個元素為基準(zhǔn),進(jìn)行排序;
 - 將大于基準(zhǔn)的排后邊,小于基準(zhǔn)的排前面,等于基準(zhǔn)的在中間(類似于荷蘭國旗問題);
 - 直至進(jìn)行排序的左邊界=右邊界。
 
運(yùn)行結(jié)果:
1.2 經(jīng)典的:
第一次排序之前:
第一次排序之后:
第二次進(jìn)行排序的范圍:
即:每次排序只搞定一個數(shù)x。(可能小于等于x之中還有多個等于x的)。
而上面1.1的方法,排完序后:
第二次排序的范圍:
減少了比較的次數(shù),提高了效率。
1.3 代碼中的partation
剛開始時,less和more的位置:
一次排序之后:
交換x和大于區(qū)域的第一個位置的元素:
可以相對減少比較次數(shù)。
1.4 改進(jìn):隨機(jī)快排(最常用的)
1.4.1 快排的缺陷
可能使得一部分區(qū)域沒數(shù)據(jù),基準(zhǔn)值選的太偏。
比如:
此時選擇7作為基準(zhǔn),一次排序后,只搞定了一個元素。花費(fèi)是:
N個元素的花費(fèi)為:,即。
1.4.2 最好的情況
大于小于區(qū)域長度相當(dāng)——類似于歸并排序的時間復(fù)雜度。
1.4.3 改進(jìn)quickSort()
public static void quickSort(int[] arr, int l, int r) {if (l < r) {swap(arr, l + (int) (Math.random() * (r - l + 1)), r);//獲取隨機(jī)的元素為基準(zhǔn)int[] p = partition(arr, l, r);quickSort(arr, l, p[0] - 1);quickSort(arr, p[1] + 1, r);} }每次不是選擇最后位置,而是選擇隨機(jī)位置的數(shù)進(jìn)行劃分。
交換這個隨機(jī)位置的數(shù)和最后位置元素的原因:便于代碼復(fù)用。
落在每個位置上的概率相等,最終的時間復(fù)雜度應(yīng)用概率表示,結(jié)果:。
最常用的,代碼簡潔——常數(shù)項(xiàng)很低。
- mergeSort:需準(zhǔn)備一個數(shù)組,并且要數(shù)組拷貝;空間復(fù)雜度是
 - quickSort:一個while搞定;空間復(fù)雜度:; 
- 隨機(jī)快排的時間復(fù)雜度是那個;
 - 記住等與區(qū)域的左右邊界,原因: 
- 當(dāng)左半部分排完后,需要知道右半部分從哪開始;
 
 - 浪費(fèi)空間的地方是在劃分點(diǎn)。總共是劃分次(概率計算) 
- 最壞是次;
 - 最好是次。
 
 
 
最少也得用3個位置存放斷點(diǎn)。
1.5 算法在設(shè)計時繞開樣本本身數(shù)據(jù)狀況的方法
1.隨機(jī),打亂數(shù)據(jù)狀況;
2.哈希,也是打亂。
1.6 其他
工程上用的是快排的非遞歸版本。
因?yàn)檫f歸的準(zhǔn)備代價高:壓棧信息多,大量都是無用信息。
遞歸層數(shù)多時系統(tǒng)棧也會報錯。
應(yīng)該為非遞歸。
2.堆排序
堆:是完全二叉樹(要么是一個滿二叉樹,要么僅有的節(jié)點(diǎn)序號和滿二叉樹中的一一對應(yīng))。
并不存在實(shí)際的二叉樹,都是數(shù)組結(jié)構(gòu),只是在數(shù)組結(jié)構(gòu)中定義了一個規(guī)則。
2.1 堆的分類
大根堆:任何一個子樹的最大值都是頭部;
小根堆:任何一個子樹的最小值都是頭部;
2.2 數(shù)組變成大根堆:
數(shù)組中的一個子數(shù)組也可想成完全二叉樹。
原始數(shù)組:
1、首先,假設(shè)需要變換的數(shù)組的范圍僅是0位置的元素:
(腦海中的:)
2、接著是0~1位置的元素:
同時需要比較1和它父節(jié)點(diǎn)元素的大小,若大于就得交換。
父節(jié)點(diǎn)位置的確定:(當(dāng)前元素的下標(biāo)-1)/2
(1-1)/2=0;
所以1位置的元素和0位置的進(jìn)行比較:1<2,不用交換
3、接著假設(shè)需要轉(zhuǎn)換的是0~2位置的元素:
比較2位置的元素和(2-1)/2=0(向下取整)位置的元素:3>2,需要交換:
交換后,比較被交換位置0的元素和它父節(jié)點(diǎn)位置(0-1)/2=0的元素,相等,不滿足大于的條件,不交換。
4、0~3位置的元素:
比較3位置的元素和(3-1)/2=1位置的元素:6>1,需要交換:
再接著比較6和它父節(jié)點(diǎn)0的元素:6>3,繼續(xù)交換:
5、0~4位置的元素:
0小于它父節(jié)點(diǎn)位置(4-1)/2=1的元素3,所以不用交換。
6、0~5位置的元素:
比較4和它父節(jié)點(diǎn)位置(5-1)/4=2的元素:4>2,需要交換:
交換后,比較被交換節(jié)點(diǎn)位置2的元素和它父節(jié)點(diǎn)位置0的元素:4<6不需要交換。
5已經(jīng)是數(shù)組的最大下標(biāo),大頂堆轉(zhuǎn)換結(jié)束。
此部分的實(shí)現(xiàn)代碼:
package Sort;public class HeapSort {public static void main(String[] args) {int[] array= {2,1,3,6,0,4};heapSort(array);for(int i=0;i<array.length;i++)System.out.print(array[i]+" ");}public static void heapSort(int[] arr) {for(int i=0;i<arr.length;i++) {heapInsert(arr,i);//對0~1、0~2...進(jìn)行建堆}}public static void heapInsert(int[] arr,int i) {while(arr[i]>arr[(i-1)/2]) {swap(arr,i,(i-1)/2);i=(i-1)/2;//變?yōu)樽约旱母腹?jié)點(diǎn),繼續(xù)向上比較}}public static void swap(int[] arr,int i,int j) {int temp=arr[i];arr[i]=arr[j];arr[j]=temp;} }運(yùn)行結(jié)果:
2.2.1 建立大根堆的時間復(fù)雜度
一個節(jié)點(diǎn)進(jìn)來時,只需要和它到父節(jié)點(diǎn)、祖宗節(jié)點(diǎn)進(jìn)行比較。
比較次數(shù)就為目前數(shù)高:
加入節(jié)點(diǎn)i時,面0~i-1的大頂堆已經(jīng)建好,所以它比的就是0~i-1所形成的樹高。
所以總共是:
2.3 heapify
當(dāng)堆中有元素發(fā)生變化,進(jìn)行調(diào)整的過程。
- 找到它的左右兩個孩子;
 - 孩子中較大的和它進(jìn)行交換;
 
值變化之前:
將6變?yōu)?:
不滿足大根堆的特性了,需要進(jìn)行調(diào)整。
首先找到變化位置0的左右孩子:0*2+1=1,0*2+2=2。
比較,選擇其中較大的和自己交換:5>4,所以1和5進(jìn)行交換:
再找被調(diào)整位置1的左右孩子:1*2+1=3,1*2+2=4。
比較,找到其中較大的:5>3,所以1和5進(jìn)行交換:
此時1位置4的左右孩子越界,計算停止。
大根堆調(diào)整完畢。
代碼實(shí)現(xiàn):
package Sort;public class HeapSort {public static void main(String[] args) {int[] array= {2,1,3,6,0,4};heapSort(array);for(int i=0;i<array.length;i++)System.out.print(array[i]+" ");System.out.println();array[0]=1;heapify(array,0,array.length);//傳入更改的位置for(int i=0;i<array.length;i++)System.out.print(array[i]+" ");}public static void heapSort(int[] arr) {for(int i=0;i<arr.length;i++) {heapInsert(arr,i);//對0~1、0~2...進(jìn)行建堆}}public static void heapInsert(int[] arr,int i) {while(arr[i]>arr[(i-1)/2]) {swap(arr,i,(i-1)/2);i=(i-1)/2;//變?yōu)樽约旱母腹?jié)點(diǎn),繼續(xù)向上比較}}public static void heapify(int[] arr,int i,int heapsize) {int left=i*2+1;while(left<heapsize) {if(left+1<heapsize) {int largest=max(arr,i,left,left+1);if(largest==arr[i])//它已經(jīng)是最大的了break;else if(largest==arr[left]) {swap(arr,i,left);i=left;}else {swap(arr,i,left+1);i=left+1;}left=2*i+1;}else {if(arr[i]<arr[left]) {swap(arr,i,left);i=left;left=i*2+1;}elsebreak;}}}public static void swap(int[] arr,int i,int j) {int temp=arr[i];arr[i]=arr[j];arr[j]=temp;}public static int max(int[] arr,int i,int j,int k) {int num=arr[i]>arr[j]?arr[i]:arr[j];return num>arr[k]?num:arr[k];} }運(yùn)行結(jié)果:
更簡短的代碼:
public static void heapify(int[] arr, int index, int size) {int left = index * 2 + 1;while (left < size) {//左孩子不越界//僅當(dāng)右孩子不越界,并且右孩子大于左孩子時,largest=右孩子下標(biāo),//否則largest=左孩子下標(biāo)int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;//largest處的元素再和index處的元素進(jìn)行比較,largest為三者中最大值的下標(biāo)largest = arr[largest] > arr[index] ? largest : index;//如果三者中最大值是index處的,結(jié)束循環(huán)if (largest == index) {break;}//largset!=index時才能執(zhí)行到此處//交換index和三者中最大值的位置swap(arr, largest, index);//改變需要對比的節(jié)點(diǎn)的下標(biāo)以及它左孩子的下標(biāo)index = largest;left = index * 2 + 1;} }?
總結(jié)
以上是生活随笔為你收集整理的算法练习day5——190322(快排、建堆、调整堆)的全部內(nèi)容,希望文章能夠幫你解決所遇到的問題。
                            
                        - 上一篇: 算法练习day1——190318(二分查
 - 下一篇: 算法练习day6——190323(求中位