简单选择排序不会排序

Question

我是算法新手，我试着写了一个选择排序。在 Internet 的一些帮助下，我有一个应该工作的脚本，但没有。 sort 方法后的结果是一个仍未排序的列表。

我不确定我是否遗漏了什么，我的代码看起来和网上的一样。

Product.cs

public class Product
{
    public string Name { get; set; }
    public double Price { get; set; }
}

Order.cs

    public class Order
    {
        public List<Product> listOfProducts = new List<Product>(){
            new Product(){ Name="Item1", Price=2.55 },
            new Product(){ Name="Item2", Price=1.92 },
            new Product(){ Name="Item3", Price=2.12 }
        };

        public List<Product> GetAllProducts(){

            return this.listOfProducts;

        }

    
        public void SortProductsByPrice(){
                int min = 0;
                for (int i = 0; i < this.listOfProducts.Count - 1; i++)
                {
                    min = i;
                    for (int j = 0; j < this.listOfProducts.Count; j++)
                    {
                        if (listOfProducts[j].Price < listOfProducts[min].Price)
                        {
                            min = j;
                        }
                    }
    
                    Product temporary = listOfProducts[min];
                    listOfProducts[min] = listOfProducts[i];
                    listOfProducts[i] = temporary;
                }
        }
    
    }

Program.cs

static void Main(string[] args)
        {
            Order order = new Order();

            // unsorted list
            foreach (Product pro in order.GetAllProducts())
            {
                Console.WriteLine(pro.Price);
            }
            Console.WriteLine("------------------------------------------");
            order.SortProductsByPrice();

            // sorted list
            foreach (Product pro in order.GetAllProducts())
            {
                Console.WriteLine(pro.Price);
            }
            Console.ReadLine();
        }

Answer 1

您的代码中的问题出在嵌套循环中。

如果您仔细查看 algorithm，您会发现：

Selection sort is a simple sorting algorithm. This sorting algorithm is an in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Initially, the sorted part is empty and the unsorted part is the entire list.

您 re-comparing 您的价值观与您已经排序的内容相同，您不应该这样做。你没有得到一个排序列表，因为在你的代码结束时，值被一遍又一遍地交换，直到它们回到原来的顺序。一个简单的解决方法是像这样更改嵌套的 for 循环：

public void SortProductsByPrice()
{
    int min = 0;
    for (int i = 0; i < this.listOfProducts.Count - 1; i++)
    {
        min = i;
        for (int j = i + 1; j < this.listOfProducts.Count; j++)
        {
            if (listOfProducts[j].Price < listOfProducts[min].Price)
            {
                min = j;
            }
        }

        Product temporary = listOfProducts[min];
        listOfProducts[min] = listOfProducts[i];
        listOfProducts[i] = temporary;
    }
}

准确地说，我们只更改了 1 行：

for (int j = i + 1; j < this.listOfProducts.Count; j++)  
             ^^^^^

如果你再看一下上面 link 中的 pseudo-code，你会发现这个函数现在类似于它：

procedure selection sort 
    list  : array of items
    n     : size of list

    for i = 1 to n - 1
        /* set current element as minimum*/
        min = i    
  
        /* check the element to be minimum */

        for j = i+1 to n 
            if list[j] < list[min] then
                min = j;
            end if
        end for

      /* swap the minimum element with the current element*/
        if indexMin != i  then
            swap list[min] and list[i]
        end if
    end for
    
end procedure

简单选择排序不会排序

Simple Selection Sort won't sort

c#

sorting

algorithm