各种排序是常见的面试题， 我希望能够帮助大家轻松的秒杀那些小菜鸟

这个排序我原本不打算介绍的， 因为时间有限， 只能挑个简单的介绍了。
有个普遍的错误的观点，认为选择排序的 时间复杂度 总是为 0(n^2),  我告诉你， 还就不是的

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

#define MAX_NUM 15

#define less(A, B) ((A) < (B))
#define exch(A, B) {char t = A; A = B; B = t;}

void selectionSort(char a[], int left, int right);

int main(void)
{
    char a[MAX_NUM+1] = "ASORTINGEXAMPLE";
    int i;

    selectionSort(a, 0, MAX_NUM-1);
 
    for (i = 0; i < MAX_NUM; i++)
    {
        printf("%c ", a[i]);
    }

    getchar();

    return 0;
}

void selectionSort(char a[], int left, int right)
{
    int i, j, min;

    for (i = left; i < right; i++)
    {
        min = i;

        for (j = i+1; j <= right; j++)
        {
            if (less(a[j], a[min]))
            {
                min = j;
            }
        }
        exch(a[i], a[min]);
    }
}

由排序过程可得， 选择排序 交换次数 与 n 成比例, 比较次数与 n^2成比例，
所以， 选择排序的 时间复杂度由 比较次数决定。

选择排序之所以慢，是因为他的运行时间与文件的已排序量基本没有关系，文件是 已有序的 或是 随机的，使用选择排序
排序， 所花时间基本一样。

需要注意的是，比较或是交换的关键字不一定是 单一数值，可能是字符串， 可能结构体...
对于大项、小键的文件， 选择排序恰恰是最好的选择，其运行时间 为线性的，没想到吧 ！


[ 本帖最后由 BlueGuy 于 2011-1-9 21:29 编辑 ]

收到的鲜花

• Devil_W 于 2011-01-09 17:56 送鲜花  -3朵   附言：有意思吗 ？？
• 以中 于 2011-02-25 11:31 送鲜花  1朵   附言：纵不日进，或可免于退乎！
• 观弈寒儒 于 2011-02-25 14:47 送鲜花  -2朵   附言：搞笑了
• 观弈寒儒 于 2011-02-25 14:48 送鲜花  -2朵   附言：误人子弟！
• 观弈寒儒 于 2011-02-25 14:49 送鲜花  -2朵   附言：我从来不批别人的主题贴，你是例外！

学习。再学习.

请问二叉树非递归建立么搞？

什么样的二叉树？前序？ 中序？ 还是后序。/
等我介绍查找的时候，顺带说下二叉树吧~~

[ 本帖最后由 BlueGuy 于 2011-1-9 17:32 编辑 ]

学习了。

最痛恨那些看帖不回帖的， 还扣我分的，
是不是我 赞美了 选择排序，冲击了你们由始以来的腐朽的观点，觉的很不爽~~

[ 本帖最后由 BlueGuy 于 2011-1-9 18:29 编辑 ]

腐朽的观点指的是什么？那种被认为是最简单的排序法？
我比较熟悉的是冒泡排序法！

腐朽的观点 是说的玩的，回击 devil_w的， 本来人缘就不好，分不多，他竟然无情的扣我的分...

冒泡排序 并不是最简单的，选择排序才是最简单的，形式单一，没有优化的余地




[ 本帖最后由 BlueGuy 于 2011-1-9 21:14 编辑 ]

有些人说，"冒泡和选择排序该被踢出教材了"， "快速排序才是最快的最好的排序算法"，其实这些观点都是很片面的。/
我个人觉得每一种排序方法都有他适用的范围，不应该去主观的评价他的优劣，正确的学习态度是：
你应该知道这个排序为什么慢，或者是为什么快，什么情况下慢 或者 什么情况下快。只有对算法的特性有着清析的认识
才能指导我们开发高效的程序。

这些都是 套话了


[ 本帖最后由 BlueGuy 于 2011-1-9 22:50 编辑 ]

收到的鲜花

• Devil_W 于 2011-01-10 00:15 送鲜花  -3朵   附言：见过2的，没见过你这么2的。
• hust_sj 于 2011-01-12 13:19 送鲜花  5朵   附言：这句话说的很中肯，本人表示非常赞同！不像 ...

BG版主，有一点你说错了，选择排序的复杂度其实和冒泡排序是一样的。
你只是通过min = i;给它一个少交换的条件。
比较的次数还是没变，和冒泡排序的次数是一样的。
选择排序的 时间复杂度 一样是 0(n^2)。

[ 本帖最后由 观弈寒儒 于 2011-1-12 01:23 编辑 ]