TimothyQiu's Blog

keep it simple stupid

常用排序算法

2 Comments

选择排序 Selection sort

每次从尚未排好的数组范围里选出一个最小的放到正确的位置。

C 语言版本:

void selection_sort(int array[], int size)
{
    int lhs, rhs;
    int min;

    for (lhs = 0; lhs < size - 1; lhs++) {
        min = lhs;
        for (rhs = lhs + 1; rhs < size; rhs++) {
            if (array[rhs] < array[min])
                min = rhs;
        }
        swap(array, lhs, min);
    }
}

C++ 版本:

template <typename Iter, typename Compare>
void selectionSort(Iter begin, Iter end, Compare compare)
{
    for (auto iter = begin; iter != end; ++iter) {
        std::iter_swap(iter, std::min_element(iter, end, compare));
    }
}

快速排序 Quicksort

从数组里选出一个基准元素,通过交换位置让它前面的元素都比它小、后面的元素都比它大,最后分而治之。

C 语言版本:

void quicksort(int array[], int left, int right)
{
    if (left < right) {
        int pivit = right; // lazy :(
        int store = left;
        int i;

        for (i = left; i < right; i++) {
            if (array[i] < array[pivit]) {
                swap(array, i, store);
                store++;
            }
        }
        swap(array, store, pivit);

        quicksort(array, left, store - 1);
        quicksort(array, store + 1, right);
    }
}

C++ 版本:

template <typename Iter, typename Compare>
void quickSort(Iter begin, Iter end, Compare compare)
{
    auto distance = std::distance(begin, end);
    if (distance > 1) {
        auto const pivot = std::next(begin, distance / 2);
        std::nth_element(begin, pivot, end, compare);
        quickSort(begin, pivot, compare);
        quickSort(pivot, end, compare);
    }
}

插入排序 Insertion sort

每次从尚未排好的数组范围取出一个元素,放到已排好的数组范围中的正确位置。(现实生活中排序时一般用的就是类似这种算法)

C 语言版本:

void insertion_sort(int array[], int size)
{
    int lhs, rhs;
    int cur;

    for (rhs = 1; rhs < size; rhs++) {
        cur = array[rhs];
        for (lhs = rhs - 1; (lhs > 0) && (array[lhs] > cur); lhs--)
            array[lhs + 1] = array[lhs];
        array[lhs] = cur;
    }
}

C++ 版本:

template <typename Iter, typename Compare>
void insertionSort(Iter begin, Iter end, Compare compare)
{
    for (auto iter = begin; iter != end; ++iter) {
        std::rotate(std::upper_bound(begin, iter, *iter, compare),
                    iter,
                    std::next(iter));
    }
}

堆排序 Heapsort

保持未排数组为堆积树,每次摘取根结点,即可取出当前未排范围中的最大/最小值放入正确位置。

C 语言版本:

void sift_down(int heap[], int root, int end)
{
    int l_child = root * 2 + 1;
    int r_child = root * 2 + 2;
    int max = root; // max heap

    if (l_child <= end && heap[l_child] > heap[max])
        max = l_child;

    if (r_child <= end && heap[r_child] > heap[max])
        max = r_child;

    if (max != root) {
        swap(heap, max, root);
        sift_down(heap, max, end);
    }
}

void heapsort(int array[], int size)
{
    int i;

    // from last parent node
    for (i = (size - 2) / 2; i >= 0; i--)
        sift_down(array, i, size - 1);

    for (i = size - 1; i > 0; i--) {
        swap(array, 0, i);
        sift_down(array, 0, i - 1);
    }
}

C++ 版本:

template <typename Iter, typename Compare>
void heapSort(Iter begin, Iter end, Compare compare)
{
    std::make_heap(begin, end, compare);
    std::sort_heap(begin, end, compare);
}

嗯,基本上常用的就是这些啦~

什么,没有冒泡排序?好吧,我至今都想不明白像冒泡排序这样写起来没有选择排序方便、想起来没有插入排序方便的排序算法是怎么成为教科书中的天字第一号排序算法的。嗯……连奥巴马都知道不能用冒泡排东西。

最后,别忘了还有睡眠排序这样神奇的存在 :)

p.s. 代码里的交换两个元素的值,美观起见就直接写 swap 啦,具体实现随便挑 :)

AT&T 和 Intel 汇编语法的主要区别

No Comments

作为一个爱折腾的大好青年,补番之余还要补一些 Linux 下的基础,比如 GDB 的正确使用方法。但无论是看 gdb 还是 gcc -S 里的汇编,感觉都不能一下子接受这种设定。

