这是一种什么样的排序方法，该方法的算法复杂度是多少

我看到了下面实现排序数组的代码。

我已经应用于一个非常长的阵列，它能够在不到一秒的时间内做到这一点，可能是20毫秒或更短。

我一直在阅读关于算法复杂性和大O符号的文章，我想知道：

这是在这段代码中实现的(现有的)排序方法
这里使用的算法的复杂性是多少
如果你要改进下面的算法/代码，你会改变什么

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 + " "); 
} 
}
}

这是选择排序。它的时间复杂度是O(²)。它在i和j上有嵌套循环，您可以看到这些循环生成范围{0，…，-1}内的每一个可能的两个索引集，其中是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; 
}
}

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

这是"冒泡排序"具有O(n^2)。您可以使用"；合并排序"；或"；"快速排序"；以将您的算法改进为O(n*log(n))。如果你总是知道你的数字的最小值和最大值，你可以使用"；数字排序"；或"；Radix Sort"；具有O(n)

参见：c#中的排序算法

相关内容

最新更新

热门标签：