一个很好的参考卡/备忘单与C中的基本排序算法?

我一直在寻找(没有好运)完美的参考卡与C中的所有基本排序算法(或者可能在伪代码中)。 维基百科是一个非常好的信息来源,但这一次我正在寻找一些更便携的东西(如果可能的话口袋大小),当然也可以打印。 任何建议将不胜感激!

我为我的一个朋友学习C做了这个,也许你会觉得它很有帮助:

#include  #include  static void swap(int *a, int *b) { if (a != b) { int c = *a; *a = *b; *b = c; } } void bubblesort(int *a, int l) { int i, j; for (i = l - 2; i >= 0; i--) for (j = i; j < l - 1 && a[j] > a[j + 1]; j++) swap(a + j, a + j + 1); } void selectionsort(int *a, int l) { int i, j, k; for (i = 0; i < l; i++) { for (j = (k = i) + 1; j < l; j++) if (a[j] < a[k]) k = j; swap(a + i, a + k); } } static void hsort_helper(int *a, int i, int l) { int j; for (j = 2 * i + 1; j < l; i = j, j = 2 * j + 1) if (a[i] < a[j]) if (j + 1 < l && a[j] < a[j + 1]) swap(a + i, a + ++j); else swap(a + i, a + j); else if (j + 1 < l && a[i] < a[j + 1]) swap(a + i, a + ++j); else break; } void heapsort(int *a, int l) { int i; for (i = (l - 2) / 2; i >= 0; i--) hsort_helper(a, i, l); while (l-- > 0) { swap(a, a + l); hsort_helper(a, 0, l); } } static void msort_helper(int *a, int *b, int l) { int i, j, k, m; switch (l) { case 1: a[0] = b[0]; case 0: return; } m = l / 2; msort_helper(b, a, m); msort_helper(b + m, a + m, l - m); for (i = 0, j = 0, k = m; i < l; i++) a[i] = b[j < m && !(k < l && b[j] > b[k]) ? j++ : k++]; } void mergesort(int *a, int l) { int *b; if (l < 0) return; b = malloc(l * sizeof(int)); memcpy(b, a, l * sizeof(int)); msort_helper(a, b, l); free(b); } static int pivot(int *a, int l) { int i, j; for (i = j = 1; i < l; i++) if (a[i] <= a[0]) swap(a + i, a + j++); swap(a, a + j - 1); return j; } void quicksort(int *a, int l) { int m; if (l <= 1) return; m = pivot(a, l); quicksort(a, m - 1); quicksort(a + m, l - m); } struct node { int value; struct node *left, *right; }; void btreesort(int *a, int l) { int i; struct node *root = NULL, **ptr; for (i = 0; i < l; i++) { for (ptr = &root; *ptr;) ptr = a[i] < (*ptr)->value ? &(*ptr)->left : &(*ptr)->right; *ptr = malloc(sizeof(struct node)); **ptr = (struct node){.value = a[i]}; } for (i = 0; i < l; i++) { struct node *node; for (ptr = &root; (*ptr)->left; ptr = &(*ptr)->left); a[i] = (*ptr)->value; node = (*ptr)->right; free(*ptr); (*ptr) = node; } } 

你一定要看看Animated Sorting Algorithms页面。 它是一种用于排序算法的惊人资源。

编辑感谢Peterino的新链接!

你需要的是Robert Sedgewick的一本名为Algorithms in C的书。

http://www.amazon.com/Algorithms-C-paperback-Robert-Sedgewick/dp/0768682339/

我可能会找一个用过的。 新的有点贵(但仍然完全值得。)

一般来说,人们不会过多担心不同的算法,很多人使用标准库qsort()函数(可能会或可能不会使用Quicksort)进行排序。 当他们不使用它时,它们通常具有更复杂的要求。 这可能是因为他们需要外部排序(将数据溢出到磁盘),或者出于与性能相关的原因。 偶尔,与使用qsort() (或者实际上是bsearch() )相关的函数调用每次比较的感知开销太大。 有时候,人们不想冒险使用Quicksort潜在的O(N ^ 2)最坏情况行为,但大多数生产qsort()算法都会为你避免这种情况。

除了关于算法的各种书籍之外 – Sedgewick就是其中之一,但还有很多其他的 – 你还可以看看Jon Bentley的“Programming Pearls”或“More Programming Pearls”书籍。 无论如何,这都是好的 – 它们非常出色 – 但是“More Programming Pearls”还包括一个用awk编写的简单算法库,包括插入排序,堆排序和快速排序。 它错过了Bubble Sort,Shell Sort和BogoSort。 它也不包括Radix Sort。