排序算法之选择类排序算法

看完了选择类排序算法，收获颇丰，记得了用数组保存二叉树的计算方法，要不是这次复习，还真给忘了。

好了，不多废话，先看代码，代码中我加上去注释比较多，为了便于记忆和理解：

/*
 * Copyright (c) 2010-~ zhouyongfei
 *
 * The source code is released for free distribution under the terms of the GNU General Public License
 *
 *
 * Author: alen Chou
 * Created Time: 2010年07月21日 星期三 09时47分46秒
 * File Name: sort3.c
 * Description: 这个文章是选择类排序的几个算法的简单实现
 * 选择类排序主要有简单选择排序，树形选择排序，堆排序
 */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define TRUE 1
#define FALSE 0

/**
 * 简单选择排序
 * @:r[]需要排序的记录数组
 * @:length，数组的元素的个数
 *
 * */
void SelectSort(int r[],int length)
{
    int i,j,k,x;
    int n = length;
    for(i = 0;i < n; i++){
        k = i;
        for(j = i+1;j < n; j++){
            if(r[j] < r[k])
                k = j;
        }
        if(k != i){
            x = r[i];
            r[i] = r[k];
            r[k] = x;
        }
    }
}

/**
 * 调整为堆
 * */
void sift(int r[],int k,int m)
{
    int t,x,i,j,flag;
    x = r[k-1];//这里我使用数组的时候很多地方都有减1操作，是为了保证数组下标和数组序号的对应。

    //之前这块老出问题，无奈参考教材，已经写了大半，所以想到了这个办法解决。不推荐使用

    i = k;
    j = 2*i;
    int finished = FALSE;
    
    while(j <= m&& !finished){
        flag = j;
        if(j < m&&r[j-1] < r[j+1-1]){
            j = j + 1; //在左右子树中选择较大值

        }
        if(x >= r[j-1])
            finished = TRUE;//如果已经存在比待调整记录小的，那就说明当前调整结束

        else{
            r[i-1] = r[j-1];
            i = j;
            j = 2*flag; //继续调整，在它的子树中寻找

        }
    }
    r[i-1] = x;
}
/**
 * 初建一个堆
 * */
void create_heap(int r[],int length)
{
    int i;
    int n = length;
    for(i = n/2;i >= 1;--i){ //初建堆的时候从中间元素开始，即n/2位置处开始，n为节点数目。

                            //逐层向上倒退，直到根结点

        sift(r,i,n);
    }

}

/**
 * 使用堆排序
 * */
void HeapSort(int r[],int length)
{
    int n,i,b;
    create_heap(r,length);
    n = length;
    for(i = n;i >= 2; --i){//每次取了堆顶元素后将剩余的再进行调整堆

        b = r[0];
        r[0] = r[i-1];
        r[i-1] = b;
        sift(r,1,i-1);
    }
}

int main(int argc, char *argv[])
{
    int i;
    int arr[] = {48,62,35,77,55,14,35,98};
    int length = sizeof(arr)/sizeof(arr[0]);

    printf("before sort\n");
    for(i = 0;i < length;i++){
        printf("%d ",arr[i]);
    }
    printf("\n");
    
    //SelectSort(arr,length);

    HeapSort(arr,length);

    printf("after sort\n");
    for(i = 0;i < length;i++){
        printf("%d ",arr[i]);
    }
    printf("\n");

    return 0;
}

这里我只是实现了简单选择排序和堆排序，树形排序的代码比较麻烦，下次我实现了以后再贴上代码。

首先来看简单选择排序：

比如从小到大排序来说，先将最小的数找到放在第一个位置，然后找到次小的数，放在第二个位置，一次类推，

就排好了序，这个算法比较简单，就没加多少注释，如果是要从大到小排序，操作刚好和刚才描述的相反。

说道选择排序算法，我想到了一个著名的问题，程序员翻饼问题，这个我会在后面的某篇文章讨论。

然后，堆排序：

堆排序是基于选择排序和树排序算法的改进算法，它弥补了树形排序占用空间多的缺陷。

堆排序之前有几个重要的步骤：调整堆和初建堆。

调整堆：就是将处理后的一个树调整成为被称之为大顶堆或者小顶堆的一个算法。（如果要从小到大排序，会

需要大顶堆算法比较多，如果是从大到小排序，会需要小顶堆比较多），我这里简单描述一下小顶堆调整算法，比如

从一个二叉树中提取了堆顶元素，然后就要重建堆，就会用到调整堆算法（从剩余元素的第一个开始调整），

步骤如下，首先以这个待调整元素为根，使用其子树中较小的和其比较，如果调整元素大，那就将子树中较小的放到

调整元素的位置，继续看刚才较小元素的左右子树，找到较小者和调整元素比较，方法和之前相同。直到找到

比待调整元素小的或者比较完了所有的元素后停止，将待调整元素置于上次较小者的位置。

大顶堆每次比较刚好和小顶堆比较的方向想相反，其余没有差别。

初建堆：

首先将无序的数组依次填放到二叉树中，必须数组arr ，arr[0]为整个二叉树的根，然后arr[1],arr[2]分别为arr[0]的左右子树。然后arr[3]arr[4]分别为arr[1]的左右子树 arr[5]arr[6]为arr[2]的左右子树，知道数组元素分配完。其实这个只是概念上的，arr数组已经是这样的顺序，所以我们知道谁是谁的子树就行。这里就用到

了前面学数组的时候用到的满二叉树a[i]的左右子树为a[2*i]和a[2*i+1]。

然后，就是调整堆，将这个二叉树调整堆，一般情况下从n/2位置处开始调整，因为这样已经可以保证整个数组

都在调整的范围之内，然后其他需要注意的都在代码中详细注释了。

好了，今天就写这些了，可能文字描述远没有图示来的直接，我也只是为了锻炼自己的文字描述能力，这里就

委屈大家了，如果还不清楚我描述的可以上网查看其他资料，或者借本书仔细阅读，相信大家都能够理解算法中的每一句的原委的。。