前些日子看到大佬写的排序算法温习，突然意识到自己早已经把这个抛到九霄云外了，所以，也想着来复习一下。
在开始记录排序算法之前，我们先来定义排序规则为从小到大排序，需要排序的数组如下：
NSMutableArray *numArr = [NSMutableArray arrayWithObjects:@(87),@(63.3),@(99.8),@(56),@(43.3), nil];
交换排序
1.冒泡排序
- 基本思想：
将数组中第一个值和第二个值进行比较，若第一个值大于第二个值，则两个值位置交换，然后第二个值和第三个值比较，同样，如果前面的值大于后面的值则位置交换，一直到第n-1个值和第n个值交换完毕，第一趟冒泡结束，将最大值移到了最后。以此类推，开始一趟趟冒泡，直至获取有序序列。
第1趟排序后：{ 63.3,87,56,43.3,99.8}
第2趟排序后：{ 63.3,56,43.3,87,99.8}
第3趟排序后：{ 56,43.3,63.3,87,99.8}
第4趟排序后：{ 43.3,56,63.3,87,99.8}
第5趟排序后：{ 43.3,56,63.3,87,99.8} - 复杂度：O(n^2)
- 代码实现：
#pragma mark - 冒泡排序
+ (void)bubbleSort:(NSMutableArray *)array
{
for (NSUInteger i = 0; i < array.count; i++)
{
for (NSUInteger j = 0; j < array.count-1-i; j++)
{
//相邻两个值进行比较
if ([array[j] floatValue] > [array[j+1] floatValue])
{
[array exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
NSLog(@"冒泡排序第%ld趟：%@",i+1,array);
}
}
2.快速排序
- 基本思想：
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，直至获取有序序列。
第一步以87为基准值，从数组尾部开始查找，找到第一个比基准值小的值43.3，此时数组是{43.3,63.3,99.8,56,43.3}，j=4；
第二步以43.3现在的位置往后找，找到第一个比基准大的值99.8，此时数组是{43.3,63.3,99.8,56,99.8}，i=2；
第三步，直至i>=j，把基准值放到正确的位置上；
以上三步可以理解成两步，第一步与第二步得到值后array[i]和array[j]互换即可。
最后以上述步骤进行左区间和右区间的快速排序。 - 复杂度：O(n^2)
- 代码实现：
#pragma mark - 快速排序
+ (void)quickSort:(NSMutableArray *)array leftIndex:(NSInteger)leftIndex rightIndex:(NSInteger)rightIndex
{
if (leftIndex >= rightIndex)
{
return ;
}
NSInteger i = leftIndex;
NSInteger j = rightIndex;
CGFloat standardValue = [array[i] floatValue];
while (i < j)
{
while (i < j && [array[j] floatValue] >= standardValue)
{
j--;
}
//如果比基准数小，则将查找到的小值调换到i的位置
array[i] = array[j];
while (i < j && [array[i] floatValue] <= standardValue)
{
i++;
}
//如果比基准数大，则将查找到的大值调换到j的位置
array[j] = array[i];
}
array[i] = [NSNumber numberWithFloat:standardValue];
//排序基准数左边的
[self quickSort:array leftIndex:leftIndex rightIndex:i-1];
//排序基准数右边的
[self quickSort:array leftIndex:i+1 rightIndex:rightIndex];
}
插入排序
1.直接插入排序
- 基本思想：
每步将一个待排序的记录，按其值的大小插入前面已经排序的数值的适当位置上，直到全部插入完为止。
第一步对前两个数进行排序，把63.3插入到87前面；
第二步对前三个数进行排序，99.8插在87之后；
以此类推...
第1趟排序后：{63.3,87,99.8,56,43.3}
第2趟排序后：{63.3,87,99.8,56,43.3}
第3趟排序后：{56,63.3,87,99.8,43.3}
第4趟排序后：{43.3,56,63.3,87,99.8} - 复杂度：O(n^2)
- 代码实现：
#pragma mark - 直接插入排序
+ (void)insertSort:(NSMutableArray *)array
{
NSInteger j;
for (NSInteger i = 1; i < array.count; i++)
{
CGFloat tempValue = [array[i] floatValue];
for (j = i-1; j >= 0 && [array[j] floatValue] > tempValue; j--)
{
[array exchangeObjectAtIndex:j+1 withObjectAtIndex:j];
}
[array replaceObjectAtIndex:j+1 withObject:[NSNumber numberWithFloat:tempValue]];
NSLog(@"直接插入第%ld趟：%@",i,array);
}
}
2.二分(折半)插入排序
- 基本思想：
折半插入排序是对插入排序算法的一种改进，排序算法过程，就是不断的依次将元素插入前面已排好序的序列中。 - 复杂度：O(n^2)
- 代码实现：
#pragma mark - 二分(折半)插入排序
+ (void)halfInsertSort:(NSMutableArray *)array
{
for (NSInteger i = 1 ; i < array.count ; i++)
{
CGFloat tempValue = [[array objectAtIndex:i] floatValue];
NSInteger left = 0;
NSInteger right = i - 1;
while (left <= right)
{
CGFloat middle = (left + right) / 2;
if(tempValue < [[array objectAtIndex:middle] floatValue])
{
right = middle - 1;
}
else
{
left = middle + 1;
}
}
for(NSInteger j = i ; j > left; j--)
{
[array replaceObjectAtIndex:j withObject:[array objectAtIndex:j - 1]];
}
[array replaceObjectAtIndex:left withObject:[NSNumber numberWithFloat:tempValue]];
NSLog(@"折半插入第%ld趟：%@",i,array);
}
}
选择排序
1.直接选择排序
- 基本思想：
在第i次选择操作中，通过n-i次值比较，从n-i+1个记录中选出最小的记录，并和第i(1<=i<=n-1)个记录交换。
第一步，依次从5个记录中选出最小记录，并和第1个记录交换;
第二步，从剩余4个记录中选出最小记录，并和第2个记录交换;
以此类推...
第1趟排序后：{43.3,63.3,99.8, 56,87}
第2趟排序后：{43.3,56,99.8, 63.3,87}
第3趟排序后：{43.3,56,63.3,99.8,87}
第4趟排序后：{43.3,56,63.3,87,99.8}
第5趟排序后：{43.3,56,63.3,87,99.8} - 复杂度：O(n^2)
- 代码实现：
#pragma mark - 直接选择排序
+ (void)selectSort:(NSMutableArray *)array
{
for (NSInteger i = 0; i < array.count; i++)
{
NSInteger minIndex = i;
for (NSInteger j = i+1; j < array.count; j++)
{
if ([array[j] floatValue] < [array[minIndex] floatValue])
{
minIndex = j;
}
}
if (minIndex != i)
{
[array exchangeObjectAtIndex:i withObjectAtIndex:minIndex];
}
NSLog(@"直接选择第%ld趟：%@",i+1,array);
}
}
