循环排序算法实现

循环排序是一种比较排序算法, 它强制将数组分解为循环数, 其中每个循环都可以旋转以生成排序数组。从理论上讲, 它是最佳的, 因为它减少了对原始数组的写入次数。

算法

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

1. 如果发现该元素在其正确位置, 则只需保留该元素原样。
2. 否则, 通过计算小于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