摘要：排序算法索引待更數(shù)據(jù)結(jié)構(gòu)與算法桶排序數(shù)據(jù)結(jié)構(gòu)與算法快速排序時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)，其定量的描述了一個(gè)算法運(yùn)行時(shí)間和輸入規(guī)模之間的關(guān)系。總結(jié)在介紹排序算法之前，本篇先對(duì)后面排序算法的基本概念說(shuō)叨說(shuō)叨，打下一個(gè)基礎(chǔ)鋪墊。
聲明：碼字不易，轉(zhuǎn)載請(qǐng)注明出處，歡迎文章下方討論交流。
前言：Java數(shù)據(jù)結(jié)構(gòu)與算法專題會(huì)不定時(shí)更新，歡迎各位讀者監(jiān)督。在介紹各類排序算法之前，本篇先聊聊算法中的一些必備知識(shí)。
0、排序算法索引(待更)
Java數(shù)據(jù)結(jié)構(gòu)與算法——桶排序
Java數(shù)據(jù)結(jié)構(gòu)與算法——快速排序
1、時(shí)間復(fù)雜度
算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)，其定量的描述了一個(gè)算法運(yùn)行時(shí)間和輸入規(guī)模之間的關(guān)系。通常用O表示，且不包括這個(gè)函數(shù)的低階和首項(xiàng)系數(shù)。如果一個(gè)算法的執(zhí)行時(shí)間為2n^2+5n+4,那么該算法時(shí)間復(fù)雜度就可以表示為O(n^2)。
一般的時(shí)間復(fù)雜度，由好到壞大概有這么幾種O(1)、O(logn)、O(n)、O(nlogn)、O(n^k)(k>=2),一般情況下，當(dāng)算法時(shí)間復(fù)雜度高于O(n^2)時(shí)，性能就變得相當(dāng)差，此時(shí)就該想辦法尋求更優(yōu)的方案。
O(n^2)的情形
for(int i=0;i
O(nlogn)的情形
for(int i=0;i
O(logn)的情形
for(int i=0;i
O(1)的情形
//與n無(wú)關(guān)的有限次的表達(dá)式，例如賦值，簡(jiǎn)單的運(yùn)算等
2、空間復(fù)雜度
空間復(fù)雜度是一個(gè)算法執(zhí)行過(guò)程中所消耗的臨時(shí)空間的一個(gè)度量。同時(shí)間復(fù)雜度一樣，也不包括這個(gè)度量函數(shù)的低階項(xiàng)和首項(xiàng)系數(shù)。相對(duì)的應(yīng)的，空間復(fù)雜度也有O(1)、O(logn)、O(n)、O(nlogn)、O(n^k)(k>=2)。
3、穩(wěn)定性
在排序算法中，評(píng)估一個(gè)算法的優(yōu)劣，除了時(shí)間復(fù)雜度和空間復(fù)雜度以外，還有一個(gè)衡量指標(biāo)就是穩(wěn)定性。在一個(gè)待排序的序列中，可能存在多個(gè)相等的項(xiàng)，經(jīng)過(guò)排序后如果這些項(xiàng)的相對(duì)次序保持不變，則我們說(shuō)這個(gè)算法是穩(wěn)定的，否則就是不穩(wěn)定的。
研究穩(wěn)定性的意義在于，如果算法是穩(wěn)定的，那么第一個(gè)元素排序的結(jié)果可以被第二個(gè)等值的元素在排序時(shí)所用，也就是說(shuō)可以避免多余的比較。
4、總結(jié)
在介紹排序算法之前，本篇先對(duì)后面排序算法的基本概念說(shuō)叨說(shuō)叨，打下一個(gè)基礎(chǔ)鋪墊。
排序算法索引(待更)
Java數(shù)據(jù)結(jié)構(gòu)與算法——桶排序
Java數(shù)據(jù)結(jié)構(gòu)與算法——快速排序
碼字不易，如對(duì)您有幫助，歡迎點(diǎn)贊收藏打賞^_^
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.specialneedsforspecialkids.com/yun/71060.html
