tipo de inserção vs algoritmo de ordenação de bolhas vs quicksort
Eu estou trabalhando em uma pesquisa na classe que eu testei tipo de classificação de bolha e inserção e tipo rápido, eu fiz o teste em números aleatórios. Os resultados mostram que a classificação por inserção é mais rápida do que a classificação por bolha e a classificação rápida é a mais lenta.
Então eu tenho o ranking abaixo em termos de tempo
tipo de inserção (o mais rápido)bubble sort (segunda pontuação)tipo rápido (o mais lento)Levando em consideração que a inserção e o bubble sort têm uma complexidade de O (n2) enquanto que a rápida ordenação O (n log n) e O (n log n) devem ser mais rápidas !!!
Alguém poderia compartilhar comigo explicações?
obrigado
(NSMutableArray *)quickSort:(NSMutableArray *)a
{
// Log the contents of the incoming array
NSLog(@"%@", a);
// Create two temporary storage lists
NSMutableArray *listOne = [[[NSMutableArray alloc]
initWithCapacity:[a count]] autorelease];
NSMutableArray *listTwo = [[[NSMutableArray alloc]
initWithCapacity:[a count]] autorelease];
int pivot = 4;
// Divide the incoming array at the pivot
for (int i = 0; i < [a count]; i++)
{
if ([[a objectAtIndex:i] intValue] < pivot)
{
[listOne addObject:[a objectAtIndex:i]];
}
else if ([[a objectAtIndex:i] intValue] > pivot)
{
[listTwo addObject:[a objectAtIndex:i]];
}
}
// Sort each of the lesser and greater lists using a bubble sort
listOne = [self bubbleSort:listOne];
listTwo = [self bubbleSort:listTwo];
// Merge pivot onto lesser list
listOne addObject:[[NSNumber alloc] initWithInt:pivot]];
// Merge greater list onto lesser list
for (int i = 0; i < [listTwo count]; i++)
{
[listOne addObject:[listTwo objectAtIndex:i]];
}
// Log the contents of the outgoing array
NSLog(@"%@", listOne);
// Return array
return listOne;
}