- 浏览: 72684 次
- 性别:
- 来自: 杭州
最新评论
代码比较粗糙,主要是用于对排序算法的理解,因而忽略了边界和容错处理相关代码。
相关文档:
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]); else break; /* 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
发表评论
-
最小c编译器
2011-11-08 14:09 1479最小c编译器(来源 (最好在linux下操作))代码有好几个 ... -
the development of c language(转)
2011-11-08 09:25 1312c语言之父Dennis Ritchie 写的关于c语言开发历 ... -
C语言,你真的弄懂了么?
2011-11-07 12:42 1768程序(来源 ): #include <stdi ... -
pe文件格式实例解析
2011-11-07 10:05 0环境:windows xp 速龙3000+(即x86兼容32位 ... -
小型elf "Hello,World"程序
2011-11-06 23:59 1373参考链接:http://timelessname.com/el ... -
elf文件格式实例解析
2011-11-05 23:00 6356试验环境:archlinux 速龙3000+(即x86兼 ... -
高质量的c源代码
2011-11-03 10:18 1152现在自由软件及开源软件越来越流行,有大量的附带源程序 ... -
fltk 库
2011-09-26 19:47 1838fltk是一个小型、开源、支持OpenGL 、跨平台(win ... -
《Introduction to Computing Systems: From bits and gates to C and beyond》
2011-09-25 23:33 2183很好的一本计算机的入门书,被很多学校采纳作为教材,作者Yale ... -
csapp bufbomb实验
2011-09-16 14:21 4620csapp (《深入理解计算机系统》)一书中有一个关于缓冲区 ... -
the blocks problem(uva 101 or poj 1208)
2011-09-11 20:57 1837题目描述见:uva 101 or poj 1208 ... -
the blocks problem(uva 101 or poj 1208)
2011-09-11 20:56 0题目描述见:uva 101 or poj 1208 ... -
编译器开发相关资源
2011-08-31 08:40 1211开发编译器相关的一些网络资源: how difficu ... -
zoj 1025 Wooden Sticks
2011-07-23 20:25 968题目见:zoj 1025 先对木棒按照长度进行排序,然后再计 ... -
zoj 1088 System Overload
2011-07-23 17:30 1168约瑟夫环 (josephus problem )问题, ... -
zoj 1091 Knight Moves
2011-07-23 09:05 847题目见zoj 1091 使用宽度搜索优先来求解, ... -
zoj 1078 palindrom numbers
2011-07-22 19:31 1147题目见zoj 1078 主要是判断一个整数在基数为2 ... -
zoj 1006 do the untwist
2011-07-22 13:24 937题目见zoj 1006 或poj 1317 简单 ... -
zoj 3488 conic section
2011-07-22 12:23 1009题目见zoj 3488 很简单的题目,却没能一次搞定,因 ... -
zoj 1005 jugs
2011-07-22 11:43 842题目内容见zoj1005 由于A,B互素且A的容 ...
相关推荐
C语言实现的堆排序算法。 提供了堆排序算法的一个接口,可以为其它功能提供功能。
冒泡排序算法选择排序算法插入排序c语言实现
根据给定的文件信息,我们可以总结出以下关于“二分法排序算法C语言实现”的相关知识点: ### 1. 二分法搜索算法原理 二分法搜索算法,也称为折半查找算法,是一种在有序数组中查找特定元素的搜索算法。其基本思想...
本资源"常用排序算法C语言实现"提供了一个实践平台,帮助学习者将理论知识转化为实际代码。 首先,让我们探讨几种常见的排序算法及其C语言实现: 1. **冒泡排序(Bubble Sort)**:冒泡排序是最基础的排序方法,...
本资料“八大排序算法C语言”聚焦于八种常见的排序算法,每种都有C语言实现,这对于理解和实践这些算法非常有帮助。 1. **冒泡排序**:冒泡排序是一种简单的交换排序,通过不断遍历数组并交换相邻的逆序元素来逐步...
一些常用排序算法的C语言实现,包括直接选择排序,希尔排序,直接插入排序,快速排序,归并排序,冒泡排序,堆排序
在本资源中,我们主要关注的是使用C语言实现算法的解答,这涵盖了算法的第1到第4个部分。C语言是一种广泛用于系统编程、应用编程、嵌入式系统以及编写算法实现的强大编程语言。其简洁性和高效性使得它成为学习和理解...
快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治策略,即将一个大问题分解为小问题来解决。在这个案例中,我们关注的是如何用C语言实现快速排序。 快速排序的步骤...
本资源“基本排序算法C语言实现”提供了一系列经典的排序算法的C语言实现,帮助开发者深入理解这些算法的工作原理并能实际运用到项目中。 1. **冒泡排序**: 冒泡排序是一种简单的排序算法,它重复地遍历要排序的...
快速排序算法 C语言实现 快速排序算法是一种高效的排序算法,通过递归的方式将记录分区排序。下面将详细介绍快速排序算法的实现细节。 首先,我们需要了解快速排序算法的基本思想。快速排序算法的核心思想是选择一...
完整的实现了归并排序的算法,使用C语言实现,相信看过本程序之后,会对归并排序了如指掌
归并排序算法C语言版
学习堆排序时自己编的代码,里面有自动生成随机数的代码段方便大家测试
本资源提供了各种常用排序算法的C语言实现,源自严蔚敏的经典教材《数据结构》。下面将详细介绍这些排序算法及其在C语言中的实现原理。 1. 冒泡排序(Bubble Sort) 冒泡排序是最基础的排序方法,通过不断交换相邻...
在本压缩包“算法C语言实现(第1-4部分).zip”中,包含的是关于算法的详细实现,使用了C语言这一经典编程语言。C语言以其高效、灵活和接近硬件的特点,常被用于编写算法代码,特别是对于数据结构和算法的底层实现,它...
排序算法是算法学习的基础,书中可能会详细介绍各种排序算法,如冒泡排序、选择排序、插入排序、快速排序、归并排序等,并通过C语言实现。这些算法各有优劣,适用于不同场景。例如,快速排序因其高效性而广泛应用于...
经典算法通常指的是那些在计算机科学中被广泛研究、具有普遍意义并被广泛应用的算法,例如排序算法(如冒泡排序、快速排序、归并排序)、搜索算法(如二分查找、深度优先搜索、广度优先搜索)以及数据结构(如栈、...
根据给定文件的信息,《算法:C语言实现(第1~4部分)基础知识、数据结构、排序及搜索》这本书主要聚焦于使用C语言来实现各种算法和数据结构。这是一本非常实用且深入浅出的计算机科学教材,对于学习者来说,能够帮助...
排序算法,包括典型的排序,起泡法、快速排序、选择排序等等
算法:C语言实现 (第1-4部分)基础知识、数据结构、排序及搜索(原书第3版) 本书是Sedgewick彻底修订和重写的C算法系列的第一本。全书分为四部分,共16章。第一部分“基础知识”(第1—2章)介绍基本算法分析原理。...