部分排序算法c语言实现
代码比较粗糙，主要是用于对排序算法的理解，因而忽略了边界和容错处理相关代码。
?
相关文档：
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 sequence of 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 that a[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++]; else tmpArray[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?