循环排序-yiteyi-C++库

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

null

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

cycle-sort

arr[]中的循环=4,3,2,1}

cyclc-sort2

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

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

说明：

 arr[] = {10, 5, 2, 3} index =  0   1   2   3cycle_start = 0 item = 10 = arr[0]Find position where we put the item  pos = cycle_starti=pos+1while(i<n)if (arr[i] < item)      pos++;We put 10 at arr[3] and change item to old value of arr[3].arr[] = {10, 5, 2, 10} item = 3 Again rotate rest cycle that start with index '0' Find position where we put the item = 3 we swap item with element at arr[1] now arr[] = {10, 3, 2, 10} item = 5Again rotate rest cycle that start with index '0' and item = 5 we swap item with element at arr[2].arr[] = {10, 3, 5, 10 } item = 2Again rotate rest cycle that start with index '0' and item = 2arr[] = {2, 3,  5, 10}  Above is one iteration for cycle_stat = 0.Repeat above steps for cycle_start = 1, 2, ..n-2

CPP

                         // C++ program to implement cycle sort                       
                         #include <iostream>                       
                         using                                     namespace                                     std;                       
           
                         // Function sort the array using Cycle sort                       
                         void                                     cycleSort(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 // count number of memory writes                       
                                                 int                                     writes = 0;                       
           
                                                 // traverse array elements and put it to on                       
                                                 // the right place                       
                                                 for                                     (                                     int                                     cycle_start = 0; cycle_start <= n - 2; cycle_start++) {                       
                                                 // initialize item as starting point                       
                                                 int                                     item = arr[cycle_start];                       
           
                                                 // Find position where we put the item. We basically                       
                                                 // count all smaller elements on right side of item.                       
                                                 int                                     pos = cycle_start;                       
                                                 for                                     (                                     int                                     i = cycle_start + 1; i < n; i++)                       
                                                 if                                     (arr[i] < item)                       
                                                 pos++;                       
           
                                                 // If item is already in correct position                       
                                                 if                                     (pos == cycle_start)                       
                                                 continue                                     ;                       
           
                                                 // ignore all duplicate  elements                       
                                                 while                                     (item == arr[pos])                       
                                                 pos += 1;                       
           
                                                 // put the item to it's right position                       
                                                 if                                     (pos != cycle_start) {                       
                                                 swap(item, arr[pos]);                       
                                                 writes++;                       
                                                 }                       
           
                                                 // Rotate rest of the cycle                       
                                                 while                                     (pos != cycle_start) {                       
                                                 pos = cycle_start;                       
           
                                                 // Find position where we put the element                       
                                                 for                                     (                                     int                                     i = cycle_start + 1; i < n; i++)                       
                                                 if                                     (arr[i] < item)                       
                                                 pos += 1;                       
           
                                                 // ignore all duplicate  elements                       
                                                 while                                     (item == arr[pos])                       
                                                 pos += 1;                       
           
                                                 // put the item to it's right position                       
                                                 if                                     (item != arr[pos]) {                       
                                                 swap(item, arr[pos]);                       
                                                 writes++;                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // Number of memory writes or swaps                       
                                                 // cout << writes << endl ;                       
                         }                       
           
                         // Driver program to test above function                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 1, 8, 3, 9, 10, 10, 2, 4 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 cycleSort(arr, n);                       
           
                                                 cout <<                                     "After sort : "                                     << endl;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 cout << arr[i] <<                                     " "                                     ;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to implement cycle sort                       
           
                         import                                     java.util.*;                       
                         import                                     java.lang.*;                       
           
                         class                                     GFG {                       
                                                 // Function sort the array using Cycle sort                       
                                                 public                                     static                                     void                                     cycleSort(                                     int                                     arr[],                                     int                                     n)                       
                                                 {                       
                                                 // count number of memory writes                       
                                                 int                                     writes =                                     0                                     ;                       
           
                                                 // traverse array elements and put it to on                       
                                                 // the right place                       
                                                 for                                     (                                     int                                     cycle_start =                                     0                                     ; cycle_start <= n -                                     2                                     ; cycle_start++) {                       
                                                 // initialize item as starting point                       
                                                 int                                     item = arr[cycle_start];                       
           
                                                 // Find position where we put the item. We basically                       
                                                 // count all smaller elements on right side of item.                       
                                                 int                                     pos = cycle_start;                       
                                                 for                                     (                                     int                                     i = cycle_start +                                     1                                     ; i < n; i++)                       
                                                 if                                     (arr[i] < item)                       
                                                 pos++;                       
           
                                                 // If item is already in correct position                       
                                                 if                                     (pos == cycle_start)                       
                                                 continue                                     ;                       
           
                                                 // ignore all duplicate elements                       
                                                 while                                     (item == arr[pos])                       
                                                 pos +=                                     1                                     ;                       
           
                                                 // put the item to it's right position                       
                                                 if                                     (pos != cycle_start) {                       
                                                 int                                     temp = item;                       
                                                 item = arr[pos];                       
                                                 arr[pos] = temp;                       
                                                 writes++;                       
                                                 }                       
           
                                                 // Rotate rest of the cycle                       
                                                 while                                     (pos != cycle_start) {                       
                                                 pos = cycle_start;                       
           
                                                 // Find position where we put the element                       
                                                 for                                     (                                     int                                     i = cycle_start +                                     1                                     ; i < n; i++)                       
                                                 if                                     (arr[i] < item)                       
                                                 pos +=                                     1                                     ;                       
           
                                                 // ignore all duplicate elements                       
                                                 while                                     (item == arr[pos])                       
                                                 pos +=                                     1                                     ;                       
           
                                                 // put the item to it's right position                       
                                                 if                                     (item != arr[pos]) {                       
                                                 int                                     temp = item;                       
                                                 item = arr[pos];                       
                                                 arr[pos] = temp;                       
                                                 writes++;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // Driver program to test above function                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     arr[] = {                                     1                                     ,                                     8                                     ,                                     3                                     ,                                     9                                     ,                                     10                                     ,                                     10                                     ,                                     2                                     ,                                     4                                     };                       
                                                 int                                     n = arr.length;                       
                                                 cycleSort(arr, n);                       
           
                                                 System.out.println(                                     "After sort : "                                     );                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 System.out.print(arr[i] +                                     " "                                     );                       
                                                 }                       
                         }                       
           
                         // Code Contributed by Mohit Gupta_OMG <(0_o)>                       

Python3

                         # Python program to implement 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)>                       

C#

                         // C# program to implement cycle sort                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                                                 // Function sort the array using Cycle sort                       
                                                 public                                     static                                     void                                     cycleSort(                                     int                                     [] arr,                                     int                                     n)                       
                                                 {                       
                                                 // count number of memory writes                       
                                                 int                                     writes = 0;                       
           
                                                 // traverse array elements and                       
                                                 // put it to on the right place                       
                                                 for                                     (                                     int                                     cycle_start = 0; cycle_start <= n - 2; cycle_start++)                       
                                                 {                       
                                                 // initialize item as starting point                       
                                                 int                                     item = arr[cycle_start];                       
           
                                                 // Find position where we put the item.                       
                                                 // We basically count all smaller elements                       
                                                 // on right side of item.                       
                                                 int                                     pos = cycle_start;                       
                                                 for                                     (                                     int                                     i = cycle_start + 1; i < n; i++)                       
                                                 if                                     (arr[i] < item)                       
                                                 pos++;                       
           
                                                 // If item is already in correct position                       
                                                 if                                     (pos == cycle_start)                       
                                                 continue                                     ;                       
           
                                                 // ignore all duplicate elements                       
                                                 while                                     (item == arr[pos])                       
                                                 pos += 1;                       
           
                                                 // put the item to it's right position                       
                                                 if                                     (pos != cycle_start) {                       
                                                 int                                     temp = item;                       
                                                 item = arr[pos];                       
                                                 arr[pos] = temp;                       
                                                 writes++;                       
                                                 }                       
           
                                                 // Rotate rest of the cycle                       
                                                 while                                     (pos != cycle_start) {                       
                                                 pos = cycle_start;                       
           
                                                 // Find position where we put the element                       
                                                 for                                     (                                     int                                     i = cycle_start + 1; i < n; i++)                       
                                                 if                                     (arr[i] < item)                       
                                                 pos += 1;                       
           
                                                 // ignore all duplicate elements                       
                                                 while                                     (item == arr[pos])                       
                                                 pos += 1;                       
           
                                                 // put the item to it's right position                       
                                                 if                                     (item != arr[pos]) {                       
                                                 int                                     temp = item;                       
                                                 item = arr[pos];                       
                                                 arr[pos] = temp;                       
                                                 writes++;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // Driver program to test above function                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     [] arr = { 1, 8, 3, 9, 10, 10, 2, 4 };                       
                                                 int                                     n = arr.Length;                       
                                   
                                                 // Function calling                       
                                                 cycleSort(arr, n);                       
           
                                                 Console.Write(                                     "After sort : "                                     );                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 Console.Write(arr[i] +                                     " "                                     );                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Nitin Mittal                       

Javascript

                         <script>                       
                         // Javascript program to implement cycle sort                       
           
                                                 // Function sort the array using Cycle sort                       
                                                 function                                     cycleSort(arr, n)                       
                                                 {                       
                                   
                                                 // count number of memory writes                       
                                                 let writes = 0;                       
                                   
                                                 // traverse array elements and put it to on                       
                                                 // the right place                       
                                                 for                                     (let cycle_start = 0; cycle_start <= n - 2; cycle_start++)                       
                                                 {                       
                                   
                                                 // initialize item as starting point                       
                                                 let item = arr[cycle_start];                       
                                   
                                                 // Find position where we put the item. We basically                       
                                                 // count all smaller elements on right side of item.                       
                                                 let pos = cycle_start;                       
                                                 for                                     (let i = cycle_start + 1; i < n; i++)                       
                                                 if                                     (arr[i] < item)                       
                                                 pos++;                       
                                   
                                                 // If item is already in correct position                       
                                                 if                                     (pos == cycle_start)                       
                                                 continue                                     ;                       
                                   
                                                 // ignore all duplicate elements                       
                                                 while                                     (item == arr[pos])                       
                                                 pos += 1;                       
                                   
                                                 // put the item to it's right position                       
                                                 if                                     (pos != cycle_start)                       
                                                 {                       
                                                 let temp = item;                       
                                                 item = arr[pos];                       
                                                 arr[pos] = temp;                       
                                                 writes++;                       
                                                 }                       
                                   
                                                 // Rotate rest of the cycle                       
                                                 while                                     (pos != cycle_start)                       
                                                 {                       
                                                 pos = cycle_start;                       
                                   
                                                 // Find position where we put the element                       
                                                 for                                     (let i = cycle_start + 1; i < n; i++)                       
                                                 if                                     (arr[i] < item)                       
                                                 pos += 1;                       
                                   
                                                 // ignore all duplicate elements                       
                                                 while                                     (item == arr[pos])                       
                                                 pos += 1;                       
                                   
                                                 // put the item to it's right position                       
                                                 if                                     (item != arr[pos]) {                       
                                                 let temp = item;                       
                                                 item = arr[pos];                       
                                                 arr[pos] = temp;                       
                                                 writes++;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                         // Driver code                       
           
                                                 let arr = [ 1, 8, 3, 9, 10, 10, 2, 4 ];                       
                                                 let n = arr.length;                       
                                                 cycleSort(arr, n);                       
                                   
                                                 document.write(                                     "After sort : "                                     +                                     "<br/>"                                     );                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 document.write(arr[i] +                                     " "                                     );                       
                                   
                                                 // This code is contributed by susmitakundugoaldanga.                       
                         </script>                       

输出：

After sort : 1 2 3 4 8 9 10 10

时间复杂性 ：O（n） ^2. ) 最坏情况：O（n） ^2. ) 平均病例：O（n） ^2. ) 最佳案例：O（n） ^2. ) 这种排序算法最适合于内存写入或交换操作代价高昂的情况。

参考： https://en.wikipedia.org/wiki/Cycle_sort 本文由 尼桑·辛格 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用贡献极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章