张仰彪第二排序法.docVIP

? ? ? ? ? ? ? ? ? ? 张仰彪第二排序法? ? ? 张仰彪第二排序法的原理与目前非常流行的反恐类网络游戏有些类似，它将待排序数组内放错位置的数据视为隐藏在节日游行队列里故意站错位置的恐怖分子，并自 动地将这些恐怖分子按照它们相互之间的内在关系而分成几个不同的小组。排序时反恐队员首先从游行队列的最前头开始清查，若遇到的人是好人，就快速通过去查 下一个。如果查到一个站错位置的恐怖分子，就停下来在这个位置上连续地排查运作，直到将这个恐怖分子及其所在小组的全部成员都清理到正确的位置上，然后才 继续前行去查下一个位置。直到清查的次数比队列的长度小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，