张仰彪第二排序法
转自:http://topic.csdn.net/u/20080116/18/22a46692-c7ee-4bdc-ae7d-c95f01232b5e.html
张仰彪第二排序法的原理与目前非常流行的反恐类网络游戏有些类似，它将待排序数组内放错位置的数据视为隐藏在节日游行队列里故意站错位置的恐怖分子，并自动地将这些恐怖分子按照它们相互之间的内在关系而分成几个不同的小组。排序时反恐队员首先从游行队列的最前头开始清查，若遇到的人是好人，就快速通过去查下一个。如果查到一个站错位置的恐怖分子，就停下来在这个位置上连续地排查运作，直到将这个恐怖分子及其所在小组的全部成员都清理到正确的位置上，然后才继续前行去查下一个位置。直到清查的次数比队列的长度小1时，尽管此时反恐队员可能仅沿着游行队列前行了很短的一段距离，还处在队列的头部，但队列中所有站错位置的恐怖分子都已被清理到了正确的位置上，排序完毕。
下面给出张仰彪第二排序法的C语言代码：
------------------------------------------------------------------------------------------
# include < stdio.h >
void main ( )
{
int a [10]；
int i； /* 记录排序的次数，并用于输入输出 */
int j = 0； /* 记录当前排序的位置 */
int temp； /* 数据交换时的存储中介 */
int order； /* 记录数据在数组里的大小排名，从小向大算 */
printf ( " Input 10 numbers：\n" )；
for ( i＝0；i < 10；i++ ) /* 输入任意10个整数 */
scanf ( " %d"，&a[i] )；
printf ( " \n" )；
for ( i＝0；i < 9；i ++ ) /* 排序的总次数比待排序数组的长度小1 */
{
order = j； /* 数据的排名从当前位置开始向后计算 */
for ( int x = j+1；x < 10；x ++ ) /* 计算当前数据在数组里的排名 */
if ( a[x] < a[j] ) order ++；
if ( order > j ) /* 如果当前数据的排名大于它现在的位置 */
{
while ( a[j] = = a[order] ) order ++； /* 处理数组里的重复数据 */
temp = a[order]； /* 将这个数据交换到正确的位置上 */
a[order] = a[j]；
a[j] = temp；
}
else /* 如果当前数据的排名等于（不可能小于）它现在的位置 */
j ++； /* 开始排下一个位置上的数据 */
}
printf ( " The sorted numbers is：\n" )；
for ( i＝0；i < 10；i ++ ) /* 输出排好序的10个整数 */
printf ( " %d"，a[i] )；
printf ( " \n" )；
}
-------------------------------------------------------------------------------
下面是本排序法的算法例子，其中带下划线的数是已排好位置的数，红色的数是当前排序的位置。
{ 4， 5， 2， 4， 1， 3，0，2， 2，0 }
第1步： 排位置0上的数"4"， 有7个比它小得数， 它的排名为7，
由于排名7大于位置0，
所以将它与位置7上的数"2"交换。
数组现在变为：
{ 2， 5， 2， 4， 1， 3，0，4， 2，0 }
第2步： 排位置0上的数"2"， 有3个比它小得数， 它的排名为3，
由于排名3大于位置0，
所以将它与位置3上的数"4"交换。
数组现在变为：
{ 4， 5， 2， 2， 1， 3，0，4， 2，0 }
第3步： 排位置0上的数"4"， 有7个比它小得数， 它的排名为7，
由于排名7大于位置0，
所以将它与位置7上的数"4"交换。
由于将要交换的两个数相等，
所以延后一个位置，将它与位置8上的数"2"交换，
数组现在变为：
{ 2， 5， 2， 2， 1， 3，0，4， 4，0 }
第4步： 排位置0上的数"2"， 有3个比它小得数， 它的排名为3，
由于排名3大于位置0，
所以将它与位置3上的数"2"交换。
由于将要交换的两个数相等，
所以延后一个位置，将它与位置4上的数"1"交换
数组现在变为：
{ 1， 5， 2， 2， 2， 3，0，4， 4，0 }
第5步： 排位置0上的数"1"， 有2个比它小得数， 它的排名为2，
由于排名2大于位置0，
所以将它与位置2上的数"2"交换。
数组现在变为：
{ 2， 5， 1， 2， 2， 3，0，4， 4，0 }
第6步： 排位置0上的数"2"， 有3个比它小得数， 它的排名为3，
由于排名3大于位置0，
所以将它与位置3上的数"2"交换。
由于将要交换的两个数相等，
所以延后一个位置，将它与位置4上的数"2"交换
由于将要交换的两个数相等，
所以延后一个位置，将它与位置5上的数"3"交换
数组现在变为：
{ 3， 5， 1， 2， 2， 2，0，4， 4，0 }
第7步： 排位置0上的数"3"， 有6个比它小得数， 它的排名为6，
由于排名6大于位置0，
所以将它与位置6上的数"0"交换。
数组现在变为：
{ 0， 5， 1， 2， 2， 2，3，4， 4，0 }
第8步： 排位置0上的数"0"， 有0个比它小得数， 它的排名为0，
由于排名0不大于位置0，
所以不进行交换，开始排下一个位置上的数。
数组现在变为：
{ 0，5，1， 2， 2， 2，3，4，4，0 }
第9步： 排位置1上的数"5"， 有9个比它小得数， 它的排名为9，
由于排名9大于位置1，
所以将它与位置9上的数"0"交换。
数组现在变为：
{ 0， 0， 1， 2， 2， 2，3，4， 4，5 }
第10步：已进行了9次排序，排序的次数正好比数组的长度小1，排序结束。
-------------------------------------------------------------------------------------
可以看出，此排序法的空间效率和时间效率都与冒泡排序法相当，而且此排序法也具有一定的智能。对于排列非常混乱的数组，此排序法要进行很多数据比较和数据交换，比较费时。但当待排序数组基本有序时，此排序法只进行数据比较，而数据交换操作则很少，时间效率将大幅提高。
同时，此排序法的原理非常独特有趣，并且富含中国古老文化的精髓和神韵。在排序时它几乎很少沿着待排序数组的数据队列前行，而是守着数据队列的头部，犹如姜太公稳坐钓鱼台，将队列里站错位置的乱臣贼子逐个擒过来、推出去，吐故纳新、收放自如，象极太极推手，又象中国的舞龙，不经意间，一列混乱的数据已成清一色一条龙。而且此排序法在运作时，可以将数组里所有放错位置的数据自动分组，一次清理完一组才继续前行，又恰似西游记里的三藏师徒，刚踏上西行路就遇到老妖怪，于是师徒几人便停下来降妖捉魔，直到将这老妖怪及其洞中所有的小妖全部剿灭，才继续西行，而没走几步，又遇到一股妖魔鬼怪，于是又停下来与妖怪大战一番......
可见，在排序原理上张仰彪第二排序法极为独特，与现有的任何一种排序法都不相似，它应当是一种全新而有效的排序法，信不信由你。
至于为什么此排序法具有将数组里放错位置的数据自动分组、按组排序的功能，老纳作了如下分析：
首先，在任何一个待排序数组里，所有放错位置的数据都可以按照它们之间的内在关系而被分成很多小组，小组有大有小，但任何一个小组都不能再被分成更小的组。
例如：有100个人按年龄（有同龄的）顺序坐成一排照相，若其中只有两个人发现自己坐错了位置，这两个人必然相互坐到了对方的位子上，只要两人对调即可，与别人无关。如果只有三个人甲、乙、丙发现自己坐错了位子，那么这三个人必然是相互轮错，例如甲坐到了乙的位子上，乙坐到了丙的位子上，丙坐到了甲的位子上，此三个人构成了一个错位三角，也可以说构成了一个错位环。如果有四个以上的人发现自己坐错了位置，情况就变得比较复杂，此时所有坐错位置的人将被分成一个个小组，每个小组里的人都是相互间轮流坐错了位子，与组外的人无关，整个小组构成一个封闭的错位环，此环不可再分，这个错位环就是前边所说的某些错位数据之间的内在关系，也是将数组内所有错位数据分组处理的唯一依据。
既然待排序数组内的错位数据具有可以分组的特点，那么本排序法在排序时每遇到一个错位数据其实就是遇到了一组错位数据。所以将一个数据放到正确的位置上后交换过来的一定仍是一个错位数据，于是再将它放到正确的位置上，而交换过来的可能又是一个错位数据，只有将这一组错位数据全部清理到正确的位置上，排序位置才继续前移，直到又遇到另一组错位数据 ......。而此过程中无论怎样交换数据都不会移动原本就在正确位置上的数据，也不会移动刚刚排好位置的数据，这一点至关重要。
而整个排序过程中排序位置究竟可以从数组头部前移多远，取决于待排序数组里原来有几个没有错位的数据。
----------------------------------------------------------------------------------------
这就是张仰彪第二排序法，爱咋咋地。
编自己的程，下自己的蛋，让别人说去吧。