選擇排序
選擇排序（Selection sort）是一種簡單直觀的排序算法丢氢。它的工作原理如下。首先在未排序序列中找到最邢雀摹（大）元素疚察，存放到排序序列的起始位置，然后仇奶，再從剩余未排序元素中繼續(xù)尋找最忻驳铡（大）元素，然后放到已排序序列的末尾该溯。以此類推岛抄，直到所有元素均排序完畢。
選擇排序的主要優(yōu)點與數(shù)據(jù)移動有關(guān)狈茉。如果某個元素位于正確的最終位置上夫椭，則它不會被移動。選擇排序每次交換一對元素论皆，它們當(dāng)中至少有一個將被移到其最終位置上益楼，因此對n個元素的表進(jìn)行排序總共進(jìn)行至多n-1次交換。在所有的完全依靠交換去移動元素的排序方法中点晴，選擇排序?qū)儆诜浅：玫囊环N。
- 最壞時間復(fù)雜度 О(n2)
- 最優(yōu)時間復(fù)雜度 О(n2)
- 平均時間復(fù)雜度 О(n2)
- 空間復(fù)雜度 О(n) total, O(1) auxiliary
Java實現(xiàn):
package cc;
public class Select {
public static void selectSort(int[] a)
{
int N = a.length;
for(int i=0;i<N;i++)
{
/* 從A[i]到A[N–1]中找最小元悯周，并將其位置賦給MinPosition */
int min = i;
for(int j=i+1;j<N;j++)
{
if(a[j]<a[min])
min=j;
}
/* 將未排序部分的最小元換到有序部分的最后位置 */
int t = a[i];
a[i] = a[min];
a[min] = t;
}
}
}
想要進(jìn)一步改進(jìn)選擇排序粒督，就在于
如何快速找到最小元？禽翼？屠橄？
如果讀者已經(jīng)對于堆較為熟悉的話，很容易就想到這里可以利用堆實現(xiàn)闰挡。
這就是堆排序的由來
堆排序
堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法锐墙。堆積是一個近似完全二叉樹的結(jié)構(gòu)，并同時滿足堆積的性質(zhì)：即子結(jié)點的鍵值或索引總是小于（或者大于）它的父節(jié)點长酗。
堆節(jié)點的訪問
通常堆是通過一維數(shù)組來實現(xiàn)的溪北。在數(shù)組起始位置為0的情形中：
- 父節(jié)點i的左子節(jié)點在位置(2*i+1);
- 父節(jié)點i的右子節(jié)點在位置(2*i+2);
- 子節(jié)點i的父節(jié)點在位置floor((i-1)/2);
堆的操作
在堆的數(shù)據(jù)結(jié)構(gòu)中，堆中的最大值總是位于根節(jié)點(在優(yōu)先隊列中使用堆的話堆中的最小值位于根節(jié)點)。堆中定義以下幾種操作：
- 最大堆調(diào)整（Max_Heapify）：將堆的末端子節(jié)點作調(diào)整之拨，使得子節(jié)點永遠(yuǎn)小于父節(jié)點
- 創(chuàng)建最大堆（Build_Max_Heap）：將堆所有數(shù)據(jù)重新排序
- 堆排序（HeapSort）：移除位在第一個數(shù)據(jù)的根節(jié)點茉继，并做最大堆調(diào)整的遞歸運算
按照選擇排序的思想，我們先實現(xiàn)一個簡單的堆排序
void Heap_Sort ( ElementType A[], int N )
{ BuildHeap(A); /* O(N) */
for ( i=0; i<N; i++ )
TmpA[i] = DeleteMin(A); /* O(logN) */
for ( i=0; i<N; i++ ) /* O(N) */
A[i] = TmpA[i];
}
T ( N ) = O ( N log N )
缺點在于：
需要額外O(N)空間蚀乔，并且復(fù)制元素需要時間烁竭。
原地堆排序
基于以上堆相關(guān)的操作，我們可以很容易的定義堆排序吉挣。例如派撕，假設(shè)我們已經(jīng)讀入一系列數(shù)據(jù)并創(chuàng)建了一個堆，一個最直觀的算法就是反復(fù)的調(diào)用del_max()
函數(shù)睬魂，因為該函數(shù)總是能夠返回堆中最大的值腥刹，然后把它從堆中刪除，從而對這一系列返回值的輸出就得到了該序列的降序排列汉买。
真正的原地堆排序使用了另外一個小技巧衔峰。堆排序的過程是：
- 創(chuàng)建一個堆H[0..n-1]
- 把堆首（最大值）和堆尾互換
- 把堆的尺寸縮小1，并調(diào)用shift_down(0),目的是把新的數(shù)組頂端數(shù)據(jù)調(diào)整到相應(yīng)位置
- 重復(fù)步驟2蛙粘，直到堆的尺寸為1
偽碼
void Heap_Sort ( ElementType A[], int N )
{ for ( i=N/2-1; i>=0; i-- )/* BuildHeap */
PercDown( A, i, N );
for ( i=N-1; i>0; i-- ) {
Swap( &A[0], &A[i] ); /* DeleteMax */
PercDown( A, 0, i );
}
}
- 最壞時間復(fù)雜度
- 最優(yōu)時間復(fù)雜度
- 平均時間復(fù)雜度
-
堆排序的動態(tài)圖
Sorting_heapsort_anim.gif
Java實現(xiàn)
package cc;
public class HeapSort {
private static int leftChild(int i) {
return 2*i+1;
}
private static void percDown(int[] a, int i, int n) {
int child;
int temp;
for(temp = a[i]; leftChild(i) < n;i = child) {
child = leftChild(i);
if(child != n-1 && a[child] < a[child+1])
child++;
if(temp < a[child])
a[i] = a[child];
else
break;
}
a[i] = temp;
}
public static void heapsort(int[] a) {
for(int i=a.length/2-1;i>=0;i--) {
percDown(a, i, a.length);
}
for(int i=a.length-1;i>0;i--) {
swap(a, 0, i);
percDown(a, 0, i);
}
}
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
