排序算法，别让教育束缚你

zfzhuman123 · 发表于 2011-7-28 11:24:16

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由 zfzhuman123 于 2011-7-28 11:24 编辑

实用排序算法（复杂度小于等于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);
}

复制代码

JX机械 · 发表于 2011-7-28 15:00:01

先收藏下来。。。

我挖 · 发表于 2013-7-2 22:35:37

看帖就要回帖支持下

fishmo · 发表于 2013-7-2 23:27:49

看看，支持下

hehex · 发表于 2013-7-3 12:12:11

确实不错，学习了。

Cocol · 发表于 2013-7-3 19:29:27

看看，回复支持下

账号		自动登录	找回密码
密码			立即注册

[技术交流] 排序算法，别让教育束缚你

马上注册，结交更多好友，享用更多功能^_^