摘要:通常情況下,快速排序的時間復雜度為,但在最壞情況下它的時間復雜度會退化至,不過我們可以通過對輸入數組進行隨機化打亂元素的排列順序來避免最壞情況的發生。
寫在最前面
導師貪腐出逃美國,兩年未歸,可憐了我。拿了小米和美團的offer,要被延期,offer失效,工作重新找。把準備過程紀錄下來,共勉。
冒泡算法最初級
public void bubbleSort(int[] a){ int len = a.length; for(int i = 0; i < len; i++){ for(int j = 1; j < len; j++){ if(a[j - 1] > a[j]){ int temp = a[j]; a[j] = a[j - 1]; a[j - 1] = temp; } } } }
小優化
public void bubbleSort(int[] a){ int len = a.length; for(int i = 0; i < len; i++){ for(int j = 1; j < len - i; j++){ if(a[j - 1] > a[j]){ int temp = a[j]; a[j] = a[j - 1]; a[j - 1] = temp; } } } }
大優化,一次冒泡過程沒有交換,直接退出排序
public void bubbleSort(int[] a){ int len = a.length; boolean flag = true; while(flag){ flag = false; for(int j = 0; j < len - 1; j++){ if(a[j] > a[j + 1]){ int temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; flag = true; } } } }快速排序
快速排序是目前應用最廣泛的排序算法之一,它是一般場景中大規模數據排序的首選,它的實際性能要好于歸并排序。通常情況下,快速排序的時間復雜度為O(nlogn),但在最壞情況下它的時間復雜度會退化至O(n^2),不過我們可以通過對輸入數組進行“隨機化”(打亂元素的排列順序)來避免最壞情況的發生。除了實際執行性能好,快速排序的另一個優勢是它能夠實現“原地排序”,也就是說它幾乎不需要額外的空間來輔助排序。
public static void quickSort(int[] a){ qSort(a, 0, a.length - 1); } private static void qSort(int[] a, int low, int high){ if(low < high){ int pivot = partition(a, low, high); qSort(a, low, pivot - 1); qSort(a, pivot + 1, high); } } private static void partition(int[] a, int low, int high){ int pivotValue = a[low]; while(low < high){ while(low < high && a[high] >= pivotValue){ high--; } a[low] = a[high]; while(low < high && a[low] <= pivotValue){ low++; } a[high] = a[low]; } a[low] = pivotValue; return low; }
穩定性的概念并不復雜,它只表示兩個值相同的元素在排序前后是否有位置變化。如果前后位置變化,則排序算法是不穩定的,否則是穩定的。穩定性的定義符合常理,兩個值相同的元素無需再次交換位置,交換位置是做了一次無用功。
兩個循環在進行元素比較時,分別用了小于和大于操作(也可以改用小于等于和大于等于,但是對性能沒有影響)。這就意味著如果出現和pivot值相同的元素,它都會被作為交換對象而移動到pivot的前面或者后面,這就出現了值相同的元素會交換順序的問題,因而是不穩定的。
本節參考 http://blog.csdn.net/yutianzu...
優化選取樞軸,優化不必要的交換
三數取中,即取三個關鍵字先進行排序,將中間數作為樞軸, 一般是取左端、右端和中間三個數, 也可以隨機選取。
修改partition算法
private static int partition(int[] a, int low, int high){ choosePivotValue(a, low, high); int pivotValue = a[low]; while(low < high){ while(low < high && a[high] > pivotValue){ high--; } //swap(a,low ,high);交換 //采用替換而不是交換的方式進行操作 a[low] = a[high]; while(low < high && a[low] < pivotValue){ low++; } a[high] = a[low]; } a[low] = pivotValue; return low; } private static void swap(int[] a,int low,int high){ int temp = a[low]; a[low] = a[high]; a[high] = temp; } //使中間值處于a[low]的位置 private static void choosePivotValue(int[] a,int low,int high){ int mid = (low + high) / 2; if(a[low] > a[high]){ // 保證左端較小 swap(a, low, high); } if(a[mid] > a[high]){//保證中間較小 swap(a, mid, high); } if(a[mid] > a[low]){//保證中間較小 swap(a, low, mid); } }
優化小數組時的排序方案
快速排序適用于非常大的數組的解決辦法, 那么相反的情況,如果數組非常小,其實快速排序反而不如直接插入排序來得更好(直接插入是簡單排序中性能最好的)。其原因在于快速排序用到了遞歸操作,在大量數據排序時,這點性能影響相對于它的整體算法優勢是可以忽略的,但如果數組只有幾個記錄需要排序時,這就成了大材小用,因此我們需要改進一下 qSort函數。
public static void qSort(int[] a, int low, int high){ if((high - low) > MAX_LENGTH){ int pivot = partition(a, low, high); qSort(a, low, pivot - 1); qSort(a, pivot + 1, high); }else{ insertSort(a); } } private static void insertSort(int[] a){ for(int i = 1; i < a.length; i++){ int key = a[i]; int j = i - 1; while(j >= 0 && a[j] > key){ a[j + 1] = a[j]; } a[j + 1] = key; } }
優化遞歸操作
遞歸對性能是有一定影響的, qSort 函數在其尾部有兩次遞歸操作。
如果待排序的序列劃分極端不平衡,遞歸深度將趨近與N ,而不是平衡時的 logN,就不僅僅是速度快慢的問題了,棧的大小是很有限的,每次遞歸調用都會耗費一定的空間 ,函數的參數越多,每次遞歸耗費的空間也越多。如果能減少遞歸,將會提高性能。我們對 qSort 實施尾遞歸優化。
public static void qSort(int[] a, int low, int high){ if((high - low) > MAX_LENGTH){ while(low < high){ int pivot = partition(a, low, high); qSort(a, low, pivot - 1); low = pivot + 1; } }else{ insertSort(a); } }
當我們將 if 改成 while 后,因為第一次遞歸以后,變量low就沒有用處了,所以可以將pivot+1 賦值給low,再循環后,來一次 partition(arr,low,high)時,其效果等同于“qSort(arr, pivot+1, high);”。結果相同,但因采用迭代而不是遞歸的方法可以縮減堆棧深度,從而提高了整體性能。
歸并排序本節參考 http://blog.csdn.net/scgaligu...
public static void sort(int[] a, int low, int high){ int mid = (low + high) / 2; sort(a, low, mid); sort(a, mid + 1, high); merge(a, low, mid, high); } private static void merge(int[] a, int low, int mid, int high){ int i = low; int j = mid + 1; int k = 0; int[] temp = new int[high - low + 1]; while(i <= mid && j <= high){ if(a[i] < a[j]){ temp[k++] = a[i++]; }else{ temp[k++] = a[j++]; } } while(i <= mid){ temp[k++] = a[i++]; } while(j <= high){ temp[k++] = a[j++]; } for(k = 0; k < temp.length; k++){ a[low + k] = temp[k]; } }選擇排序
public static void choseSort(int[] a){ for(int i = 0; i < a.length; i++){ int lowIndex = i; for(int j = i; j < a.length; j++){ if(a[j] < a[lowIndex]){ lowIndex = j; } } int temp = a[i]; a[i] = a[lowIndex]; a[lowIndex] = temp; } }插入排序
public static void insertSort(int[] a){ for(int i = 1; i < a.length; i++){ int j = i - 1; int key = a[i]; while(j >= 0 && a[j] > key){ a[j + 1] = a[j]; j--; } a[j + 1] = key; } }
本文參考 http://blog.csdn.net/xsf50717...
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/70125.html
摘要:一基礎接口的意義百度規范擴展回調抽象類的意義想不想通過一線互聯網公司面試文檔整理為電子書掘金簡介谷歌求職記我花了八個月準備谷歌面試掘金原文鏈接翻譯者 【面試寶典】從對象深入分析 Java 中實例變量和類變量的區別 - 掘金原創文章,轉載請務必保留原出處為:http://www.54tianzhisheng.cn/... , 歡迎訪問我的站點,閱讀更多有深度的文章。 實例變量 和 類變量...
摘要:作者重慶森林鏈接來源牛客網整個三月份通過??途W和網友分享的經驗學到了很多東西,現在反饋一下我的面試經歷,希望對同學們有幫助。個人情況大三本方向渣碩,經過實驗室學長內推,于三月底完成面試。校招是實力和運氣的結合,缺一不可。 歡迎關注我的微信公眾號:Java面試通關手冊(堅持原創,分享美文,分享各種Java學習資源,面試題,以及企業級Java實戰項目回復關鍵字免費領?。簊howImg(h...
摘要:算法名稱描述優點缺點標記清除算法暫停除了線程以外的所有線程算法分為標記和清除兩個階段首1 回顧我的時間線 在本文的開頭,先分享一下自己的春招經歷吧: 各位掘友大家好,我是練習時長快一年的Android小蔡雞,喜歡看源碼,逛掘金,寫技術文章...... 好了好,不開玩笑了OWO,今年春招投了許多簡歷的,但是被撈的只有阿里,頭條和美團,一路下來挺不容易的. 個人認為在春招中運氣>性格>三觀>技術...
摘要:正確做法是給加索引,還有聯合索引,并不能避免全表掃描。 前言:有收獲的話請加顆小星星,沒有收獲的話可以 反對 沒有幫助 舉報三連 有心的同學應該會看到我這個noteBook下面的其它知識,希望對你們有些許幫助。 本文地址 時間點:2017-11 一個16年畢業生所經歷的php面試 一、什么是面試 二、面試準備 1. 問:什么時候開始準備? 2. 問:怎么準備? 三、面試...
閱讀 2877·2021-09-22 15:54
閱讀 1886·2019-08-30 15:53
閱讀 2239·2019-08-29 16:33
閱讀 1416·2019-08-29 12:29
閱讀 1386·2019-08-26 11:41
閱讀 2366·2019-08-26 11:34
閱讀 2946·2019-08-23 16:12
閱讀 1420·2019-08-23 15:56