清风竹林

ぷ雪飘绛梅映残红
   ぷ花舞霜飞映苍松
     ----- Do more,suffer less

冒泡和选择排序该被踢出教材了(转)

文章源于csdn的一篇帖子,原地址:http://topic.csdn.net/u/20100805/20/231B9356-847D-4FE9-87BA-2A2A3C55CA76.html

非常汗颜,楼主所提到的一些方法,像鸽巢排序与梳排序的名字我都没听说过,故摘抄至此,共勉之!

--------------------------------------------------------------------------------------
实用排序算法(复杂度小于等于O(n^2))中效率最低但实现并不是最简单的的两个,C、C++教材却总喜欢拿来大讲特讲,非常不利于初学者养成“程序效率”的思维。

实际上,各种排序算法里,除了堆排序实现较为复杂外,从代码量的角度,大多数算法都不比冒泡、选择算法复杂多少。

举几个高速的排序算法的例子,这些才适合进入教材

鸽巢排序,排序字节串、宽字节串最快的排序算法,计数排序的变种(将计数缓冲区大小固定,少一次遍历开销),速度是STL中std::sort的20多倍,更重要的是实现极其简单!缺点是需要一个size至少等于待排序数组取值范围的缓冲区,不适合int等大范围数据
C/C++ code
void PigeonholeSort(BYTE *array, int length) { int b[256] = {0}; int i,k,j = 0; for(i=0; i<length; i++) b[array[i]]++; for(i=0; i<256; i++) for(k=0; k<b[i]; k++) array[j++] = i; }



多一次遍历的计数排序,排序字节串的话速度约是鸽巢排序的一半
C/C++ code
void CountingSort(BYTE *array, int length) { int t; int i, z = 0; BYTE min,max; int *count; min = max = array[0]; for(i=0; i<length; i++) { if(array[i] < min) min = array[i]; else if(array[i] > max) max = array[i]; } count = (int*)malloc((max-min+1)*sizeof(int)); for(i=0; i<max-min+1; i++) count[i] = 0; for(i = 0; i < length; i++) count[array[i]-min]++; for(t = 0; t <= 255; t++) for(i = 0; i < count[t-min]; i++) array[z++] = (BYTE)t; free(count); }


快速排序,快排最标准的递归实现,速度约是std::sort的一半
C/C++ code
void swap(BYTE *a,BYTE *b) { BYTE tmp; if ( a != b ) { tmp = *a; *a = *b; *b = tmp; } } int partition(BYTE *arr,int left, int right) { int i = left - 1, j = right; BYTE v = arr[right]; while(1) { while(arr[++i] < v); while(arr[--j] > v) if(j == 1) break; if(i >= j) break; swap(&arr[i],&arr[j]); } swap(&arr[i],&arr[right]); return i; } void quicksort(BYTE *arr, int left, int right) { if (left < right) { int i = partition(arr,left,right); quicksort(arr,left,i-1); quicksort(arr,i+1,right); } } void QuickSort(BYTE *array,int length) { quicksort(array,0,length-1); }


这是速度与std::sort相当的三路划分快排
C/C++ code
void swap(BYTE *a,BYTE *b) { BYTE tmp; if ( a != b ) { tmp = *a; *a = *b; *b = tmp; } } void quicksort(BYTE *arr, int left, int right) { if (left < right) { BYTE v = arr[right]; int i = left - 1,j = right,p = left - 1,q = right,k=0; while (1) { while (arr[++i] < v); while (arr[--j] > v) if(j==left) break; if (i >= j) break; swap(&arr[i], &arr[j]); if(arr[i] == v) { p++; swap(&arr[p],&arr[i]); } if(arr[j] == v) { q--; swap(&arr[q],&arr[j]); } } swap(&arr[i],&arr[right]); j = i - 1; i++; for(k=left; k<=p; k++,j--) swap(&arr[k],&arr[j]); for(k=right-1; k>=q; k--,i++) swap(&arr[k],&arr[i]); quicksort(arr,left,j); quicksort(arr,i,right); } } void QuickSort(BYTE *array,int length) { quicksort(array,0,length-1); }



