Java排序算法的分類與介紹

這篇文章主要介紹“Java排序算法的分類與介紹”，在日常操作中，相信很多人在Java排序算法的分類與介紹問題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”Java排序算法的分類與介紹”的疑惑有所幫助！接下來，請(qǐng)跟著小編一起來學(xué)習(xí)吧！

介紹

排序是將一組數(shù)據(jù),依指定的順序進(jìn)行排列的過程

排序分類

內(nèi)部排序:指將需要處理的所有數(shù)據(jù)都加載到內(nèi)部存儲(chǔ)器中進(jìn)行排序.常見的內(nèi)部排序有:直接插入排序、希爾排序、簡(jiǎn)單選擇排序、堆排序、冒泡排序、快速排序、歸并排序、基數(shù)排序。

外部排序:數(shù)據(jù)量過大,無法全部加載到內(nèi)存中,需要借助外部存儲(chǔ)進(jìn)行排序。

算法的時(shí)間復(fù)雜度

度量一個(gè)程序(算法)執(zhí)行時(shí)間的兩種方法:

事后統(tǒng)計(jì)方法這種方法可行,但是有兩個(gè)問題:一是要想對(duì)設(shè)計(jì)的算法的運(yùn)行性能進(jìn)行評(píng)測(cè),需要實(shí)際運(yùn)行該程序;二是所得時(shí)間的統(tǒng)計(jì)量依賴于計(jì)算機(jī)的硬件\軟件等環(huán)境因素,這種方式,要在同一臺(tái)計(jì)算機(jī)的相同狀態(tài)下運(yùn)行,才能比較哪個(gè)算法速度更快.

事前估計(jì)方法通過分析算法的時(shí)間復(fù)雜度來判斷哪個(gè)算法更優(yōu).

時(shí)間頻度

一個(gè)算法花費(fèi)的時(shí)間與算法中語句的執(zhí)行次數(shù)成正比例,哪個(gè)算法中語句執(zhí)行的次數(shù)多,它花費(fèi)時(shí)間就多.一個(gè)算法中語句執(zhí)行次數(shù)稱為語句頻度或時(shí)間頻度.記為T(n).

比如計(jì)算1-100所有數(shù)字之和,有兩種算法

int total=0; int end=100; //for循環(huán)計(jì)算 for(int i=1;i<=end;i++){     total+=i; }

執(zhí)行次數(shù)取決于end長(zhǎng)度.它的T(n)=n+1.

//直接計(jì)算 total = (1+end)*end/2;

直接計(jì)算只需執(zhí)行一次即可,它的T(n) = 1.

估算時(shí)間頻度時(shí)注意事項(xiàng):

• 忽略常數(shù)項(xiàng):如T(n)=2n+20和T(n)=2n,隨著n的變大,20可忽略.

• 忽略低次項(xiàng):如T(n)=2n^2+3n+10和T(n)=2n^2,隨著n的變大,3n+10可以忽略.

• 忽略系數(shù):如T(n)=5n^2+7n和T(n)=3n^2+2n,隨著n的變大,5和3可以忽略.

時(shí)間復(fù)雜度

1. 一般情況下,算法中的基本操作語句的重復(fù)執(zhí)行次數(shù)是問題規(guī)模n的某個(gè)函數(shù),用T(n)表示,若有某個(gè)輔助函數(shù)f(n),使得當(dāng)n趨近于無窮大時(shí),T(n)/f(n)的極限值為不等于零的常數(shù),則稱f(n)是T(n)的同量級(jí)函數(shù).記作T(n)=O(f(n)),稱O(f(n))為算法的漸進(jìn)時(shí)間復(fù)雜度,簡(jiǎn)稱時(shí)間復(fù)雜度.

2. T(n)不同,但是時(shí)間復(fù)雜度可能相同.如:T(n)=n^2+7n+6與T(n)=3n^2+2n+2,他們的T(n)不同,但是時(shí)間復(fù)雜度都是O(n^2)

3. 計(jì)算時(shí)間復(fù)雜度方法

