圈排序

圈排序是一种比较排序算法，它强制将数组分解为圈数，其中每个圈可以旋转以生成排序数组。 理论上它在理论上是最优的，它减少了对原始数组的写入次数。

算法

考虑一组n个不同的元素。 给出元素a，可以通过计算小于a的元素的数量来计算a的索引。

• 如果找到元素处于正确的位置，只需保持原样。
• 否则，通过计算小于a的元素总数来找到a的正确位置。 它必须出现在排序数组中。 被替换的另一个元素b将被移动到其正确的位置。 这个过程一直持续到在a的原始位置得到一个元素。

所示过程构成一个循环圈，为列表的每个元素重复此循环。 结果列表将被排序。

使用C语言实现圈排序的示例代码如下所示 -

#include<stdio.h>  
void sort(int a[], int n)  
{  
    int writes = 0,start,element,pos,temp,i;  

    for (start = 0; start <= n - 2; start++) {  
        element = a[start];  
        pos = start;  
        for (i = start + 1; i < n; i++)  
            if (a[i] < element)  
                pos++;  
        if (pos == start)  
            continue;  
        while (element == a[pos])  
            pos += 1;  
        if (pos != start) {  
            //swap(element, a[pos]);  
        temp = element;  
        element = a[pos];  
            a[pos] = temp;    
            writes++;  
        }  
        while (pos != start) {  
            pos = start;  
            for (i = start + 1; i < n; i++)  
                if (a[i] < element)  
                    pos += 1;  
            while (element == a[pos])  
                pos += 1;  
            if (element != a[pos]) {  
              temp = element;  
          element = a[pos];  
              a[pos] = temp;    
                writes++;  
            }  
        }  
    }  

 }  

int main()  
{  
    int a[] = {1, 9, 2, 4, 2, 10, 45, 3, 2};  
    int n = sizeof(a) / sizeof(a[0]),i;  
    sort(a, n);  
    printf("After sort, array : ");  
    for (i = 0; i < n; i++)  
        printf("%d  ",a[i]);  
    return 0;  
}

执行上面示例代码，得到以下结果：

After sort, array :
1
2
2
2
3
4
9
10
45

使用Java语言实现圈排序的示例代码如下所示 -

public class CycleSort   
{  
    static void sort(int a[], int n)  
    {  
        int writes = 0,start,element,pos,temp,i;  

        for (start = 0; start <= n - 2; start++) {  
            element = a[start];  
            pos = start;  
            for (i = start + 1; i < n; i++)  
                if (a[i] < element)  
                    pos++;  
            if (pos == start)  
                continue;  
            while (element == a[pos])  
                pos += 1;  
            if (pos != start) {  
                //swap(element, a[pos]);  
            temp = element;  
            element = a[pos];  
                a[pos] = temp;    
                writes++;  
            }  
            while (pos != start) {  
                pos = start;  
                for (i = start + 1; i < n; i++)  
                    if (a[i] < element)  
                        pos += 1;  
                while (element == a[pos])  
                    pos += 1;  
                if (element != a[pos]) {  
                  temp = element;  
              element = a[pos];  
                  a[pos] = temp;    
                    writes++;  
                }  
            }  
        }  
    }  
    public static void main(String[] args)  
    {  
        int a[] = { 1, 9, 2, 4, 2, 10, 45, 3, 2 };  
        int n = a.length,i;  
        sort(a, n);  
        System.out.println("After sort, array : ");  
        for (i = 0; i < n; i++)  
            System.out.println(a[i]);  

    }  
}

执行上面示例代码，得到以下结果：

After sort, array :
1
2
2
2
3
4
9
10
45

使用C#语言实现圈排序的示例代码如下所示 -

using System;  
public class CycleSort   
{  
    static void sort(int[] a, int n)  
    {  
        int writes = 0,start,element,pos,temp,i;  

        for (start = 0; start <= n - 2; start++) {  
            element = a[start];  
            pos = start;  
            for (i = start + 1; i < n; i++)  
                if (a[i] < element)  
                    pos++;  
            if (pos == start)  
                continue;  
            while (element == a[pos])  
                pos += 1;  
            if (pos != start) {  
                //swap(element, a[pos]);  
            temp = element;  
            element = a[pos];  
                a[pos] = temp;    
                writes++;  
            }  
            while (pos != start) {  
                pos = start;  
                for (i = start + 1; i < n; i++)  
                    if (a[i] < element)  
                        pos += 1;  
                while (element == a[pos])  
                    pos += 1;  
                if (element != a[pos]) {  
                  temp = element;  
              element = a[pos];  
                  a[pos] = temp;    
                    writes++;  
                }  
            }  
        }  
    }  
    public void Main()  
    {  
        int[] a = { 1, 9, 2, 4, 2, 10, 45, 3, 2  };  
        int n = a.Length,i;  
        sort(a, n);  
        Console.WriteLine("After sort, array : ");  
        for (i = 0; i < n; i++)  
            Console.WriteLine(a[i]);  

    }  
}

执行上面示例代码，得到以下结果：

After sort, array :
1
2
2
2
3
4
9
10
45