循环排序的Python程序-yiteyi-C++库

循环排序是一种就地排序算法，不稳定排序算法，这是一种比较排序，从理论上讲，对原始数组的写入总数来说是最佳的。

null

就内存写入的数量而言，它是最佳的。信息技术最小化内存写入的次数排序（每个值要么被写入零次，如果它已经在正确的位置，要么被写入一次到正确的位置。）
它基于这样一种思想：要排序的数组可以划分为多个循环。循环可以可视化为一个图形。如果排序数组中第i个索引处的元素必须存在于第j个索引处，则有n个节点和一条从节点i指向节点j的边。 arr[]中的循环={4,5,2,1,5}
arr[]中的循环=4,3,2,1}

我们一个一个地考虑所有的循环。我们首先考虑包含第一元素的周期。我们找到第一个元素的正确位置，将其放置在其正确的位置，如J。我们考虑ARR [j]的旧值并找到其正确的位置，我们一直这样做直到当前循环的所有元素都放置在正确的位置，即，我们不返回循环起点。

Python3

                         # Python program to impleament cycle sort                       
                                   
                         def                                     cycleSort(array):                       
                                                 writes                                     =                                     0                       
                                   
                                                 # Loop through the array to find cycles to rotate.                       
                                                 for                                     cycleStart                                     in                                     range                                     (                                     0                                     ,                                     len                                     (array)                                     -                                     1                                     ):                       
                                                 item                                     =                                     array[cycleStart]                       
                                   
                                                 # Find where to put the item.                       
                                                 pos                                     =                                     cycleStart                       
                                                 for                                     i                                     in                                     range                                     (cycleStart                                     +                                     1                                     ,                                     len                                     (array)):                       
                                                 if                                     array[i] < item:                       
                                                 pos                                     +                                     =                                     1                       
                                   
                                                 # If the item is already there, this is not a cycle.                       
                                                 if                                     pos                                     =                                     =                                     cycleStart:                       
                                                 continue                       
                                   
                                                 # Otherwise, put the item there or right after any duplicates.                       
                                                 while                                     item                                     =                                     =                                     array[pos]:                       
                                                 pos                                     +                                     =                                     1                       
                                                 array[pos], item                                     =                                     item, array[pos]                       
                                                 writes                                     +                                     =                                     1                       
                                   
                                                 # Rotate the rest of the cycle.                       
                                                 while                                     pos !                                     =                                     cycleStart:                       
                                   
                                                 # Find where to put the item.                       
                                                 pos                                     =                                     cycleStart                       
                                                 for                                     i                                     in                                     range                                     (cycleStart                                     +                                     1                                     ,                                     len                                     (array)):                       
                                                 if                                     array[i] < item:                       
                                                 pos                                     +                                     =                                     1                       
                                   
                                                 # Put the item there or right after any duplicates.                       
                                                 while                                     item                                     =                                     =                                     array[pos]:                       
                                                 pos                                     +                                     =                                     1                       
                                                 array[pos], item                                     =                                     item, array[pos]                       
                                                 writes                                     +                                     =                                     1                       
                                   
                                                 return                                     writes                       
                                   
                         #  driver code                       
                         arr                                     =                                     [                                     1                                     ,                                     8                                     ,                                     3                                     ,                                     9                                     ,                                     10                                     ,                                     10                                     ,                                     2                                     ,                                     4                                     ]                       
                         n                                     =                                     len                                     (arr)                       
                         cycleSort(arr)                       
                                   
                         print                                     (                                     "After sort : "                                     )                       
                         for                                     i                                     in                                     range                                     (                                     0                                     , n) :                       
                                                 print                                     (arr[i], end                                     =                                                             ' '                                     )                       
                                   
                         # Code Contributed by Mohit Gupta_OMG <(0_o)>                       

输出：

After sort : 
1 2 3 4 8 9 10 10

请参阅完整的文章循环排序更多细节！

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章