插入排序： O(n^2)，穩定排序
插入排序是在一個已經有序的小序列的基礎上，一次插入一個元素。當然，剛開始這個有序的小序列只有1個元素，就是第一個元素。比較是從有序序列的末尾開始，也就是想要插入的元素和已經有序的最大者開始比起，如果比它大則直接插入在其后面，否則一直往前找直到找到它該插入的位置。如果碰見一個和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后順序沒有改變，從原無序序列出去的順序就是排好序后的順序，所以插入排序是穩定的。
void
insert_sort(int *array, int len)
{
int i, j, backup;
for(i=1; i<=len-1; ++i) {
backup = array[i];
for(j=i-1; j>=0 && array[j]>backup; --j)
array[j+1] = array[j];
array[j+1] = backup;
}
}
void
insert_sort_recursive(int *array, int len)
{
if(len == 1)
return;
insert_sort_recursive(array, len-1);
int j, backup = array[len-1];
for(j=len-2; j>=0 && array[j]>backup; --j)
array[j+1] = array[j];
array[j+1] = backup;
}
選擇排序： O(n^2)，非穩定排序
選擇排序是給每個位置選擇當前元素最小的，比如給第一個位置選擇最小的，在剩余元素里面給第二個元素選擇第二小的，依次類推，直到第n-1個元素，第n個元素不用選擇了，因為只剩下它一個最大的元素了。那么，在一趟選擇，如果當前元素比一個元素小，而該小的元素又出現在一個和當前元素相等的元素后面，那么交換后穩定性就被破壞了。比較拗口，舉個例子，序列5 8 5 2 9， 我們知道第一遍選擇第1個元素5會和2交換，那么原序列中2個5的相對前后順序就被破壞了，所以選擇排序不是一個穩定的排序算法。
void
select_sort(int *array, int len)
{
int i, j, min;
for(i=0; i<len-1; ++i) {
min = i;
for(j=i+1; j<=len-1; ++j)
min = array[min] < array[j] ? min : j;
if(min != i)
swap(array+min, array+i);
}
}
冒泡排序： O(n^2)時間復雜度，穩定排序
冒泡排序就是把小的元素往前調或者把大的元素往后調。比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。所以，如果兩個元素相等，我想你是不會再無聊地把他們倆交換一下的；如果兩個相等的元素沒有相鄰，那么即使通過前面的兩兩交換把兩個相鄰起來，這時候也不會交換，所以相同元素的前后順序并沒有改變，所以冒泡排序是一種穩定排序算法。
void
swap(int *a, int *b) /* precondition: pointer a and b can't be the same */
{
*a = *a + *b;
*b = *a - *b;
*a = *a - *b;
}
void
bubble_sort(int *array, int len)
{
int i, j;
for(i=0; i<len-1; ++i) {
for(j=len-1; j>i; --j) {
if(array[j-1] > array[j])
swap(array+j-1, array+j);
}
}
}
下半年就要正式找工了，淘寶的實習因為爺爺去世提前告一段落。
書籍
編程語言： 《C和指針》，《C專家編程》，《C++ Primer》，《Effective C++》
數據結構與算法： 《算法導論》，《編程珠璣》，《編程之美》
操作系統: 《操作系統》，《深入理解計算機系統》，《Linux內核設計與實現》
計算機網絡: 《TCP/IP詳解 卷一》
編程實踐
常用數據結構，排序，搜索，圖算法，動態規劃，字符串等
參考： PKU已做題目，何海濤的面試100題，IT面試題
題目:
題目：在數組中，數字減去它右邊的數字得到一個數對之差。求所有數對之差的最大值。例如在數組{2, 4, 1, 16, 7, 5, 11, 9}中，數對之差的最大值是11，是16減去5的結果。
對于分治算法，實現的不好，參考原作者的思路，對于左半部分最大值、右半部分最小值都是可以在遞歸里求出的，參考：
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<limits.h>
#define MAX(a, b) ((a)>(b) ? (a) : (b))
#define MIN(a, b) ((a)<(b) ? (a) : (b))
/*
* 題目:
* 在數組中，數字減去它右邊的數字得到一個數對之差。求所有數對之差的最大值
* 例如:
* 在數組{2, 4, 1, 16, 7, 5, 11, 9}中，數對之差的最大值是11，是16減去5的結果
*/
int
naive_solution(int *array, int len) //O(n^2)
{
int i, j, ret = INT_MIN;
for(i=0; i<len; ++i)
for(j=i+1; j<len; ++j)
ret = MAX(ret, array[i]-array[j]);
return ret;
}
int
divide_and_conquer_solution(int *array, int begin, int end) //O(nlogn)
{
if(begin >= end)
return INT_MIN;
int i, ret, left_ret, right_ret, left_max, right_min, mid;
mid = begin + ((end-begin)>>1);
left_ret = divide_and_conquer_solution(array, begin, mid);
right_ret = divide_and_conquer_solution(array, mid+1, end);
left_max = array[begin];
for(i=begin+1; i<=mid; ++i)
left_max = MAX(left_max, array[i]);
right_min = array[end];
for(i=end-1; i>mid; --i)
right_min = MIN(right_min, array[i]);
ret = MAX(left_ret, right_ret);
ret = MAX(ret, left_max-right_min);
return ret;
}
int
dynamic_programming_solution(int *array, int len) //O(n)
{
int i, cur_ret, cur_min;
cur_ret = array[len-2] - array[len-1];
cur_min = MIN(array[len-2], array[len-1]);
for(i=len-3; i>=0; --i) {
cur_ret = MAX(cur_ret, array[i]-cur_min);
cur_min = MIN(cur_min, array[i]);
}
return cur_ret;
}
int
main(int argc, char **argv)
{
int i, num, *data = NULL;
scanf("%d", &num);
assert(num>=2);
data = (int *)malloc(sizeof(int) * num);
assert(data != NULL);
for(i=0; i<num; i++)
scanf("%d", data+i);
printf("naive_solution result: %d\n", naive_solution(data, num));
printf("divide_and_conquer_solution result: %d\n", divide_and_conquer_solution(data, 0, num-1));
printf("dynamic_programming_solution result: %d\n", dynamic_programming_solution(data, num));
free(data);
return 0;
}
摘要: 來源: http://coolshell.cn/articles/4990.html月光博客6月12日發表了《寫給新手程序員的一封信》，翻譯自《An open letter to those who want to start programming》，我的朋友（他在本站的id是Mailper）告訴我，他希望在酷殼上看到一篇更具操作性的文章。因為他也是喜歡編程和技術的家伙，于是，我讓他把...
閱讀全文
問題:
Given a random number generator which can generate the number in range (1,5) uniformly. How can you use it to build a random number generator which can generate the number in range (1,7) uniformly?
(給定一個隨機數生成器，這個生成器能均勻生成1到5(1,5)的隨機數，如何使用這個生成器生成均勻分布的1到7(1,7)的數?)
解法一:
拒絕采樣定理
簡單的說, 把 1-5 的隨機數發生器用兩次, 拼成一個5進制的數, 就是1-25. 將這 1-25 平均分配的25種情況映射到7種情況上, 問題就解決了. 因為21是7的倍數, 我們可以每三個映射到一個, 即1-3 映射到1, …, 19-21 映射到7. 可見, 這些情況之間的概率是一樣的. 那么, 要是拼成的數字正好是 22-25 這四個呢? 有兩種方法, 第一種是丟棄這個數字, 從頭再來, 直到拼成的數字在1-21之間. 因為這個是個概率算法, 不能保證每次都能落在1-21, 所以采樣的密度不高. 還有一種方法, 是說, 假如落到了 22-25, 那這次的采樣結果就用上次的. 可以證明, 這看上去兩個互相矛盾的算法, 結果都能均等的得到等概率的分布. (前者叫做 Reject Sampling, 后者叫做 Metropolis Algorithm, 都是數學物理模擬里面常用的方法)
解法二:
二進制
1-2映射到0，3跳過，4-5映射到1
生成三位的二進制即可
問題來源: 編程珠璣
解法一:
遍歷這n個items，巧妙地利用概率來篩選
void
generate_random_m_from_n(int n, int m)
{
int i, remaining, select = m;
srand(time(NULL));
for(i=0; i<n; i++) {
remaining = n - i;
if(rand()%remaining < select) {
printf("%d\t", i);
--select;
}
}
printf("\n");
}
解法二:
shuffle，即隨機洗牌程序，然后選擇前m個items即可
代碼參考:
http://blog.fuqcool.com/2011/04/17/algorithm-shuffle.html
作者：fuqcool 發布時間：2011-04-17 23:16:02 分類： algorithms
最近自己在做一個小的程序，需要把一個集合里面的元素全部隨機地打散。自己想了一個方法，復雜度是n，覺得不太快。后來參照了一下python關于shuffle的算法，發現我的方法跟它的是一樣的，連python的代碼都這么寫，可能已經沒有辦法再快了吧！
下面就來介紹洗牌算法，用C語言描述。
算法的前提是有一個產生隨機數的函數
// Generates a random integer between beg and end.
int GetRandomNumber(int beg, int end);
還有一個交換函數。
// Swap a and b.
void Swap(int a, int b);
上面兩個函數我就不寫出實現了，因為這篇文章的重點在于算法的討論。
假設我們有一堆撲克牌，怎么才能把這副牌完全打亂呢？計算機當然不能像人手那樣洗牌。但是它可以產生隨機數，隨機地從一副牌中抽出一張牌是可以的。既然這樣那就好辦了，我們不停地從牌堆中隨機抽取一張撲克牌，然后把這些牌堆起來，直到原來的牌堆只剩下一張牌的時候為止。這樣不就完成了洗牌的動作了嗎。
下面是C代碼：
int Shuffle(int[] a, int len)
{
for (int i = len - 1; i > 0; i--)
{
// Select an element from index 0 to i randomly;
int index = GetRandomNumber(0, i);
// exchange a[i] with a[index]
Swap(a[index], a[i]);
}
}
順便也貼出python的random單元關于shuffle的實現：
def shuffle(self, x, random=None, int=int):
"""x, random=random.random -> shuffle list x in place; return None.
Optional arg random is a 0-argument function returning a random
float in [0.0, 1.0); by default, the standard random.random.
"""
if random is None:
random = self.random
for i in reversed(xrange(1, len(x))):
# pick an element in x[:i+1] with which to exchange x[i]
j = int(random() * (i+1))
x[i], x[j] = x[j], x[i]