iOS 开发常见排序算法及其优化
一 冒泡排序
冒泡排序：原理：冒泡顾名思义，就像气泡从水底冒出一样，它的排序方式是：研究了一下，它给人的感觉是像近视眼一样，它只能看见自己和紧挨着自己的下一个数字，所以它的排序方式也就是将比较元素和紧挨着自己的元素比较看是否交换位置，然后持续这个过程，比较的一直都是紧挨着的两个元素。下面看代码吧，再代码里面再详细解释。
冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端，故名。
由于冒泡排序简洁的特点，它通常被用来对于计算机程序设计入门的学生介绍算法的概念。
冒泡排序的复杂程度：n2 算法非常稳定
-(void)buddding{
NSMutableArray * titles =[NSMutableArray arrayWithObjects:@"23",@"67",@"9",@"10", nil];
for (int i = 0; i < titles.count; i++) {
for (int j = 0; j < titles.count - i - 1; j++) {
if ([titles[j] integerValue] > [titles[j+1] integerValue]) {
[titles exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
}
}
算法的优化： 我们判定上一次有没有进行排序 如果没有则说明已经排序完成
-(void)bubbling{
BOOL flag = NO; //记录是否存在交换
NSMutableArray * titles = [NSMutableArray arrayWithObjects:@"2",@"3",@"34",@"56",@"12",@"22", nil];
for (int i = 0; i < titles.count; i++) {
flag = NO ;
for (int j = 0; j < titles.count - i - 1; j++) {
if ([titles[j] integerValue] >[titles[j+1] integerValue]) {
flag = YES ;
[titles exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
if (flag == NO) {//退出排序
break ;
}
}
NSLog(@"--===%@",titles);
}
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)
- (void)selectionAscendingOrderSortWithArray:(NSMutableArray *)ascendingArr
{
for (int i = 0; i < ascendingArr.count; i ++) {
for (int j = i + 1; j < ascendingArr.count; j ++) {
if ([ascendingArr[i] integerValue] > [ascendingArr[j] integerValue]) {
int temp = [ascendingArr[i] intValue];
ascendingArr[i] = ascendingArr[j];
ascendingArr[j] = [NSNumber numberWithInt:temp];
} }}
NSLog(@"选择升序排序后结果：%@", ascendingArr);
}
3、快速排序：
实现思路：
1. 从数列中挑出一个元素，称为 "基准"（pivot），
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割之后，该基准是它的最后位置。这个称为分割（partition）操作。
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
快速排序是基于分治模式处理的，对一个典型子数组A[p...r]排序的分治过程为三个步骤：
1.分解：
A[p..r]被划分为俩个（可能空）的子数组A[p ..q-1]和A[q+1 ..r]，使得
A[p ..q-1] <= A[q] <= A[q+1 ..r]
2.解决：通过递归调用快速排序，对子数组A[p ..q-1]和A[q+1 ..r]排序。
3.合并。
递回的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递回下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
复杂度：
平均时间复杂度：O(n^2)
平均空间复杂度：O(nlogn) O(nlogn)~O(n^2)
#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 && tempValue <= [arr[right] integerValue]) {
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] = [NSNumber numberWithInteger:tempValue];
return left;
}
4、插入排序：
实现思路：
1. 从第一个元素开始，认为该元素已经是排好序的。
2. 取下一个元素，在已经排好序的元素序列中从后向前扫描。
3. 如果已经排好序的序列中元素大于新元素，则将该元素往右移动一个位置。
4. 重复步骤3，直到已排好序的元素小于或等于新元素。
5. 在当前位置插入新元素。
6. 重复步骤2。
#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);
}
五、归并排序：
把序列分成元素尽可能相等的两半。
把两半元素分别进行排序。
把两个有序表合并成一个。
#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;
}