• 用常數(shù)1代替運(yùn)行時(shí)間中的所有加法常數(shù).

• 修改后的運(yùn)行次數(shù)函數(shù)中,只保留最高階項(xiàng).

• 去除最高階項(xiàng)的系數(shù).

常見的時(shí)間復(fù)雜度

• 常數(shù)階O(1)

無論代碼執(zhí)行了多少行,只要是沒有循環(huán)等復(fù)雜結(jié)構(gòu),那這個(gè)代碼的復(fù)雜度就是O(1)

int i = 1; int j = 2; ++i; j++; int m = i+j;

上述代碼在執(zhí)行的時(shí)候,它消耗的時(shí)間并不是隨著某個(gè)變量的增長(zhǎng)而增長(zhǎng),那么無論這類代碼有多長(zhǎng),即使有幾萬幾十萬行,都可以用O(1)來表示它的時(shí)間復(fù)雜度.

• 對(duì)數(shù)階O(log2n)

int i = 1; while(i<n){   i = i*2; }

在while循環(huán)里面,每次都將i乘以2,乘完之后,i距離n就越來越近了.假設(shè)循環(huán)x次之后,i就大于n了,此時(shí)循環(huán)就結(jié)束了,也就是說2的x次方等于n,那么x=  log2n也就是說當(dāng)循環(huán)log2n次以后,這個(gè)代碼就結(jié)束了.因此這個(gè)時(shí)間復(fù)雜度為O(log2n).

• 線性階O(n)

for(i=1;i<=n;i++){   j = i;   j++; }

for循環(huán)里面的代碼會(huì)執(zhí)行n遍,因此它消耗的時(shí)間是隨著n的變化而變化的,因此這類代碼都可以使用O(n)來表示它的時(shí)間復(fù)雜度.

• 線性對(duì)數(shù)階O(nlog2n)

for(int m=1;m<n;m++){   i = 1;   while(i<n){   i = i*2;   } }

這個(gè)線性對(duì)數(shù)階O(log2n)就是將時(shí)間復(fù)雜度為O(logn)的代碼循環(huán)N遍.

• 平方階O(n^2)

即雙層for循環(huán),n*m

• 立方階O(n^3)

3層循環(huán)

• K次方階O(n^k)

k次循環(huán)

• 指數(shù)階O(2^n)

常見的算法時(shí)間復(fù)雜度由小到大依次為:O(1)

平均時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度

1. 平均時(shí)間復(fù)雜度是指所有可能的輸入實(shí)例均以等概率出現(xiàn)的情況下,該算法的運(yùn)行時(shí)間.

2. 最壞情況下的復(fù)雜度稱最壞時(shí)間復(fù)雜度.一般討論的時(shí)間復(fù)雜度是最壞情況下的時(shí)間復(fù)雜度.這樣做的原因是:最壞情況下的時(shí)間復(fù)雜度是算法在任何輸入實(shí)例上運(yùn)行時(shí)間的界限,這就保證了算法的運(yùn)行時(shí)間不會(huì)比最壞情況更長(zhǎng).

3. 平均時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度是否一致,和算法有關(guān)(如下表).

算法的空間復(fù)雜度

1. 類似于時(shí)間復(fù)雜度的討論,一個(gè)算法的空間復(fù)雜度(Space complexity)定義為該算法所耗費(fèi)的存儲(chǔ)空間,它也是問題規(guī)模n的函數(shù).

2. 空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的度量.有的算法需要占用的臨時(shí)工作單元數(shù)與解決問題的規(guī)模n有關(guān),它隨著n的增大而增大,當(dāng)n較大時(shí),將占用較多的存儲(chǔ)單元,例如快速排序和歸并排序就屬于這種情況.

3. 在做算法分析時(shí),主要討論的時(shí)間復(fù)雜度.從用戶體驗(yàn)上看,更看重程序執(zhí)行的速度.一些緩存產(chǎn)品(Redis,Memcache)和算法(基數(shù)排序)本質(zhì)就是用空間換時(shí)間.

到此，關(guān)于“Java排序算法的分類與介紹”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！