說(shuō)到排序算法，它是計(jì)算機(jī)技術(shù)中最基本使用率最高的算法，需要非常復(fù)雜的算法都會(huì)用到排序，所以了解排序算法的思想和原理，對(duì)于編寫(xiě)軟件非常重要?！肮び破涫卤叵壤淦??！毕胍煤门判蛩惴ǎ捅仨殞?duì)它有足夠深刻的了解，才能在編寫(xiě)中用好。

從計(jì)算機(jī)算法角度來(lái)分析，衡量一個(gè)算法的優(yōu)劣，主要通過(guò)時(shí)間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性和適用范圍來(lái)考慮。

排序算法是非常常用的算法類別，比如信用卡賬單中的交易是按照日期排序的——這種排序很可能使用了某種排序算法。在計(jì)算時(shí)代早期，大家普遍認(rèn)為30%的計(jì)算周期都用在了排序上，今天這個(gè)比例可能降低了，大概是因?yàn)楝F(xiàn)在的排序算法更加高效。現(xiàn)在這個(gè)時(shí)代數(shù)據(jù)可以說(shuō)是無(wú)處不在，而整理數(shù)據(jù)的第一步往往就是進(jìn)行排序。所有的計(jì)算機(jī)系統(tǒng)都實(shí)現(xiàn)了各種排序算法以供系統(tǒng)和用戶使用。 ??

（1）理解數(shù)據(jù)的特點(diǎn)

使用排序處理數(shù)據(jù)有利于理解數(shù)據(jù)的特點(diǎn)，方便我們之后的分析與視覺(jué)化。像一些生活中的例子比如詞典，菜單，如果不是按照一定順序排列的話，人們想要找到自己需要的東西的時(shí)間就會(huì)大大增加。

計(jì)算機(jī)需要處理大規(guī)模的數(shù)據(jù)，排序后，人們可以根據(jù)數(shù)據(jù)的特點(diǎn)和需求來(lái)設(shè)計(jì)計(jì)算機(jī)的后續(xù)處理流程。

（2）降低時(shí)間復(fù)雜度

使用排序預(yù)處理可以降低求解問(wèn)題所需要的時(shí)間復(fù)雜度，通常是一個(gè)以空間換取時(shí)間的平衡。如果一個(gè)排序好的列表需要被多次分析的話，只需要耗費(fèi)一次排序所需要的資源是很劃算的，因?yàn)橹蟮拿看畏治龆伎梢詼p少很多時(shí)間。

（3）穩(wěn)定性方面

如果一個(gè)排序算法能夠保留數(shù)組中重復(fù)元素的相對(duì)位置則可以被稱為是穩(wěn)定的。這個(gè)性質(zhì)在許多情況下很重要。例如：在考慮一個(gè)需要處理大量含有地理位置和時(shí)間戳的事件互聯(lián)網(wǎng)商業(yè)應(yīng)用程序。

首先，我們?cè)跁r(shí)間發(fā)生時(shí)將它們挨個(gè)存儲(chǔ)在一個(gè)數(shù)組中，這樣在數(shù)組中它們已經(jīng)是按照時(shí)間順序排序好了的?，F(xiàn)在假設(shè)在進(jìn)一步處理前將按照地理位置劃分。一種簡(jiǎn)單的方法是將數(shù)組按照位置排序。如果排序算法不是穩(wěn)定的，排序后的每個(gè)城市的交易可能不會(huì)再是按照時(shí)間順序排序的了。

很多情況下，不熟悉排序穩(wěn)定性的程序員在第一次遇到這種情形的時(shí)候會(huì)在使用不穩(wěn)定排序算法后把數(shù)組弄的一團(tuán)糟而一臉懵逼。上一篇文章中我們講到的插入排序和歸并排序都屬于穩(wěn)定的，其他幾個(gè)（選擇，希爾，快速，堆排序）都是不穩(wěn)定的。有很多辦法能夠?qū)⑷我馀判蛩惴ň幊谭€(wěn)定的，但一般只有在穩(wěn)定性是必要的情況下穩(wěn)定的排序算法才有優(yōu)勢(shì)。不要想當(dāng)然認(rèn)為算法具有穩(wěn)定性是理所當(dāng)然的，但事實(shí)上沒(méi)有任何實(shí)際應(yīng)用中常見(jiàn)的算法不是用了大量額外的時(shí)間和空間才做到了這一點(diǎn)（研究人員開(kāi)發(fā)了這樣的算法，但應(yīng)用程序員發(fā)現(xiàn)它們太復(fù)雜了，無(wú)法在實(shí)際開(kāi)發(fā)中使用）。 

