一 快速排序

快速排序是我们平常最常使用的一种排序算法,因为它速度快,效率高,是最优秀的一种排序算法.
它的平均时间复杂度为:O(nlgn)

原理:

快速排序采用的是一种分治的思想,它先找一个基准数,然后将比这个基准数小的数字都放到它的左边,然后再递归调用,分别对左右两边快速排序,直到每一边只有一个数字.整个排序就完成了.

-(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];

}

二 冒泡排序

冒泡排序在我们实际开发中,使用的还是比较少的.它更加适合数据规模比较少的时候,因为它的效率是比较低的,但是优点是逻辑简单,容易让我们记得.

原理:

冒泡排序其实就是逐一比较交换,进行里外两次循环,外层循环为遍历所有数字,逐个确定每个位置,里层循环为确定了位置后,遍历所有后面没有确定位置的数字,与该位置的数字进行比较,只要比该位置的数字小,就和该位置的数字进行交换.

-(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)
(https://cxlhaha.github.io/2017/03/19/%E5%87%A0%E7##原理:
直接插入排序是将从第二个数字开始,逐个拿出来,插入到之前排好序的数列里.如图:

直接插入排序
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];
}
}

与冒泡排序的区别:
冒泡排序法是两两依次比较，并做交换，交换的次数多。选择排序法是每次循环找出最值，循环结束后将最值调整到合适位置，交换的次数少。
剩余常见排序算法:
归并排序,希尔排序,堆排序,基数排序,桶排序.