冒用公司名义做网站,用asp.net做的网站模板下载,wordpress评论区镶嵌图片,邯郸企业做网站方案所有未排序的数组是经过检查合法的主要的内排序包括冒泡、插入、希尔、堆排序、归并、快速、桶排序等其C语言实现的源文件下载地址#xff1a;http://download.csdn.net/detail/mcu_tian/9530227冒泡排序冒泡排序应该是排序中最简单的算法了主要思路如下#xff1a;1#xf… 所有未排序的数组是经过检查合法的 主要的内排序包括冒泡、插入、希尔、堆排序、归并、快速、桶排序等 其C语言实现的源文件下载地址http://download.csdn.net/detail/mcu_tian/9530227 冒泡排序 冒泡排序应该是排序中最简单的算法了 主要思路如下 1 比较相邻的元素。如果第一个比第二个大就交换他们两个。 2对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对。在这一点最后的元素应该会是最大的数。 3针对所有的元素重复以上的步骤除了最后一个。 4 持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较。 C语言的一般实现如下 void bubble_sort(int *array,int num) { int i 0; int j 0; int temp; for(;j num;j) { for(i num;i j ;–i) { if(array[i] array[i-1]) { temp array[i]; array[i] array[i-1]; array[i-1] temp; } } } } 冒泡算法实现和原理都很简单而且是稳定的排序算法但是该算法不论什么情况下算法的比较交换的次数都是恒定的都为1234… …n-1 算法的复杂度为On^2 插入排序 插入排序是最简单常用的排序算法将数组分为两部分排好序的数列以及未排序的数列将未排序的数列中的元素与排好序的数列进行比较然后将该元素插入到已排序列的合适位置中。 直接插入排序 直接插入排序是插入排序中最简单的一种实现 该算法的主要思路是 ⒈ 从第一个元素开始该元素可以认为已经被排序 ⒉ 取出下一个元素在已经排序的元素序列中从后向前扫描 ⒊ 如果该元素已排序大于新元素将该元素移到下一位置 ⒋ 重复步骤3直到找到已排序的元素小于或者等于新元素的位置 ⒌ 将新元素插入到下一位置中 ⒍ 重复步骤2~5 该排序算法的C语言的一般实现如下 void insertion_sort(int *array,int num) { int i,j; int temp; i 0; j 0; for(;i num;i) { for(ji;(j 0)(array[j] array[j-1]);j–) { temp array[j-1]; array[j-1] array[j]; array[j] temp; } } } 该算法的最坏情况如逆序那么复杂度为O(N^2) 最好的情况如已经预先排好序或者基本排好那么复杂度为ON 上面实现的算法中排序数量比较大的时候在比较插入操作时直接比较操作的代价和交换操作很大是呈线性增长。 因此该算法适用于少量数据的排序。 希尔排序 希尔排序是把记录按下标的一定增量分组对每组使用直接插入排序算法排序随着增量逐渐减少每组包含的关键词越来越多当增量减至1时整个文件恰被分成一组算法便终止。 希尔排序是特殊的插入排序 上述的增量会逐渐减少直至减少到1该过程中增量会形成一个序列称为增量序列。 希尔排序的算法的时间复杂度跟增量序列密切相关。 具体实现如下 1:按希尔增量序列进行排序即增量序列为N/2,N/4………1 C语言的实现如下 void shell_sort(int *array,int num)// { int increment 0; int temp 0; int j 0; int k 0; int m 0; for(increment num/2;increment 0;increment / 2) { printf(“increment:%d \n “,increment); for(j 0;j increment;j) { for(k j;k num;k kincrement) { printf(“k:%d \n “,k); for(m k;(m j)(array[m] array[m-increment]);m m -increment) { temp array[m]; array[m] array[m-increment]; array[m-increment] temp; } } } } } 使用希尔增量时希尔排序的最坏时间复杂度为ON^2 2:按照Hibbard增量序列进行排序即增量序列为2^k-1………7,3,1 其中(2^k-1)n 此种增量的希尔排序的最坏运行时间为O(N^3/2) 3按照sedgwick增量序列进行排序增量序列为1,5,19,41,109…… 此种增量的希尔排序的的最坏运行时间为ON^7/6 以上两种的实现跟前面的希尔增量序列实现的代码差不多1除了最外层的循环迭代由于增量与序列的不同稍微有点变化之外。 堆排序 堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法。 将待排序的的序列构建成堆大根堆即父节点比子节点的数值要大小根堆父节点比子节点要小。 然后将堆的根最大值或者最小值取下剩余的数据再构建成堆再取下根值如此迭代直到只剩最后一个值。 出于效率的原因堆在数组中实现其中数组的下表对应着堆积树的节点序列取下的根节点将堆中的最后一个元素进行交换那么一直到最后该数组就是为一个排列好的数组。 其实现如下 void heap_sort(int *array,int num) { /* 初次建立大根堆注意数组下表与堆元素序列的对应问题数组的下表是从0开始的 o(n) */ int k; for(k num/2;k 0;k–) { int flag; int tmp; int i k ; while(2*i1 num) { if(2*i1 num-1) { flag 2*i 1; } else { if(array[2*i1] array[2*i2]) { flag 2*i 1; } else { flag 2*i 2; } } if(array[i] array[flag]) break; else { tmp array[flag]; array[flag] array[i]; array[i] tmp; i flag; } } } /*取下根与堆的最后一个元素交换再重新建堆如此迭代往复*/ int max; int end; int i; for(i 0;i num;i ) { //put the max num to the end end num -1 -i; max array[0]; array[0] array[end]; array[end] max; //rebuild the heap,the length of array is end – 1 int flag; int tmp; int i 0; while(2*i1 end) { if(2*i1 end-1) { flag 2*i 1; } else { if(array[2*i1] array[2*i2]) { flag 2*i 1; } else { flag 2*i 2; } } if(array[i] array[flag]) break; else { tmp array[flag]; array[flag] array[i]; array[i] tmp; i flag; } } } } 在实现过程的时候第一阶段堆的构建最多用到2N次比较在取掉最大值重新建堆的一次过程中最多用到2logi。 因此在最坏的情况下总数最多为2NlogN-ON次比较。 在实践中慢于sedgewick增量排序是 不稳定的排序方法 归并排序 归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide and Conquer的一个非常典型的应用。 将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并也就是下面用到的方法。 归并排序使用递归实现递归的终止条件为当一个序列只有一个元素的时候为已排序序列即返回然后返回的两个序列都为已排序序列使用归并进行合并排序。 其实现C代码如下 //两个序列在同一个数组中而且在位置上是相邻的根据形参将两个序列标记出来将两个序列归并结果到临时数组中然后在复制到数组中。 //实现过程中很多地雷尤其数组下标一不小心就越界了。core dump void merge(int *array,int *tmp_array,int lpos,int rpos,int end) { int left_end rpos – 1; int right_end end; int left_pos lpos; int right_pos rpos; int i; int tmp 0; while((left_pos left_end)(right_pos right_end)) { if(array[left_pos] array[right_pos]) { tmp_array[tmp] array[left_pos]; left_pos; } else { tmp_array[tmp] array[right_pos]; right_pos; } tmp; } while(left_pos left_end) { tmp_array[tmp] array[left_pos]; left_pos; tmp; } while(right_pos right_end) { tmp_array[tmp] array[right_pos]; right_pos; tmp; } for(i 0;i tmp;i) { array[lpos i] tmp_array[i]; } } //递归的实现终止条件为只有一个数返回 //递归返回之后该序列部分为已经排好序 //将两次的返回序列进行归并排序 void m_sort(int *array,int *tmp_array,int left,int right) { int centre (left right)/2; if(left right) { m_sort(array,tmp_array,left,centre); m_sort(array,tmp_array,centre1,right);//centre记住只能不能是-坑死老爹了要是-的话如left 0right 1的时候centre就是 -1呀都越界到天边去了。调了好久。 merge(array,tmp_array,left,centre1,right); } } //这个也可以不要其实就可以了但是为了保持与前面排序算法的实现保的函数形参保持一致还是加上了。 void recursion_merge_sort(int *array,int num) { int *tmp_array; tmp_array malloc(num*sizeof(int)); assert(tmp_array ! NULL); m_sort(array,tmp_array,0,num-1); free(tmp_array); } 该实现并没有在每次递归中使用临时数组而是公用了一个指针传递过来的数组这样大大的减少了算法过程中不会导致内存线性的消耗。 归并排序的算法复杂度为ONlogN但是一般不用于主存的内部排序因为可能增加排序的时候附加的内存主要用在外部排序对于内部排序主要还是快排。 快速排序 快速排序采用的思想是分治思想。 快速排序是找出一个元素理论上可以随便找一个作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值如此作为基准的元素调整到排序后的正确位置。递归快速排序将其他n-1个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正 确位置排序完成。所以快速排序算法的核心算法是分区操作即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。 快速排序的关键问题在找基准值的问题由于找的值不能太小也不太大大概使分区后两个区的元素数量基本上没有太大的偏差。 基准值的选取不能是最大值和最小值虽然这样最后能够完成排序但是算法的效率就会大大的打折扣。 若是随机选取值都有可能取得值过大或者过小。 比较安全的做法是使用三数中值分割法即使用两端的值加上中间位置的值中的中间值作为基准值这样可以消除最坏的情况。 在选取基准值之后然后就类似于归并递归式一样进行分割递归。 但是待排序的数组小于20以后可以选取直接使用插入排序因为对于小数组进行分割递归的话其效率往往还不如直接使用插入。 下面为C实现的代码 //使用三数中值法选取中至作为基准值然后将三个数值中的中值放在倒数第二个最大值放置于最后面 //这样放置元素之后那么这三个值最小值和最大值已经放在了合适的位置不需要再进行比较移动了在后面的算法中可以体现 //返回数组中的倒数第二个值即基准值这样放的优点是能够使左右两边的在遍历的时候可以应对极端情况可以遍历到所有元素。 int median_three(int *array,int left,int right) { int centre; int tmp; int i; centre (leftright)/2; if(array[left] array[right]) { tmp array[right]; array[right] array[left]; array[left] tmp; } if(array[centre] array[right]) { tmp array[right]; array[right] array[centre]; array[centre] tmp; } if(array[left] array[centre]) { tmp array[centre]; array[centre] array[left]; array[left] tmp; } tmp array[centre]; array[centre] array[right-1]; array[right-1] tmp; return array[right-1]; } //快排实现 void q_sort(int*array,int left,int right) { int pivot; int left_i; int right_i; int tmp; if(right-left 3) { insertion_sort(arrayleft,right-left1); //当待排的数量小于3的时候就直接快排其实小于20可以这里是了验证 } else { pivot median_three(array,left,right);//找出基准值 left_i left 1; //从左边加一个在三数中值的时候小于中间值的已经放在了左边因此没有必要再进行比较操作 right_i right -2;//同上加上中间值放在倒数第二个位置 while(1) { while(array[left_i] pivot )//相等就停止左右两边都是这样可以使相等的值最大限度地在基准值的左右两边均匀分布 { left_i; } while(array[right_i] pivot) { –right_i; } if(left_i right_i) { tmp array[left_i]; array[left_i] array[right_i]; array[right_i] tmp; } else //当左边的游标等于或者大于右边的右边时候该趟分割结束 { break; } } //由于校准值放在数组的倒数第二个因此将其放到合适的位置去即与左游标对应的值与其进行交换即可 tmp array[left_i]; array[left_i] array[right-1]; array[right-1] tmp; //继续迭代 q_sort(array,left,left_i); q_sort(array,left_i1,right); } } void quick_sort(int *arrary,int num) { q_sort(arrary,0,num-1); } 快速排序是实践中最快的已知算法平均运行时间为O(NlogN)最坏的情况是ON^2 只要不要在选取校准值太坏以及以及在处理相等的值时停止最坏的情况基本上是可以避免的。 桶排序 桶排序非常高效 但是该算法只能用于整数排序。 算法的实现 其具体的算法实现为使用一个数组初始化的值为0数组长度不小于于待排序的所有数据的最大值 遍历一遍待排序的数据序列将数列中的数据对应到数组中的下标将数组中该元素置为1或者加1。 例如 满足条件的数组A[i] 初始化值都为0 待排序的序列a,b,c 遍历一遍待排序的序列将序列中的元素对应到元素的位置将值1例如A[a] 1; 然后再遍历一遍数组 for(i 0;i max;i) { while(A[i]) { 输出该值 A[i]– } } 则输出的值的序列就是排序过后的序列了。 该算法的运算复杂度为O(max) max 为待排序列中的最大值 max的确定可以遍历一遍数组确定也可以根据输入的范围估计。 但是该算法不能用于浮点排序只能用于整数排序如果是有负数那么负数和下标的对应关系需要注意。 而且当max很大的时候并且排序的元素不是很多的时候会占用大量的内存空间造成大量的内存浪费效率反而会降低。 因此该种算法只适用于该max值不大的整数排序。 在C中可以使用bool 或者使用位运算用位中0和1标识序列中存在的数值 但是该只能用于没有重复的数据或者是可以忽略重复的数据。 位的排序在以前的博客中有写到链接为 http://blog.csdn.net/mcu_tian/article/details/46834589 参考资料数据结构与算法分析C语言描述原书第2版
