一 快速排序
快速排序是我们平常最常使用的一种排序算法,因为它速度快,效率高,是最优秀的一种排序算法.
它的平均时间复杂度为:O(nlgn)
原理:
快速排序采用的是一种分治的思想,它先找一个基准数,然后将比这个基准数小的数字都放到它的左边,然后再递归调用,分别对左右两边快速排序,直到每一边只有一个数字.整个排序就完成了.
OC实现:
-(void)quickSort:(NSMutableArray *)list startIndex:(NSInteger )startIndex endIndex:(NSInteger)endIndex
{
if (list==nil||startIndex>=endIndex) {
return;
}
NSInteger tempIndex=startIndex;
NSNumber *tempNumber=list[startIndex];
for (NSInteger i=startIndex+1; i<=endIndex; i++) {
if ([tempNumber integerValue]>[list[i] integerValue]) {
tempIndex++;
[list exchangeObjectAtIndex:tempIndex withObjectAtIndex:i];
}
}
[list exchangeObjectAtIndex:startIndex withObjectAtIndex:tempIndex];
[self quickSort:list startIndex:startIndex endIndex:tempIndex-1];
[self quickSort:list startIndex:tempIndex+1 endIndex:endIndex];
}
二 冒泡排序
冒泡排序在我们实际开发中,使用的还是比较少的.它更加适合数据规模比较少的时候,因为它的效率是比较低的,但是优点是逻辑简单,容易让我们记得.
原理:
冒泡排序其实就是逐一比较交换,进行里外两次循环,外层循环为遍历所有数字,逐个确定每个位置,里层循环为确定了位置后,遍历所有后面没有确定位置的数字,与该位置的数字进行比较,只要比该位置的数字小,就和该位置的数字进行交换.
OC实现:
-(void)bubbleSort:(NSMutableArray *)list
{
for (int i=0; i<list.count; i++) {
for (int j=i+1; j<list.count; j++) {
if ([list[i] integerValue]>[list[j] integerValue]) {
[list exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
}
}
三 直接插入排序
直接插入排序的平均时间复杂度是:O(n^2)
原理:
直接插入排序是将从第二个数字开始,逐个拿出来,插入到之前排好序的数列里.
如图:
直接插入排序
OC实现:
-(void)insertSort:(NSMutableArray *)list
{
for (int i=1; i<list.count; i++) {
NSInteger value=[list[i] integerValue];
NSInteger j=i-1;
while (j>=0&&value<[list[j] integerValue]) {
j--;
}
[list removeObjectAtIndex:i];
[list insertObject:@(value) atIndex:j+1];
}
}
四 直接选择排序
直接选择排序的平均时间复杂度是:O(n^2),和冒泡排序一样,逻辑简单,但是效率不高,适合少量的数据排序
原理:
直接选择排序是从第一个位置开始遍历位置,找到剩余未排序的数据里最小的,找到最小的后,再做交换
OC实现:
-(void)selectSort:(NSMutableArray *)list
{
for (int i=0; i<list.count; i++) {
int k=i;
for (int j=i+1; j<list.count; j++) {
if ([list[j] integerValue]<[list[k] integerValue]) {
k = j;
}
}
[list exchangeObjectAtIndex:i withObjectAtIndex:k];
}
}
与冒泡排序的区别:
冒泡排序法是两两依次比较，并做交换，交换的次数多。
选择排序法是每次循环找出最值，循环结束后将最值调整到合适位置，交换的次数少。
剩余常见排序算法:
归并排序,希尔排序,堆排序,基数排序,桶排序.
