怎么做网站的寄生,套餐,北京学网站开发,wordpress博客优秀代码比较粗糙#xff0c;主要是用于对排序算法的理解#xff0c;因而忽略了边界和容错处理相关代码。 相关文档#xff1a;
Insert Sort ,Bubble Sort ,Select Sort ,Shell sort ,Quick sort ,Heap sort ,Merge sort on Wikipedia
algorithm Repository :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.hint 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 Hibbards 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*inc1) ;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 knuths 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*inc1) ;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 Sedgewicks sequence: 1,5,19,41,...which can be constructed by:1,19,104,505,...,9(4^k-2^k)1, k0,1,2,3,...5,41,209,929,...,(2^(k2))*(2^(k2)-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[j1]){tmp a[j];a[j] a[j1];a[j1] 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 i1; 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(alow,n-low);return 0;
}
int heapify(int a[], int i, int n)
{int maxIndex i;int lChild 2*i1,rChild lChild1;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(amid,n-mid);mergeArray(a,mid,n);}return 0;
}
misc.c:
#include stdio.h
#include time.h
#include stdlib.hvoid 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
