排序算法总结（一）冒泡排序和选择排序

访问www.tomcoding.com网站，学习Oracle内部数据结构，详细文档说明，下载Oracle的exp/imp，DUL，logminer，ASM工具的源代码，学习高技术含量的内容。

冒泡排序

这个算法可以说是排序算法中最著名的一个了，名字独特，也好理解，在一个数组中有n个元素，扫描整个数组中没有排序的元素，从第一个元素开始，每个元素与它后面的元素比较，数值小的放在前面，数值大的放在后面，那么经过第一轮扫描，最大的数值就放在了数组最后的位置，就像每个元素是一个气泡，最大的气泡最先浮到数组顶端。第二轮扫描，由于最大的元素已经找到，需要找第二大的元素，这时扫描的元素个数少了一个，变为n-1，经过第二轮扫描，第二大的元素放到了数组倒数第二的位置。依次类推，第三次扫描元素个数变为n-2，第三大的元素排到了倒数第三的位置。这样每次扫描的元素越来越少，最后扫描到未排序的元素只有一个时，排序就结束了，这时数组中的数值按照升序排列好了。

第0轮：扫描n-1个元素，从0开始到n-2，每个元素j与后一个元素j+1比较，小的在前，大的在后，如果不一致时，要把这两个元素交换位置。

第1轮：扫描n-2个元素，从0开始到n-3，每个元素j与后一个元素j+1比较。

第2轮：扫描n-3个元素，从0开始到n-4，每个元素j与后一个元素j+1比较。

第3轮：扫描n-4个元素，从0开始到n-5，每个元素j与后一个元素j+1比较。

……

第n-2轮：扫描1个元素，第0个和第1个元素比较。

第n-1轮：扫描0个元素，结束。其实在上一轮比较完，就可以结束了。

用C语言编写一个函数实现冒泡排序算法，i表示扫描的轮的序号，j表示每一轮中扫描的元素序号（数组下标）。

/* ai是要排序的整数数组指针

 *  n是数组中元素的个数

 */

void bubble_sort(int *ai, int n)

{

    int         i, j, k;

    /* 循环n-1轮 */

    for (i = 0; i < (n-1); i++) {

        /* 每一轮，扫描n-1-i个元素 */

        for (j = 0; j < (n-1-i); j++) {

            if (ai[j] > ai[j+1]) {

                /* 前一个元素比后一个大，交换位置，否则不用交换 */

                k       = ai[j];

                ai[j]   = ai[j+1];

                ai[j+1] = k;

            }

        }

    }

}

选择排序

这个也是经常用到的排序算法，甚至是最容易想到的算法，虽然不好确定它的名字。工作原理如下，把要排序的数组分成两部分，第一部分是排过序的元素集合，第二部分是没有排过序的元素集合，开始时第一部分的元素个数为0，第二部分为全部元素，算法要进行多轮选择，每一轮选择都是从第二部分元素中找到最小的元素，把这个元素放到第一部分的末尾，这样经过多轮选择后，第一部分越来越大，第二部分越来越小，当第二部分元素数为0时，排序就结束了。

实现算法时也有两个关键点要确定，第一个是循环的轮数，假设数组中元素的个数是n，每一轮要找到一个最小数据，所以原则上应该找n轮，其实找到n-1轮时，最后一轮就剩下一个元素了，没有比较的必要了，所以循环的轮数为n-1。第二个是每轮查找元素的个数，看下表。

第0轮，扫描n-0个元素，从0到n-1

第1轮，扫描n-1个元素，从1到n-1

第2轮，扫描n-2个元素，从2到n-1

第3轮，扫描n-3个元素，从3到n-1

……

第n-2轮，扫描2个元素，从n-2到n-1

第n-1轮，扫描1个元素，从n-1到n-1

用C语言写一个函数实现这个算法。

/* ai 是要排序的整数数组

 *  n 是数组中元素的个数

 *

 * 函数中i，j是计数变量

 * min_index是第二部分数组中最小值的元素下标

 * min变量暂存第二部分中最小值

 * tail是第一部分的尾部位置

 * start是第二部分开始扫描的起始位置

 */

static void selection_sort(int *ai, int n)

{

    int         i, j, k, min_index;

    int         min;

    int         tail;

    int         start;

    /* 开始时，第一部分没有元素，尾部在第0个元素 */

    tail = 0;

    for (i = 0; i < (n-1); i++) {

        start = tail;

        min   = ai[start];

        min_index = -1;

        for (j = start; j < n; j++) {

            if (ai[j] < min) {

                min_index = j;

                min = ai[j];

            }

        }

        if (min_index != -1) {

            /* 找到了最小值，交换元素 */

            k             = ai[tail];

            ai[tail]      = ai[min_index];

            ai[min_index] = k;

        }

        tail++;

    }

}

这个函数看起来有些复杂，我们来简化一下。从上面看tail其实就是i的位置，start是i的下一个位置，min值是扫描第二部分的第一个元素，把这些简化后，得到下面的函数。

void selection_sort(int *ai, int n)

{

    int         i, j, k;

    int         min_index;

    for (i = 0; i < (n-1); i++) {

        min_index = i;

        for (j = i+1; j < n; j++) {

            if (ai[j] < ai[min_index])

                min_index = j;

        }

        if (min_index != i) {

            /* 交换元素 */

            k             = ai[i];

            ai[i]         = ai[min_index];

            ai[min_index] = k;

        }

    }

}

检查排序结果

写一个函数来检查一下排序后的元素顺序有没有错误，方法很简单，在数组中遍历一次，看看前一个元素是否比后一个元素大，如果大就说明排序出错了。

void check_result(int *ai, int n)

{

    int         i;

    for (i=0; i<n-1; i++) {

        if (ai[i] > ai[i+1]) {

            fprintf(stderr, "error, element[%d]=%d, element[%d]=%d\n\n", i, ai[i], i+1, ai[i+1]);

            return;

        }

    }

    fprintf(stdout, "element is sorted.\n\n");

}

写一个程序测试一下排序结果。

int main(int argc, char *argv[])

{

    static int  chaos[16] = {23, 6, 235, 89, 4, 12, 76, 35, 129, 30, 77, 15, 61, 44, 49, 88};

    int         array[16];

    fprintf(stdout, "test for bubble_sort function.\n\n");

    memcpy(array, chaos, 16*sizeof(int));

    bubble_sort(array, 16);

    check_result(array, 16);

    fprintf(stdout, "test for selection_sort function.\n\n");

    memcpy(array, chaos, 16*sizeof(int));

    selection_sort(array, 16);

    check_result(array, 16);

    return (0);

}