排序
1.冒泡排序
冒泡算法是一种基础的排序算法，这种算法会重复的比较数组中相邻的两个元素。如果一个元素比另一个元素大（小），那么就交换这两个元素的位置。重复这一比较直至最后一个元素。这一比较会重复n-1趟，每一趟比较n-j次，j是已经排序好的元素个数。每一趟比较都能找出未排序元素中最大或者最小的那个数字。这就如同水泡从水底逐个飘到水面一样。冒泡排序是一种时间复杂度较高，效率较低的排序方法。其空间复杂度是O(n)。
1, 最差时间复杂度 O(n^2)
2, 平均时间复杂度 O(n^2)
如图：
image
OC代码如下:
#pragma mark - 冒泡升序排序
- (void)bubbleAscendingOrderSortWithArray:(NSMutableArray *)array
{
for (int i = 0; i < array.count; i++)
{
for (int j = 0; j < array.count - 1 - i;j++)
{
if ([array[j+1]intValue] < [array[j] intValue])
{
NSString *temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
#pragma mark - 冒泡降序排序
- (void)bubbleDescendingSortWithArray:(NSMutableArray *)array
{
for (int i = 0; i<array.count; i++)
{
for (int j = 0; j<array.count-1-i; j++)
{
if ([array[j] integerValue]<[array[j+1] integerValue])
{
NSString *temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
2.选择排序
实现思路：
1. 设数组内存放了n个待排数字，数组下标从1开始，到n结束。
2. i=1
3. 从数组的第i个元素开始到第n个元素，寻找最小的元素。（具体过程为:先设arr[i]为最小，逐一比较，若遇到比之小的则交换）
4. 将上一步找到的最小元素和第i位元素交换。
5. 如果i=n－1算法结束，否则回到第3步
复杂度：
平均时间复杂度：O(n^2)
平均空间复杂度：O(1)
image
代码如下：
#pragma mark - 选择升序排序
- (NSMutableArray *)selectionAscendingOrderSortWithArray:(NSMutableArray *)array
{
for (int i = 0; i<array.count; i++)
{
for (int j = i+1; j<array.count; j++)
{
if ([array[i] integerValue]<[array[j] integerValue])
{
NSString *temp = array[j];
array[j] = array[i];
array[i] = temp;
}
}
}
return array;
}
#pragma mark - 选择降序排序
- (NSMutableArray *)selectionDescendingOrderSortWithArray:(NSMutableArray *)array
{
for (int i = 0; i<array.count; i++)
{
for (int j = i+1; j<array.count; j++)
{
if ([array[i] integerValue]>[array[j] integerValue])
{
NSString *temp = array[j];
array[j] = array[i];
array[i] = temp;
}
}
}
return array;
}
3.快速排序：
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序n个元素要O(nlogn)次比较。在最坏状况下则需要O(n^2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他O(nlogn)算法更快，因为它的内部循环可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治策略(Divide and Conquer)来把一个序列分为两个子序列。步骤为：
从序列中挑出一个元素，作为"基准"(pivot).
把所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准的后面（相同的数可以到任一边），这个称为分区(partition)操作。
对每个分区递归地进行步骤1~2，递归的结束条件是序列的大小是0或1，这时整体已经被排好序了。
如图：
image
代码如下：
#pragma mark - 快速升序排序
-(void)quickAscendingOrderSort:(NSMutableArray *)arr leftIndex:(NSInteger)left rightIndex:(NSInteger)right
{
if (left < right)
{
NSInteger temp = [self getMiddleIndex:arr leftIndex:left rightIndex:right];
[self quickAscendingOrderSort:arr leftIndex:left rightIndex:temp-1];
[self quickAscendingOrderSort:arr leftIndex:temp + 1 rightIndex:right];
}
NSLog(@"快速升序排序结果：%@", arr);
}
- (NSInteger)getMiddleIndex:(NSMutableArray *)arr leftIndex:(NSInteger)left rightIndex:(NSInteger)right
{
NSInteger tempValue = [arr[left] integerValue];
while (left<right)
{
while (left<right&&[arr[right] integerValue]>=tempValue)
{
right --;
}
if(left<right)
{
arr[left] = arr[right];
}
while (left<right&&[arr[left] integerValue]<=tempValue)
{
left ++;
}
if (left<right)
{
arr[right] = arr[left];
}
}
arr[left] = [NSString stringWithFormat:@"%ld",tempValue];
return left;
}
4.插入排序
实现思路：
1. 从第一个元素开始，认为该元素已经是排好序的。
2. 取下一个元素，在已经排好序的元素序列中从后向前扫描。
3. 如果已经排好序的序列中元素大于新元素，则将该元素往右移动一个位置。
4. 重复步骤3，直到已排好序的元素小于或等于新元素。
5. 在当前位置插入新元素。
6. 重复步骤2。
复杂度：
平均时间复杂度：O(n^2)
平均空间复杂度：O(1)
如图：
image
代码如下：
#pragma mark - 插入升序排序
- (void)insertionAscendingOrderSort:(NSMutableArray *)ascendingArr
{
for (NSInteger i = 1; i < ascendingArr.count; i ++) {
NSInteger temp = [ascendingArr[i] integerValue];
for (NSInteger j = i - 1; j >= 0 && temp < [ascendingArr[j] integerValue]; j --) {
ascendingArr[j + 1] = ascendingArr[j];
ascendingArr[j] = [NSNumber numberWithInteger:temp];
}
}
NSLog(@"插入升序排序结果：%@",ascendingArr);
}
5.归并排序
思路：
1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2.设定两个指针，最初位置分别为两个已经排序序列的起始位置
3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4.重复步骤3直到某一指针到达序列尾
5.将另一序列剩下的所有元素直接复制到合并序列尾
如图：
image
代码如下：
#pragma mark - 归并升序排序
- (void)megerSortAscendingOrderSort:(NSMutableArray *)ascendingArr
{
NSMutableArray *tempArray = [NSMutableArray arrayWithCapacity:1];
for (NSNumber *num in ascendingArr) {
NSMutableArray *subArray = [NSMutableArray array];
[subArray addObject:num];
[tempArray addObject:subArray];
}
while (tempArray.count != 1) {
NSInteger i = 0;
while (i < tempArray.count - 1) {
tempArray[i] = [self mergeArrayFirstList:tempArray[i] secondList:tempArray[i + 1]];
[tempArray removeObjectAtIndex:i + 1];
i++;
}
}
NSLog(@"归并升序排序结果：%@", ascendingArr);
}
- (NSArray *)mergeArrayFirstList:(NSArray *)array1 secondList:(NSArray *)array2 {
NSMutableArray *resultArray = [NSMutableArray array];
NSInteger firstIndex = 0, secondIndex = 0;
while (firstIndex < array1.count && secondIndex < array2.count) {
if ([array1[firstIndex] floatValue] < [array2[secondIndex] floatValue]) {
[resultArray addObject:array1[firstIndex]];
firstIndex++;
} else {
[resultArray addObject:array2[secondIndex]];
secondIndex++;
}
}
while (firstIndex < array1.count) {
[resultArray addObject:array1[firstIndex]];
firstIndex++;
}
while (secondIndex < array2.count) {
[resultArray addObject:array2[secondIndex]];
secondIndex++;
}
return resultArray.copy;
}
6.OC自带的数组排序
一般排序算法在开发总很少用到，因为OC已经有封装好接口。
NSArray *sortArray = [array sortedArrayUsingComparator:^NSComparisonResult(id _Nonnull obj1, id _Nonnull obj2) {
NSNumber *num1 = [NSNumber numberWithInteger:[obj1 integerValue]];
NSNumber *num2 = [NSNumber numberWithInteger:[obj2 integerValue]];
//升序
return [num1 compare:num2];
//降序
// return [num2 compare:num1] ;
}];
