1.快速排序

1.1 非經(jīng)典：

• 每次選取數(shù)組的最后一個元素為基準(zhǔn)，進(jìn)行排序；
• 將大于基準(zhǔn)的排后邊，小于基準(zhǔn)的排前面，等于基準(zhǔn)的在中間（類似于荷蘭國旗問題）；
• 直至進(jìn)行排序的左邊界=右邊界。

package Sort;public class QuickSort {public static void main(String[] args) {int[] array= {1,5,4,8,3,2};quickSort(array,0,array.length-1);for(int i=0;i<array.length;i++)System.out.print(array[i]+" ");}public static void quickSort(int[] arr,int L,int R) {if(L<R) {int[] p=partation(arr,arr[R],L,R);//獲取等于區(qū)域開始和結(jié)束的下標(biāo)quickSort(arr,L,p[0]-1);//小于區(qū)域quickSort(arr,p[1]+1,R);//大于區(qū)域}}public static int[] partition(int[] arr, int l, int r) {//分為三個區(qū)域：小于，等于，大于，返回等于域的開始和結(jié)束下標(biāo)int less = l - 1;int more = r;while (l < more) {if (arr[l] < arr[r]) {swap(arr, ++less, l++);} else if (arr[l] > arr[r]) {swap(arr, --more, l);} else {l++;}}swap(arr, more, r);//交換基準(zhǔn)和大于域的第一個位置的元素return new int[] {less + 1, more};}public static void swap(int[] arr,int i,int j) {int temp=arr[i];arr[i]=arr[j];arr[j]=temp;} }

運(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)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。