2014
01-31

# 纸上谈兵: 排序算法简介及其C实现

(C语言的数组名都转成指针，传递给函数，所以需要传递数组中元素的数目ac给函数，详细见”Expert C Programming: Deep C Secrets”一书)

http://www.sorting-algorithms.com/

### 冒泡排序 (Bubble Sort)

/*By Vamei*/
/*swap the neighbors if out of order*/
void bubble_sort(int a[], int ac)
{
/*use swap*/
int i,j;
int sign;
for (j = 0; j < ac-1; j++) {
sign = 0;
for(i = ac-1; i > j; i--)
{
if(a[i-1] > a[i]) {
sign = 1;
swap(a+i, a+i-1);
}
}
if (sign == 0) break;
}
}

### 插入排序 (Insertion Sort)

/*By Vamei*/
/*insert the next element
into the sorted part*/
void insert_sort(int a[], int ac)
{
/*use swap*/
int i,j;
for (j=1; j < ac; j++)
{
i = j-1;
while((i>=0) && (a[i+1] < a[i]))
{
swap(a+i+1, a+i);
i--;
}
}
}

### 选择排序 (Selection Sort)

/*By Vamei*/
/*find the smallest of the rest,
then append to the sorted part*/
void select_sort(int a[], int ac)
{
/*use swap*/
int i,j;
int min_idx;
for (j = 0; j < ac-1; j++)
{
min_idx = j;
for (i = j+1; i < ac; i++)
{
if (a[i] < a[min_idx])
{
min_idx = i;
}
}
swap(a+j, a+min_idx);
}
}

### 希尔排序 （Shell Sort）

/*By Vamei*/
/*quickly sort the turtles at the tail of the array*/
void shell_sort(int a[], int ac)
{
int step;
int i,j;
int nsub;
int *sub;

/* initialize step */
step = 1;
while(step < ac) step = 3*step + 1;

/* when step becomes 1, it's equivalent to the bubble sort*/
while(step > 1) {
/* step will go down to 1 at most */
step = step/3 + 1;
for(i=0; i<step; i++) {
/* pick an element every step,
and combine into a sub-array */
nsub = (ac - i - 1)/step + 1;
sub = (int *) malloc(sizeof(int)*nsub);
for(j=0; j<nsub; j++) {
sub[j] = a[i+j*step];
}
/* sort the sub-array by bubble sorting.
It could be other sorting methods */
bubble_sort(sub, nsub);
/* put back the sub-array*/
for(j=0; j<nsub; j++) {
a[i+j*step] = sub[j];
}
/* free sub-array */
free(sub);
}
}
}

Shell Sorting依赖于间隔(step)的选取。一个常见的选择是将本次间隔设置为上次间隔的1/1.3。见参考书籍。

### 归并排序 (Merge Sort)

/*By Vamei*/
/*recursively merge two sorted arrays*/
void merge_sort(int *a, int ac)
{
int i, j, k;
int ac1, ac2;
int *ah1, *ah2;
int *container;

/*base case*/
if (ac <= 1) return;

/*split the array into two*/
ac1 = ac/2;
ac2 = ac - ac1;
ah1 = a + 0;
ah2 = a + ac1;

/*recursion*/
merge_sort(ah1, ac1);
merge_sort(ah2, ac2);

/*merge*/
i = 0;
j = 0;
k = 0;
container = (int *) malloc(sizeof(int)*ac);
while(i<ac1 && j<ac2) {
if (ah1[i] <= ah2[j]) {
container[k++] = ah1[i++];
}
else {
container[k++] = ah2[j++];
}
}
while (i < ac1) {
container[k++] = ah1[i++];
}
while (j < ac2) {
container[k++] = ah2[j++];
}

/*copy back the sorted array*/
for(i=0; i<ac; i++) {
a[i] = container[i];
}
/*free space*/
free(container);
}

### 快速排序 (Quick Sort)

