我正在研究我测试冒泡排序和插入排序和快速排序的课程,我对随机数进行了测试。结果表明,插入排序比冒泡排序快,而快速排序是最慢的排序。
所以我在时间方面有以下排名
- 插入排序(最快)
- 冒泡排序(第二分)
- 快速排序(最慢)
考虑到插入和冒泡排序的复杂度为 O(n2),而快速排序 O(n log n) 和 O(n log n) 应该更快!!!
有人可以与我分享解释吗?
谢谢
(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;
}