資訊專欄INFORMATION COLUMN
摘要：時(shí)間復(fù)雜度的簡(jiǎn)介算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)，描述了算法的執(zhí)行時(shí)間。通常使用大符號(hào)來表示。在進(jìn)行算法分析時(shí)，語句總的執(zhí)行次數(shù)是關(guān)于問題規(guī)模的函數(shù)，進(jìn)而分析隨的變情況來確定的數(shù)量級(jí)。
時(shí)間復(fù)雜度的簡(jiǎn)介
算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)，描述了算法的執(zhí)行時(shí)間。通常使用大O符號(hào)來表示。 在進(jìn)行算法分析時(shí)，語句總的執(zhí)行次數(shù)T(n)是關(guān)于問題規(guī)模n的函數(shù)，進(jìn)而分析T(n)隨n的變 情況來確定T(n)的數(shù)量級(jí)。 一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù),O(f(n)) 分析:隨著n的增長(zhǎng)，算法執(zhí)行的時(shí)間的增長(zhǎng)率和 f(n) 的增長(zhǎng)率成正比， 所以 f(n) 越小，算法的時(shí)間復(fù)雜度越低，算法的效率越高。 常見的時(shí)間復(fù)雜度分析 有幾重for循環(huán)，只有一重則時(shí)間復(fù)雜度為O(n)，二重則為O(n^2)依此類推 如果有二分則為O(logn)，二分例如二分查找，如果一個(gè)for循環(huán)套一個(gè)二分， 那么時(shí)間復(fù)雜度則為O(nlogn) 常見的時(shí)間復(fù)雜度 常數(shù)階O(1),對(duì)數(shù)階O( ),線性階O(n), 線性對(duì)數(shù)階O(nlog2n),平方階O(n^2)，立方階O(n^3),...， k次方階O(n^k),指數(shù)階O(2^n) 隨著問題規(guī)模n的不斷增大，上述時(shí)間復(fù)雜度不斷增大，算法的執(zhí)行效率越低。
快速排序
快速排序的分析
快速排序的流程
快速排序的代碼實(shí)現(xiàn)
public static void main(String[] args) {
//1.定義要排序的數(shù)組
int[] arr = {5,2,6,8,4,3,7};
//2.定義變量low保存數(shù)組中第一個(gè)元素的索引
int low = 0;
//3.定義變量high保存數(shù)組中最后一個(gè)元素的索引
int high = arr.length - 1;
System.out.println("排序前的元素:" + Arrays.toString(arr));
quickSort(arr, low, high);
System.out.println("排序后的元素:" + Arrays.toString(arr));
}
public static void quickSort(int[] arr,int low,int high){
//1.定義變量來保存數(shù)組第一個(gè)元素在數(shù)組拍完序后的位置
int position;
if(low < high){
position = findPosition(arr,low,high);
//2.對(duì)小于數(shù)組中第一個(gè)數(shù)的部分進(jìn)行快速排序
quickSort(arr, low, position - 1);
//3.對(duì)大于數(shù)組中第一個(gè)數(shù)的部分進(jìn)行快速排序
quickSort(arr, position + 1, high);
}
}
//查找第一個(gè)元素在要排序的數(shù)中的位置
//當(dāng)low=high的時(shí)候，low和high的值就是第一個(gè)元素排序完在數(shù)組中的值
public static int findPosition(int[] arr,int low,int high){
//1.定義變量temp保存數(shù)組的第一個(gè)元素
int temp = arr[low];
while(low < high){
//2.high索引對(duì)應(yīng)的元素比temp大，--high
while(low < high && arr[high] >= temp){
--high;
}
//3.循環(huán)結(jié)束,high索引對(duì)應(yīng)的值小于第一個(gè)元素，將high索引對(duì)應(yīng)的值賦值給low索引對(duì)應(yīng)的值
arr[low] = arr[high];
//4.low索引對(duì)應(yīng)的元素比temp小，++low
while(low < high && arr[low] <= temp){
++low;
}
//5.循環(huán)結(jié)束,low索引對(duì)應(yīng)的值大于第一個(gè)元素，將low索引對(duì)應(yīng)的值賦值給high索引對(duì)應(yīng)的值
arr[high] = arr[low];
}
//6.將數(shù)組第一個(gè)元素放置在數(shù)組排序完的位置上
arr[low] = temp;
//7.最外層循環(huán)接收，low=high，第一個(gè)元素在拍完序中的位置就是low和hight的值
return low;
}
快速排序的時(shí)間復(fù)雜度為O(nlogn) 冒泡排序和選擇排序的時(shí)間復(fù)雜度為O(n^2)
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/70429.html
摘要：快速排序的介紹來源百度百科快速排序由在年提出。快速排序是面試出現(xiàn)的可能性比較高的，也是經(jīng)常會(huì)用到的一種排序，應(yīng)該重點(diǎn)掌握。前面一個(gè)章節(jié)已經(jīng)講了遞歸了，那么現(xiàn)在來看快速排序就非常簡(jiǎn)單了。 快速排序就這么簡(jiǎn)單 從前面已經(jīng)講解了冒泡排序、選擇排序、插入排序了，本章主要講解的是快速排序，希望大家看完能夠理解并手寫出快速排序的代碼，然后就通過面試了！如果我寫得有錯(cuò)誤的地方也請(qǐng)大家在評(píng)論下指出。 ...
摘要：今天跟大家分享多種排序算法里使用較廣泛，速度快的排序算法快速排序法平均時(shí)間復(fù)雜度為。快速排序法的原理快速排序是一種劃分交換排序，它采用分治的策略，通常稱其為分治法。 HTML5學(xué)堂-碼匠：前幾期算法之旅跟大家分享了冒泡排序法和選擇排序法，它們都屬于時(shí)間復(fù)雜度為O(n^2)的慢排序。今天跟大家分享多種排序算法里使用較廣泛，速度快的排序算法—— 快速排序法 [ 平均時(shí)間復(fù)雜度為O (n l...
摘要：實(shí)現(xiàn)快速排序介紹通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。 冒泡排序 介紹 重復(fù)遍歷要排序的元素列，依次比較兩個(gè)相鄰的元素，前一個(gè)元素若比后一個(gè)元素大則互換位置。以升序排序?yàn)槔?，最大的元素?huì)在第一次遍歷后冒泡到數(shù)組的末端。假如數(shù)組...
標(biāo)準(zhǔn)庫中的sort函數(shù)，是快速排序算法的典型實(shí)現(xiàn)。算法將含有n個(gè)元素的序列排序，平均需要 O(n log n) 時(shí)間。 上周，我提出了測(cè)試一個(gè)程序的性能比測(cè)試其功能更難這個(gè)觀點(diǎn)。確認(rèn)程序的性能達(dá)到標(biāo)準(zhǔn)以及確定標(biāo)準(zhǔn)的含義都十分困難。 接下來，我會(huì)繼續(xù)討論標(biāo)準(zhǔn)庫中的sort(排序)函數(shù)。sort函數(shù)實(shí)現(xiàn)了快速排序算法，快速排序算法平均可以在 O(n log n) 時(shí)間內(nèi)對(duì)含有n個(gè)元素的序列進(jìn)行排序...
閱讀 1330·2023-04-25 17:05
閱讀 3081·2021-11-19 09:40
閱讀 3838·2021-11-18 10:02
閱讀 1823·2021-09-23 11:45
閱讀 3094·2021-08-20 09:36
閱讀 2850·2021-08-13 15:07
閱讀 1205·2019-08-30 15:55
閱讀 2542·2019-08-30 14:11
