实用排序算法（复杂度小于等于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
=
min
; t
<=
max
; 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
);
}
-
这是堆排序，相对复杂些，效率是std::sort的四分之一
C/C++ code
-
UINT parent(UINT i)
{
return
(UINT)floor(i
/
2
);
}
UINT left(UINT i)
{
return
2
*
i;
}
UINT right(UINT i)
{
return
(
2
*
i
+
1
);
}
void
Max_Heapify(BYTE
*
A, UINT i, UINT length)
{
UINT l
=
left(i);
UINT r
=
right(i);
UINT largest;
BYTE temp;
if
(l
<
length
&&
A[l]
>
A[i])
largest
=
l;
else
largest
=
i;
if
(r
<
length
&&
A[r]
>
A[largest])
largest
=
r;
if
(largest
!=
i)
{
temp
=
A[i];
A[i]
=
A[largest];
A[largest]
=
temp;
Max_Heapify(A, largest, length);
}
}
void
Build_Max_Heap(BYTE
*
A, UINT length)
{
int
i
=
0
;
for
(i
=
length; i
>=
0
; i
--
)
Max_Heapify(A, i, length);
}
void
HeapSort(BYTE
*
A, UINT length)
{
BYTE temp;
int
i
=
0
;
Build_Max_Heap(A,length);
for
(i
=
length
-
1
; i
>=
1
; i
--
)
{
temp
=
A[
0
];
A[
0
]
=
A[i];
A[i]
=
temp;
length
=
length
-
1
;
Max_Heapify(A,
0
, length);
}
}
