详解排序算法--堆排序
选择排序
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。
![Uploading Selection_sort_animation_154868.gif . . .]
Selection_sort_animation.gif
- 最坏时间复杂度 О(n²)
- 最优时间复杂度 О(n²)
- 平均时间复杂度 О(n²)
- 空间复杂度 О(n) total, O(1) auxiliary
Java实现:
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;
}
}
}
想要进一步改进选择排序，就在于
如何快速找到最小元？？？
如果读者已经对于堆较为熟悉的话，很容易就想到这里可以利用堆实现。
这就是堆排序的由来
堆排序
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
堆节点的访问
通常堆是通过一维数组来实现的。在数组起始位置为0的情形中：
- 父节点i的左子节点在位置(2*i+1);
- 父节点i的右子节点在位置(2*i+2);
- 子节点i的父节点在位置floor((i-1)/2);
堆的操作
在堆的数据结构中，堆中的最大值总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点)。堆中定义以下几种操作：
- 最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
- 创建最大堆（Build_Max_Heap）：将堆所有数据重新排序
- 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
按照选择排序的思想，我们先实现一个简单的堆排序
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)空间，并且复制元素需要时间。
原地堆排序
基于以上堆相关的操作，我们可以很容易的定义堆排序。例如，假设我们已经读入一系列数据并创建了一个堆，一个最直观的算法就是反复的调用del_max()
函数，因为该函数总是能够返回堆中最大的值，然后把它从堆中删除，从而对这一系列返回值的输出就得到了该序列的降序排列。
真正的原地堆排序使用了另外一个小技巧。堆排序的过程是：
- 创建一个堆H[0..n-1]
- 把堆首（最大值）和堆尾互换
- 把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置
- 重复步骤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 );
}
}
- 最坏时间复杂度
Sorting_heapsort_anim.gif
Java实现
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;
}
}