相当简单的梳排序,效率是std::sort的三分之一
C/C++ code
void CombSort(BYTE *arr, int size) { UINT gap = size, swapped = 1, i = 0; BYTE swap = 0; while ((gap > 1) || swapped) { if (gap > 1) gap = gap / 1.3; swapped = 0; i = 0; while ((gap + i) < size) { if (arr[i] - arr[i + gap] > 0) { swap = arr[i]; arr[i] = arr[i + gap]; arr[i + gap] = swap; swapped = 1; } ++i; } } }


LSD基数排序,与std::sort速度相当,但是需要一个与输入缓冲一样大的缓冲区
C/C++ code
#define R 256 #define digit(a, d) ( a >> 8*d ) static BYTE *aux; void radix_sort(BYTE *arr, int left, int right) { if(left < right) { int d = 0; for(d=3; d>=0; d--) { int i=0, j=0, count[R+1]; for(j=0; j<R; j++) count[j] = 0; for(i=left; i<=right; i++) count[digit(arr[i],d) + 1]++; for(j=1; j<R; j++) count[j] += count[j-1]; for(i=left; i<=right; i++) aux[count[digit(arr[i],d)]++] = arr[i]; for(i=left; i<=right; i++) arr[i] = aux[i-1]; } } } void RadixSort(BYTE *array,int length) { aux = (BYTE*)malloc(length); radix_sort(array,0,length-1); free(aux); }


归并排序,效率越是std::sort的六分之一,通常的实现是递归,但和快排不同,归并改循环极其容易
C/C++ code
void merge(BYTE *array, int low, int mid, int high) { int i, k; BYTE *temp = (BYTE *) malloc(high-low+1); int begin1 = low; int end1 = mid; int begin2 = mid + 1; int end2 = high; for (k = 0; begin1 <= end1 && begin2 <= end2; ++k) if(array[begin1]<array[begin2]) temp[k] = array[begin1++]; else temp[k] = array[begin2++]; while(begin1<=end1) temp[k++] = array[begin1++]; while(begin2<=end2) temp[k++] = array[begin2++]; for (i = 0; i < (high-low+1); i++) array[low+i] = temp[i]; free(temp); } void merge_sort(BYTE *array, UINT first, UINT last) { UINT mid,i; for(mid=1; mid<=last-first; mid += mid) for(i=first; i<=last-mid; i+=mid+mid) merge(array,i,i+mid-1,min(i+mid+mid-1,last)); } void MergeSort(BYTE *array, UINT length) { merge_sort(array,0,length-1); }

posted on 2010-11-25 09:59 李现民 阅读(880) 评论(2)  编辑 收藏 引用 所属分类: 绝对盗版算法为魂

评论

# re: 冒泡和选择排序该被踢出教材了(转) 2010-11-28 01:15 oldman

总结的很好,但对于帖子的名称,建议改换之,理由如下:

中国的国情是大部分计算机专业的学生是从命令式语言开始学习的,比如C。在命令式语言的范围内,冒泡和选择排序是比较好理解的,对于初学者来讲是个很好的入门方式。一开始就让初学者学一些不太浅显易懂的算法,徒然让他们对这份领域望而生畏。

还有如果要介绍计数排序和桶排序,最好把基于比较和不是基于比较的系统讲解下,这样有助于学生对排序算法建立宏观的感性认知。

另外,强烈建议计算机专业开设FP(函数式编程)课程,FP的思想对理解数据结构和算法有很好的帮助  回复  更多评论   

# re: 冒泡和选择排序该被踢出教材了(转) 2010-11-28 09:35 李现民

@oldman
对您提出的意见表示感谢
但是, 这文章是转csdn上的一篇帖子,帖子的地址您可以在文章的最开始处看到,基于尊重原创的想法,我觉得还是不要去修改的好。
再次表示感谢!  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理