Несмотря на цикл while
внутри for
, этот тип является линейным O(n)
.Если цикл while происходит несколько раз для данного i
, то для значений i
, которые соответствуют swapPoint
, цикл while не будет выполняться вообще.
Эта реализация будет работать только для массивов целых чиселтам, где нет дубликатов и значения последовательны от 0 до n-1, поэтому Quicksort все еще имеет значение O(n log n)
, потому что он работает с непоследовательными значениями.
Это можно легко проверить, выполнивнаихудший случай:
input = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
с последующим использованием следующего кода:
int whileCount = 0;
for (int i = 0; i < n; i++)
{
while (input[i] != i)
{
whileCount++;
// swap
int swapPoint = input[i];
input[i] = input[swapPoint];
input[swapPoint] = swapPoint;
}
Console.WriteLine("for: {0}, while: {1}", i, whileCount);
}
Вывод будет следующим:
for: 0, while: 9
for: 1, while: 9
for: 2, while: 9
for: 3, while: 9
for: 4, while: 9
for: 5, while: 9
for: 6, while: 9
for: 7, while: 9
for: 8, while: 9
for: 9, while: 9
, поэтому вы видите даже вв худшем случае, когда вы выполняете цикл while
n-1
раз в первой итерации цикла for
, вы все равно получаете только n-1
итераций цикла while для всего процесса.
Дополнительные примеры со случайными данными:
{7, 1, 2, 4, 3, 5, 0, 6, 8, 9} => 2 on i=0, 1 on i=3 and nothing more. (total 3 while loop runs)
{7, 8, 2, 1, 0, 3, 4, 5, 6, 9} => 7 on i=0 and nothing more (total 7 while loop runs)
{9, 8, 7, 4, 3, 1, 0, 2, 5, 6} => 2 on i=0, 2 on i=1, 1 on i=2, 1 on i=3 (total 6 while loop runs)