冒泡排序
基本思想：两两比较相邻的关键字，如果反序则交换，直到没有反序的记录为止
简单的冒泡排序如下：
NSMutableArray *ary1 = [NSMutableArray arrayWithArray:@[@2,@6,@1,@3,@4,@5,@9]];
for (int i = 0; i < [ary1 count] ; i++) {
for (int j = 0; j < [ary1 count] - i - 1; j++) {
if (ary1[j] > ary1[j+1]) {
int temp = [ary1[j] intValue];
ary1[j] = ary1[j+1];
ary1[j+1] = @(temp);
}
}
}
NSLog(@"%@",ary1);
⚠️时间复杂度O（n2）。
两种优化方式
第一种
设置一个标记位来标记是否发生了交换，如果没有发生交换就提前结束；
NSMutableArray *ary1 = [NSMutableArray arrayWithArray:@[@2,@6,@1,@3,@4,@5,@9]];
int flag = 0;//设置一个标记来标志一趟比较是否发生交换. 如果没有发生交换，则数组已经有序
for (int i = 0; i < [ary1 count] ; i++) {
flag = 0;
for (int j = 0; j < [ary1 count] - i - 1; j++) {
if (ary1[j] > ary1[j+1]) {
flag = 1;
int temp = [ary1[j] intValue];
ary1[j] = ary1[j+1];
ary1[j+1] = @(temp);
}
}
if (flag == 0) break;
}
NSLog(@"%@",ary1);
第二种
记录最后发生交换的位置，作为下一趟比较结束的位置
NSMutableArray *ary1 = [NSMutableArray arrayWithArray:@[@1,@3,@6,@8,@4,@5,@9]];
int flag = 0 ,k = (int)[ary1 count] - 1;//用一个变量记录下最后一个发生交换的位置，后面没有发生交换的已经有序;所以可以用这个值来作为下一次比较结束的位置
for (int i = 0; i < [ary1 count] ; ++i) {
if (flag > 0) break;
for (int j = 0; j < k ; ++j) {
if (ary1[j] > ary1[j+1]) {
flag = j;
int temp = [ary1[j] intValue];
ary1[j] = ary1[j+1];
ary1[j+1] = @(temp);
}
}
}
NSMutableArray *res = [NSMutableArray arrayWithCapacity:[ary1 count]];
flag -= 1;
int i = 0, j = flag; //i,j 表示的下标
while (i < flag && j < [ary1 count]) {
if (ary1[i] <= ary1[j]) {
[res addObject:ary1[i++]];
}else{
[res addObject:ary1[j++]];
}
}
while (i < flag) {
[res addObject:ary1[i++]];
}
while (j < [ary1 count]) {
[res addObject:ary1[j++]];
}
NSLog(@"%@",res);
冒泡排序优缺点：
优点:比较简单，空间复杂度较低，是稳定的；
缺点:时间复杂度太高，效率慢；
时间复杂度
最优的时间复杂度为：O( n^2 ) ；有的说 O(n)，下面会分析这种情况；
最差的时间复杂度为：O( n^2 )；
平均的时间复杂度为：O( n^2 )；
空间复杂度
空间复杂度就是在交换元素时那个临时变量所占的内存空间；
最优的空间复杂度就是开始元素顺序已经排好了，则空间复杂度为：0；
最差的空间复杂度就是开始元素逆序排序了，则空间复杂度为：O(n)；
平均的空间复杂度为：O(1)；
选择排序
iOS实现如下所示：
/**
选择排序
@param array 需要排序的Array
*/
+ (void)selectSort:(NSMutableArray *)array{
//遍历数组
/*
选择排序的原理：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
//排序数组
NSMutableArray *originalArray =
[NSMutableArray arrayWithObjects:@9,@1,@2,@5,@7,@4,@8,@6,@3,@5,nil];
*/
NSInteger min = 0;
for (int i=0; i<array.count; i++) {
//先设数组最小值下标为i；
min = i;
for (int j=i+1; j<array.count; j++) {
//待排序数组array[j] < array[min] 其最小值的下标为j
if (array[j]<array[min]) {
min = j;
}
}
//交换数据
if (min != i) {
[array exchangeObjectAtIndex:i withObjectAtIndex:min];
}
}
NSLog(@"选择排序：%@",array);
}
选择排序和冒泡排序的区别：
（1）冒泡排序是比较相邻位置的两个数，而选择排序是按顺序比较，找最大值或者最小值；
（2）冒泡排序每一轮比较后，位置不对都需要换位置，选择排序每一轮比较都只需要换一次位置；
（3）冒泡排序是通过数去找位置，选择排序是给定位置去找数；
（4）冒泡排序在内循环交换，选择排序在外循环交换
选择排序优缺点：
优点：一轮比较只需要换一次位置；
时间复杂度
选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有 n 个元素，则比较次数总是[n *(n - 1)] / 2。
而移动次数与序列的初始排序有关。当序列正序时，移动次数最少，为 0。当序列反序时，移动次数最多，为[3n *(n - 1) ]/ 2。选择排序的最优时间复杂度和最差时间复杂度和平均时间复杂度都为 ：O(n^2)
空间复杂度
空间复杂度，最优的情况下（已经有顺序）复杂度为：O(0) ；最差的情况下（全部元素都要重新排序）复杂度为：O(n )；平均的时间复杂度：O(1)
算法稳定性
选择排序是不稳定的排序方法
快速排序
是高快省的排序算法,在快速排序算法中，使用了分治策略。首先把序列分成两个子序列，递归地对子序列进行排序，直到整个序列排序结束。
- (void)quickSortArray:(NSMutableArray *)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex
{
if (leftIndex >= rightIndex) {//如果数组长度为0或1时返回
return ;
}
NSInteger i = leftIndex;
NSInteger j = rightIndex;
//记录比较基准数
NSInteger key = [array[i] integerValue];
while (i < j) {
/**** 首先从右边j开始查找比基准数小的值 ***/
while (i < j && [array[j] integerValue] >= key) {//如果比基准数大，继续查找
j--;
}
//如果比基准数小，则将查找到的小值调换到i的位置
array[i] = array[j];
/**** 当在右边查找到一个比基准数小的值时，就从i开始往后找比基准数大的值 ***/
while (i < j && [array[i] integerValue] <= key) {//如果比基准数小，继续查找
i++;
}
//如果比基准数大，则将查找到的大值调换到j的位置
array[j] = array[i];
}
//将基准数放到正确位置
array[i] = @(key);
/**** 递归排序 ***/
//排序基准数左边的
[self quickSortArray:array withLeftIndex:leftIndex andRightIndex:i - 1];
//排序基准数右边的
[self quickSortArray:array withLeftIndex:i + 1 andRightIndex:rightIndex];
}
快速排序复杂度分析
最优的情况下，时间复杂度为O(nlogn),最坏的情况下为O(n²)。平实的情况为O(nlogn)。
对于空间复杂度来说，主要是递归造成的栈空间的使用，最好情况，递归树的深度为log₂n,其空间复杂度也就是O(longn),最坏情况，需要进行n-1次递归调用，空间复杂度为O(n),平均情况，空间复杂度为O(logn)
由于关键字的比较和交换是跳跃进行的，因此，快速排序是一种不稳定的排序方法。
网友评论