选择排序

选择排序（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 );
}
}

复制

最坏时间复杂度

O(n\log n)

最优时间复杂度

O(n\log n)

[1]

平均时间复杂度

\Theta (n\log n)

堆排序的动态图

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];elsebreak;}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;}
}