（4）排序應(yīng)用

1. 商業(yè)計(jì)算

一般大量的信息都被存儲(chǔ)在大型數(shù)據(jù)庫(kù)中，能夠按照多個(gè)鍵排序以提供搜索效率。

可以說(shuō)沒(méi)有線性對(duì)數(shù)級(jí)別的排序算法就沒(méi)法將這些海量的數(shù)據(jù)進(jìn)行排序，進(jìn)一步處理這些數(shù)據(jù)也會(huì)變得極端困難，甚至是不可能的。

2. 信息搜索

有序的信息可以確保我們可以用經(jīng)典的二分查找法來(lái)進(jìn)行高效的搜索。

3. 運(yùn)籌學(xué)

① 排序算法在調(diào)度中的應(yīng)用

問(wèn)題：假設(shè)我們需要完成N個(gè)任務(wù)，第j個(gè)任務(wù)需要耗時(shí)tj秒，我么需要在完成任務(wù)的同時(shí)，將每個(gè)任務(wù)的平均完成時(shí)間最小化。

思路：只要將任務(wù)按照處理時(shí)間升序排列就可以達(dá)到目標(biāo)。

實(shí)現(xiàn)：因此按照最短優(yōu)先原則，將任務(wù)按耗時(shí)排序，或者插入最小優(yōu)先隊(duì)列中，即可完成目標(biāo)。

② 負(fù)載均衡問(wèn)題

問(wèn)題：假設(shè)我們有M個(gè)相同的處理器以及N個(gè)任務(wù)，目標(biāo)是在盡可能短的時(shí)間內(nèi)在這些處理器上完成所有任務(wù)。

思路：這個(gè)問(wèn)題是NP-困難的，因此實(shí)際上不可能算出最優(yōu)的方法，一種較優(yōu)調(diào)度方法是最大優(yōu)先。將任務(wù)按照耗時(shí)降序排列，將每個(gè)任務(wù)依次分配給當(dāng)前可用的處理器。

實(shí)現(xiàn)：先逆序排序這些任務(wù)，然后為M個(gè)處理器維護(hù)一個(gè)優(yōu)先隊(duì)列，每個(gè)元素的優(yōu)先級(jí)就是對(duì)應(yīng)處理器上運(yùn)行的任務(wù)耗時(shí)之和。每一步都刪去優(yōu)先級(jí)最低的處理器，將下個(gè)任務(wù)分配這個(gè)處理器，然后重新插入優(yōu)先隊(duì)列。

4. 值計(jì)算

一些數(shù)值計(jì)算算法采用優(yōu)先隊(duì)列和排序來(lái)控制計(jì)算中的精確度。

數(shù)值積分的一個(gè)方法，就是使用優(yōu)先隊(duì)列來(lái)存儲(chǔ)一組小間隔中每段的近似精度。積分的過(guò)程就是刪除精確度最低的間隔，并分為兩段，然后將兩段都重新加入優(yōu)先隊(duì)列，直到達(dá)到預(yù)期的精度。

5. 霍夫曼壓縮

這是數(shù)據(jù)壓縮中的一個(gè)經(jīng)典算法。

算法處理的數(shù)據(jù)中每個(gè)元素都有一個(gè)小整數(shù)作為權(quán)重，處理的過(guò)程就是將權(quán)重最小的兩個(gè)元素歸并為一個(gè)新的元素，權(quán)重相加得到新元素的權(quán)重。

使用優(yōu)先隊(duì)列可以立即實(shí)現(xiàn)這個(gè)算法。

其他的幾種數(shù)據(jù)壓縮算法也是基于排序的。

6. 字符串處理

字符串算法常常依賴于排序算法（常用特殊的字符串排序算法）。