【啊哈！算法】之四、选择排序

选择排序的基本思想是：每一趟从待排序的数据中选出最小元素，顺序放在已排好序的数据最后，直到全部数据排序完毕。

选择排序包括：简单选择排序，堆排序~！

一、简单选择排序

简单选择排序时一种不稳定的算法，他的时间复杂度是：O(n^2)，空间复杂度就需要一个中间单元A【0】的空间！

来根据图看一下排序的过程！

根据图大家应该能看出来，算法的思想是：

对于这一组数据，如上面的待排序的数据{K_{1,K2,…,Kn}，首先从数据中寻找最小值，我们假定是Kn , 那么我们要把Kn和K1来交换，就是把最小值移动到最前面，然后从除K1外的剩下的元素去寻找另一个最小值，然后和K2交换，就这样依次类推，直到元素的最后！}

OK，来看一下动画演示：选择排序动画演示

我们的堆通常是通过一维数组来实现的！ 可以用树状结构来表示：
也就是：父节点i的左子结点的位置是：（2*i)
父节点i的右子结点的位置是：（2*i+1)
子节点i的父节点的位置是floor（i/2)
ok来看一下：
{1,35,14,60,61,45,15,81}

ok我们下面来看一下堆排序的过程：
给一组数据：{20，12，35，15，10，80，30，17，2，1}（n=10）
初始状态的堆图为：

根据堆得性质可以看书来，上面的堆不是最大堆也不是最小堆！
所以我们要来调整堆！
从后往前查找，自第一个具有孩子的结点开始，根据完全二叉树性质，这个元素在数组中的位置为i=[n/2]，如果以这个结点为根的子树已是最大堆，则此时不需调整，否则必须调整子树使之成为堆。随后，继续检查以i-1、i-2等结点为根的子树，直到检查到整个二叉树的根结点（i=1），并将其调整为堆为止。

调整方法：由于A[i]的左、右子树均已是堆，因此A[2i]和A[2i+1]分别是各自子树中关键字最大的结点。若A[i]不小于A[2i]和A[2i+1]，则A[i]没有违反堆性质，那么以A[i]为根的子树已是堆，无须调整；否则必须将A[i]和A[2i]与A[2i+1]中较大者（不妨设为A[j]）进行交换。交换后又可能使结点A[j]违反堆性质，同样由于该结点的两棵子树仍然是堆，故可重复上述的调整过程，直到当前被调整的结点已满足堆性质，或者该结点已是叶子结点为止。

最终，这组数据经过调整后的最大堆为：{80，17，35，12，10，20，30，15，2，1}！

ok我们再来看一下转换为最小堆，只有最大堆怎么能满足我们呢！
①将建成的最大堆作为初始无序区。
②将堆顶元素（根）A[1]和A[n]交换，由此得到新的无序区A[1..n-1]和有序区A[n]，且满足A[1..n-1]≤A[n]
③将A[1..n-1]调整为堆。
④再次将A[1]和无序区最后一个数据A[n-1]交换，由此得到新的无序区A[1..n-2]和有序区A[n-1..n]，且仍满足关系A[1..n-2]≤A[n-1..n]，同样要将A[1..n-2]调整为堆。直到无序区只有一个元素A[1]为止。
说明：如果需要生成降序序列，则利用最小堆进行操作。

注意：

①堆中任一子树亦是堆。

②以上讨论的堆实际上是二叉堆(Binary Heap)，类似地可定义k叉堆。

OK，大家来看一下动画演示：堆排序动画演示

OK，下面来看看代码，先来看一个不递归的：

//堆调整递归版本void Heapify(int *a, int i, int size){int left = 2 * i;int right = 2 * i + 1;int largest = i;if(left < size && a[largest] < a[left]){largest = left;}if(right < size && a[largest] < a[right]){largest = right;}if(i != largest){swap(a[largest], a[i]);Heapify(a, largest, size);}}

2012/8/8

jofranks 于南昌

1楼woshizhu12321小时前

讲得好