圈排序

圈排序是一種比較排序演算法，它強制將陣列分解為圈數，其中每個圈可以旋轉以生成排序陣列。 理論上它在理論上是最優的，它減少了對原始陣列的寫入次數。

演算法

考慮一組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