圈排序

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

演算法

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