/*By Vamei*/
/*select pivot, put elements (<= pivot) to the left*/
void quick_sort(int a[], int ac)
{
/*use swap*/

/* pivot is a position,
all the elements before pivot is smaller or equal to pvalue */
int pivot;
/* the position of the element to be tested against pivot */
int sample;

/* select a pvalue.
Median is supposed to be a good choice, but that will itself take time.
here, the pvalue is selected in a very simple wayi: a[ac/2] */
/* store pvalue at a[0] */
swap(a+0, a+ac/2);
pivot = 1;

/* test each element */
for (sample=1; sample<ac; sample++) {
if (a[sample] < a[0]) {
swap(a+pivot, a+sample);
pivot++;
}
}
/* swap an element (which <= pvalue) with a[0] */
swap(a+0,a+pivot-1);

/* base case, if only two elements are in the array,
the above pass has already sorted the array */
if (ac<=2) return;
else {
/* recursion */
quick_sort(a, pivot);
quick_sort(a+pivot, ac-pivot);
}
}

### 堆排序 (Heap Sort)

(heap)是常见的数据结构。它是一个有优先级的队列。最常见的堆的实现是一个有限定操作的Complete Binary Tree。这个Complete Binary Tree保持堆的特性，也就是父节点(parent)大于子节点(children)。因此，堆的根节点是所有堆元素中最小的。堆定义有插入节点删除根节点操作，这两个操作都保持堆的特性。

/* By Vamei
Use an big array to implement heap
DECLARE: int heap[MAXSIZE] in calling function
heap[0] : total nodes in the heap
for a node i, its children are i*2 and i*2+1 (if exists)
its parent is i/2  */

void insert(int new, int heap[])
{
int childIdx, parentIdx;
heap[0] = heap[0] + 1;
heap[heap[0]] = new;

/* recover heap property */
percolate_up(heap);
}

static void percolate_up(int heap[]) {
int lightIdx, parentIdx;
lightIdx  = heap[0];
parentIdx = lightIdx/2;
/* lightIdx is root? && swap? */
while((parentIdx > 0) && (heap[lightIdx] < heap[parentIdx])) {
/* swap */
swap(heap + lightIdx, heap + parentIdx);
lightIdx  = parentIdx;
parentIdx = lightIdx/2;
}
}

int delete_min(int heap[])
{
int min;
if (heap[0] < 1) {
/* delete element from an empty heap */
printf("Error: delete_min from an empty heap.");
exit(1);
}

/* delete root
move the last leaf to the root */
min = heap[1];
swap(heap + 1, heap + heap[0]);
heap[0] -= 1;

/* recover heap property */
percolate_down(heap);

return min;
}

static void percolate_down(int heap[]) {
int heavyIdx;
int childIdx1, childIdx2, minIdx;
int sign; /* state variable, 1: swap; 0: no swap */

heavyIdx = 1;
do {
sign     = 0;
childIdx1 = heavyIdx*2;
childIdx2 = childIdx1 + 1;
if (childIdx1 > heap[0]) {
/* both children are null */
break;
}
else if (childIdx2 > heap[0]) {
/* right children is null */
minIdx = childIdx1;
}
else {
minIdx = (heap[childIdx1] < heap[childIdx2]) ?
childIdx1 : childIdx2;
}

if (heap[heavyIdx] > heap[minIdx]) {
/* swap with child */
swap(heap + heavyIdx, heap + minIdx);
heavyIdx = minIdx;
sign = 1;
}
} while(sign == 1);
}

### 总结

/* By Vamei */
/* exchange the values pointed by pa and pb*/
void swap(int *pa, int *pb)
{
int tmp;
tmp = *pa;
*pa = *pb;
*pb = tmp;
}

1. #!/usr/bin/env python
def cou(n):
arr =
i = 1
while(i<n):
arr.append(arr[i-1]+selfcount(i))
i+=1
return arr[n-1]

def selfcount(n):
count = 0
while(n):
if n%10 == 1:
count += 1
n /= 10
return count

2. 一开始就规定不相邻节点颜色相同，可能得不到最优解。我想个类似的算法，也不确定是否总能得到最优解：先着一个点，随机挑一个相邻点，着第二色，继续随机选一个点，但必须至少有一个边和已着点相邻，着上不同色，当然尽量不增加新色，直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