所謂排序，即將原來無序的一個序列重新排列成有序的序列。

排序方法中涉及到穩(wěn)定性，所謂穩(wěn)定性，是指待排序的序列中有兩個或兩個以上相同的項，在排序前和排序后看這些相同項的相對位置有沒有發(fā)生變化，如果沒有發(fā)生變化，即該排序方法是穩(wěn)定的，如果發(fā)生變化，則說明該排序方法是不穩(wěn)定的。

如果記錄中關鍵字不能重復，則排序結(jié)果是唯一的，那么選擇的排序方法穩(wěn)定與否就無關緊要了；如果關鍵字可以重復，則在選擇排序方法時，就要根據(jù)具體的需求來考慮選擇穩(wěn)定還是不穩(wěn)定的排序方法。那么，哪些排序算法是不穩(wěn)定的呢？

“快些選堆”：其中“快”指快速排序，“些”指希爾排序，“選”指選擇排序，“堆”指堆排序，即這四種排序方法是不穩(wěn)定的，其他自然都是穩(wěn)定的。

排序算法分類

1、插入類排序

即在一個已經(jīng)有序的序列中，插入一個新的記錄，就好比軍訓排隊，已經(jīng)排好一個縱隊，這時來了個新家伙，于是新來的“插入”這個隊伍中的合適位置。這類排序有：直接插入排序、折半插入排序、希爾排序。

2、交換類排序

該類方法的核心是“交換”，即每趟排序，都是通過一系列的“交換”動作完成的，如軍訓排隊時，教官說：你比旁邊的高，你倆交換下，還比下一個高就繼續(xù)交換。這類排序有：冒泡排序、快速排序。

3、選擇類排序

該方法的核心是“選擇”，即每趟排序都選出一個最小（或最大）的記錄，把它和序列中的第一個（或最后一個）記錄交換，這樣最小（或最大）的記錄到位。如軍訓排隊時，教官選出個子最小的同學，讓他和第一個位置的同學交換，剩下的繼續(xù)選擇。這類排序有：選擇排序、堆排序。

4、歸并類排序

所謂歸并，就是將兩個或兩個以上的有序序列合并成一個新的有序序列。如軍訓排隊時，教官說：每個人先和旁邊的人組成二人組，組內(nèi)排好隊，二人組和旁邊的二人組組成四人組，內(nèi)部再排好隊，以此類推，直到最后全部同學都歸并到一個組中并排好序。這類排序有：（二路）歸并排序。

5、基數(shù)類排序

此類方法較為特別，是基于多關鍵字排序的思想，把一個邏輯關鍵字拆分成多個關鍵字，如一副撲克牌，按照基數(shù)排序思想可以先按花色排序，則分成4堆，每堆再按A-K的順序排序，使得整副撲克牌最終有序。

排序算法分析

本文主要分析的排序算法有：冒泡排序、選擇排序、插入排序、希爾排序、快速排序、歸并排序、堆排序。

交換算法

由于大部分排序算法中使用到兩個記錄相互交換的動作，因此將交換動作單獨封裝出來，便于各排序算法使用。

1. //交換函數(shù) 
2. Array.prototype.swap = function(i, j) { 
3.   var temp = this[i]; 
4.    this[i] = this[j]; 
5.    this[j] = temp; 
6. } 

插入排序

算法思想：每趟將一個待排序的關鍵字，按照其關鍵字值的大小插入到已經(jīng)排好的部分序列的適當位置上，直到插入完成。

1. //插入排序 
2. Array.prototype.insertionSort = function() { 
3.     for (var i = 1; i < this.length; ++i) 
4.     { 
5.         var j = i, 
6.             value = this

    1/6    1 2 3 4 5 6 下一頁 尾頁