代码比较粗糙，主要是用于对排序算法的理解，因而忽略了边界和容错处理相关代码。

 

相关文档：

Insert Sort  ,Bubble Sort ,Select Sort ,Shell sort ,Quick sort ,Heap sort ,Merge sort on Wikipedia

algorithm Repository :C语言实现部分排序算法，代码质量较高，其实现类似于库函数

sorting and searching algorithms :点击左边的链接即可查看整份文档

排序算法性能比较：图片链接

插入，选择，冒泡排序的算法复杂度为O(n^2)

希尔排序(shell sort)的算法复杂度因所采用增量序列的不同而有很大差别，例如shell增量序列（1,2,..,2^k)的算法复杂度可能达到O(n^2),其他增量序列则为O(n^1.5)到O(n^(7/6))不等，但其算法复杂度不可能达到O(nlogn);

快速排序，堆排序，归并排序算法复杂度为O(nlogn)。

快速排序虽然被认为是最快的，但是写一个完全正确的算法却并不容易（即在任何情况下算法复杂度均为O(nlogn))，感兴趣的可以看看glib 和bsd 的快速排序实现,有一篇论文《engineering a sort function 》中也写了qsort的实现

包含三个文件：

sort.c:

/* to compiler the program, use: gcc -o sort sort.c misc.c -g -Wall
/* insert sort */
#include <stdio.h>
#include <stdlib.h>
#include "misc.h"int insertSort(int a[], int n);
int shellSortSh(int a[], int n);
int shellSortHi(int a[], int n);
int shellSortKn(int a[], int n);
int bubSort(int a[], int n);
int selectSort(int a[], int n);
int median3(int a[], int n);
int quickSort(int a[], int n);
int heapify(int a[],int i, int n);
int heapSort(int a[], int n);
int mergeArray(int a[],int splitIndex,int n);
int mergeSort(int a[], int n);
/*
void testMedian3()
{int a[3] = {3,2,1};int len = ARRLEN(a);median3(a,len);printArray(a,len);}*/
int main(void)
{int a[] = {8,1,4,9,6,3,5,2,7,0};/*  int a[] = {5,7,3,8};*/int len = ARRLEN(a);/*  testSort(a,len,insertSort);*//*  testSort(a,len,shellSortKn);*/testSort(a,len,mergeSort);/*  testMedian3();*/return 0;
}
int insertSort(int a[], int n)
{int i,j;int tmp;for(i = 0; i < n; i++){tmp = a[i];for(j = i; j > 0 && a[j-1] > tmp; --j)a[j] = a[j-1];a[j] = tmp;/*      printArray(a,n);*/}return 0;
}
/* the origin shell sort by Shell using increment sequenceof n/2,n/4 ... 1 */
int shellSortSh(int a[], int n)
{int i,j;int inc;int tmp;for(inc = n/2; inc > 0; inc /= 2)for(i = inc; i <n; i++){tmp = a[i];for(j = i; j >= inc && tmp < a[j-inc]; j -= inc)a[j] = a[j-inc];a[j] = tmp;printArray(a,n);}return 0;
}
/* shell sort by Hibbard's sequence:2^k-1,...,7,3,1 */
int shellSortHi(int a[],int n)
{int i,j;int inc;int tmp;for(inc = 1; inc < n/2; inc = 2*inc+1) ;for( ; inc > 0; inc /= 2)for(i = inc; i <n; i++){tmp = a[i];for(j = i; j >= inc && tmp < a[j-inc]; j -= inc)a[j] = a[j-inc];a[j] = tmp;printArray(a,n);}return 0;
}
/* Shell sort using knuth's sequence:(3^k-1)/2,...,13,4,1 */
int shellSortKn(int a[], int n)
{int i,j;int inc;int tmp;for(inc = 1; inc < n/3; inc = 3*inc+1) ;for( ; inc > 0; inc /= 3)for(i = inc; i <n; i++){tmp = a[i];for(j = i; j >= inc && tmp < a[j-inc]; j -= inc)a[j] = a[j-inc];a[j] = tmp;printArray(a,n);}return 0;
}
/*for shell sort there is also a Sedgewick's sequence: 1,5,19,41,...which can be constructed by:1,19,104,505,...,9(4^k-2^k)+1, k=0,1,2,3,...5,41,209,929,...,(2^(k+2))*(2^(k+2)-3)+1, k = 0,1,2,3,.. *//*bubble sort */
int bubSort(int a[], int n)
{int i,j,tmp;for(i = n-1; i >= 0; --i)for(j = 0;  j < i; j++)if(a[j] >a[j+1]){tmp = a[j];a[j] = a[j+1];a[j+1] = tmp;}return 0;
}
/* select sort */
int selectSort(int a[], int n)
{int i,j;int minIndex,minNum;for(i = 0; i < n; i++){minIndex = i;minNum = a[i];for(j = i+1; j < n; j++)if(a[j] < minNum){minIndex = j;minNum = a[j];}a[minIndex] = a[i];a[i] = minNum;}return 0;
}
/* partition function to find a element to cut an array to two pieces */
/* This function is used by quick sort function */
int median3(int a[], int n)
{int mid = n/2-1;/* the following three sentences make sure thata[0] <= a[mid] <= a[n-1] */if(a[0] > a[mid])swap(&a[0],&a[mid]);if(a[0] > a[n-1])swap(&a[0],&a[n-1]);if(a[mid] > a[n-1])swap(&a[mid],&a[n-1]);/* exchange elemments to set the pivot at the beginning of array */swap(&a[0],&a[mid]);return a[0];
}
/* quick sort */
int quickSort(int a[], int n)
{int low = 1, high = n-1;int pivot;printArray(a,n);if(n <= 3){insertSort(a,n);return 0;}pivot = median3(a,n);while(low < high){while(a[low] < pivot) low++;while(a[high] > pivot) high--;if(low < high)swap(&a[low],&a[high]);elsebreak;/*      printArray(a,10);*/}swap(&a[0],&a[low-1]);quickSort(a,low-1);quickSort(a+low,n-low);return 0;
}
int heapify(int a[], int i, int n)
{int maxIndex = i;int lChild = 2*i+1,rChild = lChild+1;if(lChild < n && a[lChild] > a[maxIndex])maxIndex = lChild;if(rChild < n && a[rChild] > a[maxIndex])maxIndex = rChild;if(maxIndex != i){swap(&a[maxIndex],&a[i]);heapify(a,maxIndex,n);}return 0;
}
int heapSort(int a[], int n)
{int i;for(i = (n-1)/2; i >= 0; i--)heapify(a,i,n);for(i = n-1; i >0; i--){swap(&a[i],&a[0]);heapify(a,0,--n);}return 0;
}
int mergeArray(int a[], int splitIndex, int n)
{int *tmpArray = malloc(n*sizeof(int));int i ,left,right;i = left= 0;right = splitIndex;while(left < splitIndex && right < n){if(a[left] <= a[right])tmpArray[i++] = a[left++];elsetmpArray[i++] = a[right++];}while(left < splitIndex)tmpArray[i++] = a[left++];while(right < n)tmpArray[i++] = a[right++];for(i = 0; i < n; i++)a[i] = tmpArray[i];return 0;
}
int mergeSort(int a[], int n)
{int mid;if(n > 1){mid = n/2;mergeSort(a,mid);mergeSort(a+mid,n-mid);mergeArray(a,mid,n);}return 0;
}

 

misc.c:

#include <stdio.h>
#include <time.h>
#include <stdlib.h>void fillArray(int a[], int n)
{int i;srand(time(NULL));for(i = 0; i < n; i++)a[i] = rand();
}
void printArray(int a[], int n)
{int i;printf("%d",a[0]);for(i = 1; i < n; i++)printf(" %d",a[i]);printf("\n");
}
void testSort(int a[], int n, int (*sort)(int a[], int n))
{printf("the initial array is:\n");printArray(a,n);sort(a,n);printf("\nAfter sorting,the array is:\n");printArray(a,n);
}
void swap(int *x, int *y)
{int tmp = *x;*x = *y;*y = tmp;
}

 misc.h:

#ifndef MISC_H
#define MISC_H#define ARRLEN(a) (sizeof(a)/sizeof(a[0]))
void fillArray(int a[], int n);
void printArray(int a[], int n);
void testSort(int a[], int n, int (*sort)(int a[], int n));
void swap(int *x, int *y);
#endif