后来发现,虽然同为 x86 汇编,但语法也分两大流派:之前上学时学的 Intel 语法,以及流行于 Unix/Linux 平台上的 AT&T 语法。

首先,两者最让人纠结的区别就是源操作数、目标操作数的顺序。AT&T 语法先写源操作数,再写目标操作数;Intel 语法先写目标操作数,再写源操作数:

AT&T
movl %esp, %ebp
Intel
MOV EBP, ESP
然后,另一个明显的区别就是指令的命名(或者说,操作数大小的指定方式)。AT&T 语法将操作数的大小表示在指令的后缀中(b、w、l);Intel 语法将操作数的大小表示在操作数的前缀中(BYTE PTR、WORD PTR、DWORD PTR):

AT&T
decw (%eax)
Intel
DEC WORD PTR [EBX]
再者,各种取址方式的表示。AT&T 语法总体上是offset(base, index, width)的格式;Intel 语法总体上是[INDEX * WIDTH + BASE + OFFSET]的格式:

AT&T
movl           0x0100, %eax
movl           (%esi), %eax
movl         -8(%ebp), %eax
movl  0x0100(,%ebx,4), %eax
movl 0x8(%edx,%ebx,4), %eax
Intel
MOV EAX, [0100]
MOV EAX, [ESI]
MOV EAX, [EBP-8]
MOV EAX, [EBX*4+0100]
MOV EAX, [EDX+EBX*4+8]

另外,各种非十进制数制下数字的表示方法。AT&T 语法用前缀表示数制(0x、0、0b);Intel 语法用后缀表示数制(h、o、b):

AT&T
movl 0x8   , %eax
movl 010   , %eax
movl 0b1000, %eax
Intel
MOV EAX,    8h
MOV EAX,   10o
MOV EAX, 1000b
最后就是零碎的东西的表示方法了。AT&T 语法要在常数前加 $、在寄存器名前加 % 符号;Intel 语法没有相应的东西要加:

AT&T
subl $0x30, %eax
Intel
SUB EAX, 30
于是,以上就是 AT&T 和 Intel 汇编语法的主要区别了……吧?

关于 WordPress 的标签

No Comments

今天心血来潮把原来的标签「C/C++」拆成了「C」和「C++」两个,虽说没有了那个很碍眼的斜杠顿时清爽不少,但出现了一个小问题:这两个标签似乎没法并存。

虽然在标签列表里可以显示为两个标签,添加时也可以分别选择添加,但一旦保存,就会又变成只有「C」标签存在。

一番 Google 后,得知如果 Slug 相同会被判为同一个标签,但我的「C++」标签的 Slug 是「cpp」,应该没有这个问题。绕来绕去,失败了 N 多次后,发现在添加标签的地方输入「cpp」保存后就能正确添加「C++」标签。

也就是说让你输入标签的地方实际上要你输入优先判定的是标签的 Slug 而不是 Name?!这是什么坑爹的设定啊?(好吧~WordPress 里标签的 Name 是可以重复的,Slug 不允许重复……)

MinGW 下编译 freeglut

No Comments

于是国庆一时兴起决定折腾下 OpenGL 玩玩。

本自然段纯吐槽,欢迎略过:学习 OpenGL 的一大幸事是有诸如 NeHe 这样的大神级教程可以参考,可惜开篇光讲怎么在 Win32 下创建空窗口就讲了洋洋洒洒 14 屏。Win32 API 创建窗口不是问题,问题是一来光空窗口就要这么长的篇幅我实在看不下去,二来他木有讲 Linux 版本的(不过示例代码有 Linux 版本下载)。要说创建窗口什么的简洁和跨平台方便还是 GLUT,而且碰巧 Google 到了 GLUTによる「手抜き」OpenGL入門 这篇,不愧是大学的讲义(?),质量非常不错。GLUT 本身貌似决定停留在这个世纪初了,于是改用 freeglut。Arch 下安装 freeglut 直接 pacman -S freeglut 即可,Windows 下就只得自己下载源码编译了。

阅读剩余部分...

Google Talk Bot in Python

No Comments

上班或者出门在外的时候有没有想过用家里闲着的电脑干点什么事呢?嘛~一切的可能性都得建立在你能连接得到自己的电脑之上才行。家里的电脑不比服务器,IP 并不固定,怎么办呢?解决方法挺多,比如花生壳,比如用 corn 发定时邮件……

对于我来说,写个会告诉你自己 IP 的 GTalk 机器人,想 SSH 连回家之前问一下是最方便的了。Lua 的 XMPP 库完全不懂怎么用,那么就先学现卖用 Python 写咯~

阅读剩余部分...