# 纸上谈兵: 排序算法简介及其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)

```/* 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;
}```

0 条评论

• ### 线性代数01 线性的大脑

线性代数是一门大学课程，但也是相当“惨烈”的一门课程。在大学期间，我对这门学科就没怎么学懂。先是挣扎于各种行列式、解方程，然后又看到奇怪的正交矩阵、酉矩阵。还没...

• ### 纸上谈兵: 堆 (heap)

堆(heap)又被为优先队列(priority queue)。尽管名为优先队列，但堆并不是队列。回忆一下，在队列中，我们可以进行的限定操作是dequeue和en...

• ### 纸上谈兵: 拓扑排序

《文明》是一款风靡20多年的回合制策略游戏，由Sid Meier开发。《文明》结构宏大，内容丰富，玩法多样，游戏性强，称得上是历史上最伟大的游戏。在文明中，你可...

• ### 【校赛小分队之我们有个女生】训练赛6

每个manager给数组a的第1到r[i]个数排序，t[i]==1则排升序，2则排降序。求m个manager排序完的序列。

• ### VR技术奠基者：虚拟现实在工业市场早已成熟

【腾讯科技编者按】亚隆·兰尼尔（Jaron Lanier）被公认为虚拟现实的奠基者，对当代科技行业的发展有着巨大的影响力。兰尼尔的成果被认为是虚拟现实技术的基础...

• ### 46. 全排列【回溯算法】

输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], ...

• ### 牛客练习赛23 D

利用全排列函数加vector数组，开十个vector，存a到i字母出现的位置，最后每个vector再push_back（字符串长度加一）作为结束标志。

• ### Day23-排序-快排&堆排&归并排序

右指针--，直到找到比基准值小的元素，将左右指针指向的元素进行交换；

• ### Java Integer源码解读

1、引言 public class IntegerDemo { public static void main(String[] args){ ...