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