选择排序的基本思想是：每一趟从待排序的数据中选出最小元素，顺序放在已排好序的数据最后，直到全部数据排序完毕。
选择排序包括：简单选择排序，堆排序~！
一、简单选择排序
简单选择排序时一种不稳定的算法，他的时间复杂度是：O(n^2)，空间复杂度就需要一个中间单元A【0】的空间！
来根据图看一下排序的过程！
根据图大家应该能看出来，算法的思想是：
对于这一组数据，如上面的待排序的数据{K1,K2,…,Kn}，首先从数据中寻找最小值，我们假定是Kn , 那么我们要把Kn和K1来交换，就是把最小值移动到最前面，然后从除K1外的剩下的元素去寻找另一个最小值，然后和K2交换，就这样依次类推，直到元素的最后！
OK，来看一下动画演示：选择排序动画演示
void select_sort(int *a, int N) { int temp; for(int i = 0; i < N - 1; i++) { //寻找最小值 temp = i; for(int j = i + 1; j < N; j++) { if(a[temp] > a[j]) { temp = j; } } //找到最小后交换数值 if(temp != i) { swap(a[temp], a[i]); } } }
二、堆排序
堆排序 是一种不稳定算法，他的时间复杂度是：O(nlgn)，堆排序不适合于记录数较少的文件，因为建立初始堆比较的次数较多！ 他的空间复杂度是O(1)！！
堆是近似于完全二叉树的一种数据结构，他的性质是：
子节点的键值或索引总是小于（大于）它的父节点：
我们的堆通常是通过一维数组来实现的！ 可以用树状结构来表示：
也就是：父节点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，下面来看看代码，先来看一个不递归的：
//********************************************************* //堆排序 这里包括三个函数： // 建堆 Build_Heap 调整堆Heap_ify 排序HeapSort //********************************************************* //建立最大堆调整 void Heap_ify(int *a, int i, int size) //size堆的大小 i 要调整的位置 { //left right 分别是i的左右子节点 largest暂存 for(int left = 2 * i, right = 2 * i + 1, largest = i; left < size || right < size;) { 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]); //调整节点 i = largest; left = 2 * i; right = 2 * i + 1; } else { break; } } } void Build_Heap(int *a, int size) { //从最后一个非叶子节点开始 for(int i = size/2 - 1; i >= 0; i--) { Heapify(a, i, size); } } void HeapSort(int *a, int size) { Build_Heap(a, size); //建堆 for(int i = size - 1; i > 0; i--) { swap(a[0], a[i]); //堆得第一个元素与之交换 Heapify(a, 0, i); //调整堆 } }
下面的是对调整的递归版本
//堆调整递归版本 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 于南昌