时间戳

首页 > 解决方案 > 这是应用什么排序方法，该方法的算法复杂度是多少

c# - 这是应用什么排序方法，该方法的算法复杂度是多少

问题描述

我遇到了下面用于实现排序数组的代码。

我已经申请了一个非常长的阵列，它能够在一秒内完成，可能是 20 毫秒或更短。

我一直在阅读有关算法复杂性和大 O 表示法的信息，并想知道：

  1. 这是在此代码中实现的（现有的）排序方法。
  2. 这里使用的算法的复杂度是多少。
  3. 如果你要改进下面的算法/代码，你会改变什么。
using System;
using System.Text;
//This program sorts an array
public class SortArray
{
    static void Main(String []args)
    {
        // declaring and initializing the array 
        //int[] arr = new int[] {3,1,4,5,7,2,6,1, 9,11, 7, 2,5,8,4}; 
        
 int[] arr = new int[] {489,491,493,495,497,529,531,533,535,369,507,509,511,513,515,203,205,207,209,211,213,107,109,111,113,115,117,11913,415,417,419,421,423,425,427,15,17,19,21,4,517,519,521,523,525,527,4,39,441,443,445,447,449,451,453,455,457,459,461,537,539,541,543,545,547,1,3,5,7,9,11,13,463,465,467,23,399,401,403,405,407,409,411,499,501,503,505,333,335,337,339,341,343,345,347,65,67,69,71,73,75,77,79,81,83,85,87,89,91,93,95,9,171,173,175,177,179,181,183,185,187,269,271,273,275,277,279,281,283,25,27,29,31,33,35,37,39,41,43,45,47,49,51,53,55,57,59,61,63,133,135,137,139,141,143,145,285,287,289,291,121,123,125,127,129,131,297,299,373,375,377,379,381,383,385,387,389,97,99,101,103,105,147,149,151,153,155,157,159,161,163,165,167,16,391,393,395,397,399,401,403,189,191,193,195,197,199,201,247,249,251,253,255,257,259,261,263,265,267,343,345,347,349,501,503,505,333,335,337,339,341,417,419,421,423,425,561,563,565,567,569,571,573,587,589,591,593,595,597,599,427,429,431,433,301,303,305,307,309,311,313,315,317,319,321,323,325,327,329,331,371,359,361,363,365,367,369,507,509,511,513,515,351,353,355,57,517,519,521,523,525,527,413,415,405,407,409,411,499,435,437,469,471,473,475,477,479,481,483,485,487,545,547,549,551,553,555,575,577,579,581,583,585,557,559,489,491,493,495,497,529,531,533,535,537,539,541,543,215,217,219,221,223,225,227,229,231,233,235,237,239,241,243,245,293,295};
        
  
        int temp; 
          // traverse 0 to array length 
        for (int i = 0; i < arr.Length ; i++) 
        {
            // traverse i+1 to array length 
            //for (int j = i + 1; j < arr.Length; j++) 
            for (int j = i+1; j < arr.Length; j++) 
            {
                // compare array element with  
                // all next element 
                if (arr[i] > arr[j]) { 
                    ///Console.WriteLine(i+"i before"+arr[i]); 
                    temp = arr[i]; 
                    arr[i] = arr[j]; 
                    arr[j] = temp; 
                    //Console.WriteLine("i  After"+arr[i]); 
                }
            }
        }           
  
        // print all element of array 
        foreach(int value in arr) 
        { 
            Console.Write(value + " "); 
        } 

    }
}

标签： c#algorithmsorting

解决方案

这是选择排序。它的时间复杂度是 O(²)。i它在和上有嵌套循环j，您可以看到这些循环在 {0,...,-1} 范围内产生每个可能的两个索引集，其中 is arr.Length。对的数量是一个三角形数，并且等于：

(-1)/2

...这是 O(²)

如果我们坚持选择排序，我们仍然可以找到一些改进。

我们可以看到，外循环的作用是将arr[i]属于那里的值存储在最终排序的数组中，并且永远不会再触及该条目。它通过搜索从该索引开始的数组右侧部分的最小值来实现。

现在，在发生在内循环中的搜索期间，它不断将较小的值交换到arr[i]. 这可能会发生几次，因为它可能会j在向右走时找到更小的值。这是对操作的浪费，因为我们宁愿只执行一次交换。这是可能的：不是立即交换，而是延迟此操作。而是跟踪最小值所在的位置（最初位于i，但这可能会成为某个j索引）。只有当内部循环完成时，才执行交换。

有一个不太重要的改进：i不必等于arr.Length - 1，因为这样就没有内部循环的迭代。因此，外部循环的结束条件可以排除该迭代的发生。

看起来是这样的：

for (int i = 0, last = arr.Length - 1; i < last; i++) 
{
    int k = i; // index that has the least value in the range arr[i..n-1] so far
    for (int j = i+1; j < arr.Length; j++) 
    {
        if (arr[k] > arr[j]) { 
            k = j; // don't swap yet -- just track where the minimum is located
        }
    }
    if (k > i) { // now perform the swap
        int temp = arr[i];
        arr[i] = arr[k]; 
        arr[k] = temp; 
    }
}

进一步的改进可以是使用内部循环不仅可以定位最小值，还可以定位最大值，并将找到的最大值移动到数组的右端。这样，数组的两端逐渐排序，内部循环将缩短两倍。尽管如此，比较次数保持不变，平均掉期次数也保持不变。因此，收益仅在于迭代开销。

推荐阅读