[TOC]
前言
這是《Java數據結構與算法》一書中關于排序算法部分的讀書筆記纽匙。
最近想看看算法方面的東西，便先整理下以前的筆記，發(fā)現關于排序算法這塊以前的筆記太潦草，這幾日重新看書修整一番冕房，現在應該可以看入眼了趁矾，如果還是寫得不好详拙，那是體育老師的鍋。
不變性：在很多算法中，有些條件在算法執(zhí)行時是不變的，這些條件被稱為不變性。如冒泡中蒿辙，out右邊的所有數據項為有序俺叭，在算法的整個運行過程中這個條件始終為真耗跛。(一開始，out右邊數為0)
初級
冒泡排序
執(zhí)行非常慢，概念上最簡單。
int out,in;
for(out = size- 1;out > 1;out--){ //outer loop(backward)
for(in = 0;in < out;in++){ //inter loop(forward)
if(a[in] > a[in + 1]){ //out of order?
swap(in,in + 1); //swap them
}
}
}
在內部循環(huán)中就是一個冒泡腹缩，從頭到尾，比較左右兩個，如果逆序就交換位置，最大的那一項會一直被交換，直到排最后猖闪。1,2比較柑爸，(交換)，2,3比較，3和4比較，4和5比較。這里的數字指的是位置竭宰，假如2是5個數據中最大的一個，1和2比較孕豹，不變椅野，2和3比較，二者交換位置妖爷，最大值到了3位置蝶涩，3和4比較，最大值到了4位置絮识，再到5位置绿聘。冒泡，冒上來次舌。
在外層循環(huán)中熄攘，是給內層循環(huán)設置數據比較的最后一項，因為下標大于out的數據項都已經排好序了彼念，是最大的放后面挪圾，不需要再比較了。變量out在每完成一個內層循環(huán)后逐沙，就左移一位哲思。
冒泡的效率: 比較的次數，(N-1) + (N-2) + (N-3) + ...+ 1= N*(N-1)/2,交換的次數取平均NxN/4,這個算法0(N^2)
選擇排序
我覺得名字起得不好吩案，體現不出這個算法的思想(主要是冒泡算法太形象了)棚赔。
思想：比較所有的數據項，取出最小值徘郭，放左邊忆嗜。比較剩下的數據，取最小崎岂，放最左。闪湾。冲甘。。
內層循環(huán)中途样，每一個in的新位置江醇，數據項a[in]和a[min]比較，如果a[in]更小何暇，則min被賦值為in的值陶夜，這里只是下標，沒交換裆站。到一次內層循環(huán)結束条辟，再交換數據項润梯。這樣陋葡，最小數據項就會一直被放在左邊。
比較的次數和冒泡是一樣的，但是交換的次數小撵溃。因為交換數據需要在內存中移動，時間上要多(java語言中粘驰，影響不大椿胯，只是改變引用位置而已)
int out,in,min;
for(out = 0;out<nElems - 1;out++){ //outer loop
min = out; //minimum
for(in = out + 1;in < nElems;in++){ //inner loop
if(a[in] < a[min]){ //if min greater
min = in; //we have a new min
}
swap(out,min); //swap them
}
}
插入排序
思想：假設左邊部分已經排序好了，從某個位置(比如10)開始無序魂爪，將10賦值給一臨時值先舷，然后和前面的數據比較，如果9位置比10大滓侍，就9右移一位蒋川，繼續(xù)和8比較。粗井。尔破。直到到數據的最左邊或找到比10位置數據小的某數據，放在它的右邊浇衬，10位置的數據就排好了懒构。
在大多數情況下，插入算法仍然需要0(N^2)的時間耘擂，但比冒泡快一倍胆剧，比選擇排序也還要快一點。經常被用在較復雜的排序算法的最后階段醉冤，例如快速排序秩霍。
int in,out;
for(out = 1;out < nElems; out++){ //out is dividing line
long temp = a[out]; //remove marked item
in = out; //start shifts at out
while(in > 0 && a[in - 1] >= temp){ //until one is smaller,
a[in] = a[in -1] //shift item right
--in;
}
a[in] = temp; //insert marked item
}
外層的for循環(huán)中，out變量從1開始蚁阳，向右移動,它標記了未排序部分的最左端的數據铃绒。
而在內層while循環(huán)中，in變量從out變量開始螺捐，向左移動颠悬，知道temp變量小于in所指的數組數據項，或者它已經不能再往左移動為止定血。while循環(huán)的每一次都向右移動了一個排序的數據項赔癌。
在每次結束時，在將temp位置的項插入后澜沟，比outer變量下標號小的數據項都是局部有序的灾票。
比較次數，1+2+3+...+(N-1) = Nx(N-1)/2茫虽，而因為每一次排序發(fā)現插入點之前刊苍，平均只有全體數據項的一半真的進行了比較既们，所以是N*(N-1)/2 /2
復制的次數大致等于比較的次數。復制和交換的時間耗費不同班缰。相對于隨機數據贤壁，這個算法比冒泡快一倍，比選擇排序略快埠忘。
對于已經有序或基本有序的數據來說脾拆，插入排序要好得多。對于逆序排列的數據莹妒，每次比較和移動都會執(zhí)行名船，所以插入排序不比冒泡排序快。
中級
歸并排序
只要O(N * logN)旨怠，而冒泡排序渠驼，選擇排序，插入排序都要用O(N * N);.
歸并排序的思想是：將一個數組分成兩半鉴腻，然后分別排序迷扇，然后將數組的兩半合并，合并的時候需要比較大小(合并的時候還要考慮兩小數組還有沒有數據爽哎，即有可能一邊有蜓席，另一邊沒有)。至于如何排序1/2半的數組课锌，當然是再分成兩個1/4數組厨内，再排序。渺贤。雏胃。直到分割的小數組只有1個數據項，不用排序了志鞍。這是用到遞歸的思想
歸并排序的缺點瞭亮，需要在存儲器中有另一個大小等于被排序的數據項數目的空間，用來復制分割出來的小數組固棚。
歸并算法的效率由來：需要復制log2N層(分子數組)街州，每一個層都是N個數據，所以是NxlogN.
int[] workSpace = new int[source.length];
recMergerSort(source,workSpace,0,length-1);
private static void recMergeSort(int[] source ,int[] workSpace,int lowerBound, int upperBound){
if (lowerBound == upperBound){
return; // if range is 1,no use sorting
} else {
int mid = (lowerBound + upperBound) / 2; //find midpoint
recMergeSort(source,workSpace,lowerBound,mid); // sort low half
recMergeSort(source,workSpace,mid + 1,upperBound); // sort high half
merge(source,workSpace,lowerBound,mid+1 ,upperBound); //merge them
}
}
private static void merge(int[] source,int[] workPlace, int lowPtr, int highPtr, int upperBound) {
int j = 0; // workspace index
int lowerBound = lowPtr;
int mid = highPtr - 1;
int n = upperBound - lowerBound + 1; // size of items
while (lowPtr <= mid && highPtr <= upperBound){
if (source[lowPtr] < source[highPtr]){
workPlace[j++] = source[lowPtr++];
} else {
workPlace[j++] = source[highPtr++]
}
}
while (lowPtr <= mid){
workPlace[j++] = source[lowPtr++];
}
while (highPtr <= upperBound){
workPlace[j++] = source[highPtr++];
}
for (j = 0;j < n; j++) {
source[lowerBound + j] = workPlace[j];
}
}
高級
希爾排序玻孟，快速排序
希爾排序大約需要O(Nx(logN)^2)時間，快速排序需要O(N*logN)時間鳍征。
而這兩種算法都不需要大量的輔助存儲空間黍翎，不同于歸并算法。
快速排序是所有通用排序算法中最快的一個排序算法艳丛。
希爾排序
希爾排序基于插入排序匣掸，但增加了一個新的特性趟紊，大大地提高了插入排序的執(zhí)行效率。(希爾是個人名碰酝。霎匈。。)
改進的地方：插入算法中送爸，如果一個數據比較小而居于最右邊铛嘱，那么它需要一個一個地移動所有中間的數據項，效率比較低袭厂。
希爾排序通過加入插入排序中元素之間的間隔墨吓，并在這些有間隔的元素中進行插入排序，從而使數據項能大跨度地移動纹磺。當這些數據項排過一趟序后帖烘，減小數據項的間隔。再進行排序橄杨，依次進行下去秘症。間隔被稱為增量，用h表示.
進行過幾次增量排序后式矫，所有的元素離它再最終有序序列中的位置相差不大乡摹，數組達到"基本有序",這時再來插入排序，移動量非常小衷佃。
當h值很大的時候趟卸，數據項每一趟排序需要移動元素的個數很少，但數據項移動的距離很長氏义，這是非常有效率的锄列。當h減少時，每一趟排序需要移動的元素的個數增多惯悠，但是此時數據項已經接近于它們排序后最終的位置邻邮，這對于插入排序可以更有效率。
其中克婶，h = h x 3 +1, h = (h -1) / 3,是經驗值筒严。
java代碼實現：
class ArraySh{
private long[] theArray;
private int nElems;
public ArraySh(int max){
theArray = new long[max];
nElems = 0;
}
public void insert(long value){
theArray[nElems] = value;
nElems++;
}
public void shellSort(){
int inner,outer;
long temp;
int h = 1;
while(h <= nElems / 3){
h = h * 3 + 1;
}
while(h > 0){
for(outer=h;outer<nElems;outer++){
temp = theArray[outer];
inner = outer;
while(inner > h - 1 && theArray[inner - h] >= temp){
theArray[inner] = theArray[inner - h];
inner -= h;
}
theArray[inner] = temp;
}
h = (h-1)/3;
}
}
}
劃分算法
劃分是快速排序的根本機制，但是劃分本身也是一個有用的操作情萤，這里單講劃分的算法鸭蛙。
劃分數據就是把數據分為兩組，使所有關鍵字大于特定值的數據項在一組筋岛，使所有關鍵字小于特定值的數據項在另一組娶视。
劃分算法由兩個指針開始工作，兩個指針分別指向數組的兩頭。在左邊的指針肪获，leftPtr寝凌，向右移動，而在右邊的指針孝赫，rightPtr较木，向左移動。
實際上青柄，leftPtr初始化時是在第一個數據項的左邊一位(-1)伐债，rightPtr是在最后一個數據項的右邊一位(size)，這是因為在工作之前刹前，它們都要分別的加一和減一泳赋。
停止和交換：當leftPtr遇到比樞紐(特定值，劃分值)小的數據項時喇喉，它繼續(xù)右移祖今，因為這個數據項的位置已經處在數組的正確一邊了。但是拣技，當遇到比樞紐大的數據項時千诬，它就停下來。類似的膏斤，當rightPtr遇到小于樞紐的數據項時徐绑，它也停下來。兩個內層的while循環(huán)莫辨，控制這個掃面過程傲茄，當兩個都停下來時，要么指針到頭要么遇到錯誤的數據(大小比較不對)沮榜，做交換(更換位置盘榨，正確排列了)。
當兩個指針最終相遇的時候蟆融，劃分過程結束草巡，并且推出這個外層的while循環(huán)。
java代碼實現：
class ArrayPar{
private long[] theArray;
private int nElems;
public ArrayPar(int max){
theArray = new long[max];
nElems = 0;
}
public void insert(long value){
theArray[nElems] = value;
nElems++;
}
public int partitionIt(int left,int right,long pivot){
int leftPtr = left - 1;
int rightPtr = right + 1;
while(true){
//這里需要檢查邊界型酥，povit是外界設定山憨，對效率影響很大，在快速排序中有更巧妙的設定方法
while(leftPtr < right && theArray[++leftPtr] < povit); //find bigger item
while(rightPtr > left && theArray[--rightPtr] > povit); //find smaller item
if(leftPtr >= rightPtr){ //if pointers cross, partition done
break;
} else {
swap(leftPtr,rightPtr);
}
}
return leftPtr;
}
}
精巧的代碼分析
這個while循環(huán)中的代碼相當精巧弥喉。舉例來說郁竟，想要從內部循環(huán)條件中除去加1操作符，并且用這個加1操作符代替空操作指令語句(空操作指令指只包括一個分號的語句由境，它表示不做任何操作)枪孩。
可以把如下代碼
while(leftPtr < right && theArray[++leftPtr] < pivot);
改為
while(leftPtr < right && theArray[leftPtr] < pivot) {
++leftPtr
};
這些改變使指針的初始值分別設為left,right，比設為left-1,right+1要更為清晰。
但是蔑舞，這些改變導致只有在滿足條件的情況下指針才會加1.而指針在任何情況下都必須移動，所以空操作指令是最有效的解決辦法嘹屯。
快速排序
最流行的排序算法攻询，時間復雜度為O(N*logN)。雖然不覺得這種行為好州弟，但有的公司喜歡筆試時讓人手寫快排(一些開發(fā)者如是說)钧栖。
原理是：把一個數組劃分為兩個子數組，這里用到劃分算法婆翔，左子數組的數據項都小于右子數組的數據項拯杠，然后遞歸地調用自身為每個子數組進行快速排序來實現，最后使用插入排序啃奴。
在這個算法中劃分的關鍵值(樞紐)的選擇非常重要潭陪。
最初思想，選用數組最右邊的值為pivot,進行一次劃分最蕾，劃分的結果就是left->mid-1, mid->right-1, right(這個位置的值是pivot)依溯，三部分，然后交換mid和right的值(劃分算法的leftPtr在停止時會停在mid位置)瘟则，這樣pivot就到中間黎炉，而小于pivot的值全在左邊，大于的值全在右邊醋拧，數組的排序不受影響慷嗜。
下面的排序從left到pivot-1,pivot+到right。中間項不參與劃分丹壕。
最初思想的java代碼實現：
class ArrayIns{
private long[] theArray;
private int nElems; // elements number, or size
public ArrayIns(int max){
theArray = new long[max];
nElems = 0;
}
public void insert(long value){
theArray[nElems] = value;
nElems++;
}
public void quickSort(){
recQuickSort(0,nElems - 1);
}
private void recQuickSort(int left,int right){
if(right - left <= 0) { // if size <= 1, already sorted
return;
} else {
long pivot = theArray[right]; // rightmost item
int partition = partitionIt(left,right,pivot);
recQuickSort(left,partition - 1); //sort left side
recQuickSort(partition+1,right); //sort right side
}
} // end recQuickSort()
private int partitionIt(int left,int right,long pivot){
int leftPtr = left - 1;
int rightPtr = right; //這里設定最右為pivot庆械，所以從right-1開始劃分，下面代碼會-1
while(true){
while(theArray[++leftPtr] < pivot);
while(rightPtr > 0 && theArray[--rightPtr] > pivot);
if(leftPtr >= rightPtr){
break;
} else {
swap(leftPtr,rightPtr);
}
} // end while(true)
swap(leftPtr,right); //restore pivot 當0->right-1劃分好了之后雀费，交換right和leftPtr的位置干奢，將pivot移動到中間，
return leftPtr; //return pivot location
}
}
最初思想中盏袄，使用最右為pivot忿峻，如果數據本身有序，那么pivot會是最小or最大(數組逆序or正序)辕羽，不能起劃分作用逛尚，效率低下。
(為什么不掃描要排序的全部數據刁愿，取中間值绰寞，因為這個做法比排序本身還要費時間，不可行)
進一步優(yōu)化："三數據項取中(median-of-three)"，找數組里第一個滤钱，最后一個觉壶，中間位置數據項的居中數據項值。
三數據取中的一個好處：可以在第二個內部while循環(huán)中取消rightPtr>left的判斷(left是數組的最左件缸，避免rightPtr跑出數組)铜靶，因為三數據取中時，也對三個數據項進行了排序他炊，已經有序争剿。
還有一個好處：對左端，右端中間的數據項排序之后痊末，劃分過程就不需要再考慮這三個數據項了蚕苇。劃分可以從left+1,right-1開始。
再一步提升凿叠，使用三數據項取中劃分方法涩笤，則必須要遵循快速排序算法不能執(zhí)行三個或者少于三個數據項的劃分的規(guī)則。數字3被稱為切割點幔嫂。
本例子中處理小劃分的方法是manualSort()辆它，代碼很簡單，只是排序3個數據項或以下的數據履恩。
處理小劃分的另一個選擇是使用插入排序锰茉，數量小插入排序效率也很高。也可以把切割點設定為別的數切心，推薦使用9.最好的選擇取決于計算機飒筑，操作系統...等。替換掉recQuickSort()中的if(size <= 3) manualSort()绽昏，改用if(size <= 9) insertSort();
class ArrayIns{
private long[] theArray;
private int nElems;
private ArrayIns(int max){
theArray = new long[max];
nElems = 0;
}
public void insert(long value){
theArray[nElems] = value;
nElems++;
}
public void quickSort(){
recQuickSort(0,nElems-1);
}
private void recQuickSort(int left,int right){
int size = right - left + 1;
if(size <= 3) {
manualSort(left,right);
} else {
long median = median0f3(left,right);
int partition = partitionIt(left,right,median);
recQuickSort(left,partition - 1);
recQuickSort(partition + 1,right);
}
}
private long medianOf3(int left,int right){
int center = (left + right) / 2;
if(theArray[left] > theArray[center]) swap(left,center);
if(theArray[left] > theArray[right]) swap(left,right);
if(theArray[center] > theArray[right]) swap(center,right);
swap(center,right - 1); // put pivot on right
return theArray[right -1];
}
private int partitionIt(int left,int right,long pivot){
int leftPtr = left; //right of first elem
int rightPtr = right -1; //left of pivot
while(true){
while(theArray[++leftPtr] < pivot);
while(theArray[--rightPtr] > pivot);
if(leftPtr >= rightPtr ){
break;
} else {
swap(leftPtr,rightPtr);
}
}
swap(leftPtr,right-1);
return leftPtr;
}
private void manualSort(int left,int right){
int size = right - left + 1;
if(size <= 1) return;
if(size == 2) {
if(theArray[left] > theArray[right]) swap(left,right);return;
} else { //size is 3
if(theArray[left] > theArray[right -1]) swap(left,right-1);
if(theArray[left] > theArray[right]) swap(left,right);
if(theArray[right-1]> theArray[right]) swap(right-1,right);
}
}
}
也可以選擇协屡，對數組整個使用快速排序，不去考慮小于界限的劃分的排序全谤。當快速排序結束時肤晓，數組已經是基本有序了，然后對整個數組應用插入排序认然，也是非巢购叮快，很多專家推薦這種方法卷员。
如盈匾，把界限設為10，那么快速排序到10就結束毕骡，每一塊10個數據里都是無序的削饵，但每一塊之間都有序了岩瘦。再插入排序。
還有一個提升窿撬，消除遞歸启昧。但這是以前計算機性能不好時好用，現在的提升已經不明顯了劈伴。
