每个排序算法中有多少交换和比较？

Question

class Sort
{
    int[] arr;
    int counter=0;
    //Constructor
    public Sort()
    {
        arr = new int[10000];
    }
    string address;
    public void SwitchCase(int Case)
    {
            switch (Case)
            {
                case 1:
                    address = @"C:UsersAqib SaeedDesktopcase1.txt";
                    break;
                case 2:
                    address = @"C:UsersAqib SaeedDesktopcase2.txt";
                    break;
                case 3:
                    address = @"C:UsersAqib SaeedDesktopcase3.txt";
                    break;
                default:
                    break;
            }
    }
    //Read file for input
    public void FillArray()
    {
        using (StreamReader rdr = new StreamReader(address))
        {  
            for (int i = 0; i < arr.Length; i++)
            {
                arr[i] = Convert.ToInt32(rdr.ReadLine());
            }
        }
    }

    // Insertion Sort
    public void InsertionSort()
    {
        int insert;
        for (int i = 1; i < arr.Length; i++)
        {
            insert = arr[i];
            int moveItem = i;
            while (moveItem > 0 && arr[moveItem - 1] > insert)
            {
                arr[moveItem] = arr[moveItem - 1];
                moveItem--;
                counter++;
            }
            arr[moveItem] = insert;
        }
    }
    public void Counter()
    {
        Console.WriteLine(counter);
    }
    //Bubble Sorting
    public void BubbleSort()
    {
        int temp;
        for (int i = 0; i < arr.Length; i++)
        {
            for (int j = 0; j < arr.Length - 1 - i; j++)
            {
                if (arr[j] > arr[j + 1])
                {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    counter++;
                }
            }
        }
    }
    //Selection Sorting
    public void SelectionSort()
    {
        int min, temp;
        for (int i = 0; i < arr.Length; i++)
        {
            min = i;
            for (int j = i + 1; j < arr.Length; j++)
            if (arr[j] < arr[min])
            min = j;
            temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
            counter++;
        }
    }
    // Write Output to file
    public void Writer()
    {
        using (StreamWriter wrtr = new StreamWriter(@"C:UsersAqibSaeedDesktopSortedOutput.txt"))
        {
            for (int i = 0; i < arr.Length; i++)
            {
                wrtr.WriteLine(arr[i]);
            }
        }
    }
}
static void Main(string[] args)
    {
        Sort srt = new Sort();
        Console.WriteLine("Enter Case 1 OR 2 OR 3");

        srt.SwitchCase(Convert.ToInt32(Console.ReadLine()));
        srt.FillArray();
        srt.BubbleSort();
        srt.Writer();
        Console.WriteLine("Sorted Output File Is Ready");
        srt.Counter();
        Console.ReadLine();
    }

我实现了Sort类来对整数排序，并放置了int计数器来确定交换和比较的次数。但我不确定它是否工作正确!还有其他方法来确定交换和比较的次数吗?

Answer 1

可以创建一个实现IComparable的类来计算比较器访问次数，还可以创建一个专门的集合来计算交换次数。像这样，你不必计算排序算法内部的访问次数，你可以更严格地将任务委托给代码部分。

在索引操作符中计算交换操作，在IComparable实现中计算比较操作

实现IComparable:

的SortItem类示例

public class SortItem<T> : IComparable<T> where T : IComparable
{
    private static int _ComparisonCount = 0;
    public static int ComparisonCount
    {
        private set
        {
            _ComparisonCount = value;
        }
        get
        {
            return _ComparisonCount;
        }
    }
    public T Value
    {
        get;
        set;
    }
    public static void ResetComparisonCount()
    {
        _ComparisonCount = 0;
    }
    #region IComparable<T> Members
    public int CompareTo(T other)
    {
        ComparisonCount++;
        return this.Value.CompareTo(other);
    }
    #endregion
}

和排序集合:

public class SortCollection<T> : IList<SortItem<T>>
{
    public SortCollection(IList<T> sortList)
    {
        InnerList = sortList;
    }
    private IList<T> InnerList = null;
    public T this[int key] 
    { 
        get 
        {
            return InnerList[key]; 
        } 
        set 
        {
            SwapCount++;
            InnerList[key] = value; 
        } 
    }
    private int _SwapCount = 0;
    public int SwapCount
    {
        private set
        {
            _SwapCount = value;
        }
        get
        {
            return _SwapCount;
        }
    }
    public void ResetSwapCount()
    {
        _SwapCount = 0;
    }

}

这里执行:

List<Int32> baseList = new List<int>(new Int32 {6, 2, 7, 3, 1, 6, 7 });
SortCollection<Int32> sortList = new SortCollection<int>(baseList);
//do the sorting....
Console.WriteLine("Swaps: " + sortList.SwapCount.ToString());
Console.WriteLine("Comparisons: " + SortItem<Int32>.ComparisonCount.ToString());
SortItem<Int32>.ResetComparisonCount();
sortList.ResetSwapCount();

Answer 2

您只计算交换而不计算比较。如果你想计数比较，那么你需要添加一个额外的计数器，每次你传递一个if比较时递增。