好久没有记录东西了，今天整理记录一些常用的算法
时间复杂度：算法运行的时间
空间复杂度：算法运行完所需内存的大小
是不是稳定的算法：根据排序是相同的数据会不会被移动
一.冒泡排序
1.什么是冒泡排序？
答：冒泡排序算法的运作如下：（从后往前）
- 1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 3.针对所有的元素重复以上的步骤，除了最后一个。
- 4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
2.时间复杂度 和 空间复杂度
冒泡排序的时间复杂度：O（n2）
冒泡排序的空间复杂度：O（1）
3.代码
NSMutableArray * array = [NSMutableArray arrayWithObjects: @"1",@"8",@"2",@"7",@"2",@"5",@"9",nil];
//选择
for (int i =0; i<[array count]-1; i++) {
for (int j = i+1; j<[array count]; j++) {
if ([array[i] intValue]>[array[j] intValue]) {
//交换
[array exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
}
NSLog(@"%@",array);
4.是否是稳定算法：是
二.快速排序———》递归
1.什么是快速排序？
答：设要排序的
数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序
一趟快速排序的算法是：
-
1）设置两个变量i、j， 排序开始的时候：i=0，j=N-1；2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；5）重复第3、4步，直到i=j；
- 6）然后，对k两边的数据，再分组分别进行上述的过程，直到不能再分组为止
注意：第一遍快速排序不会直接得到最终结果，只会把比k大和比k小的数分到k的两边。为了得到最后结果，需要再次对下标2两边的数组分别执行此步骤，然后再分解数组，直到数组不能再分解为止（只有一个数据），才能得到正确结果。
2.时间复杂度 和 空间复杂度
快速排序的时间复杂度：O（n2）
快速排序的空间复杂度：O（log 2 N）~O(log n)
3.代码
- (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的位置
NSNumber *temp = array[i];
array[i] = array[j];
array[j] = temp;
NSLog(@"%@",array);
/**** 当在右边查找到一个比基准数小的值时，就从i开始往后找比基准数大的值 ***/
while (i < j && [array[i] integerValue] <= key) {//如果比基准数小，继续查找
i++;
}
//如果比基准数大，则将查找到的大值调换到j的位置
NSNumber *bigTemp = array[j];
array[j] = array[i];
array[i] = bigTemp;
NSLog(@"%@",array);
}
//将基准数放到正确位置
array[i] = @(key);
/**** 递归排序 ***/
//排序基准数左边的
[self quickSortArray:array withLeftIndex:leftIndex andRightIndex:i - 1];
//排序基准数右边的
[self quickSortArray:array withLeftIndex:i + 1 andRightIndex: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的位置
NSNumber *temp = array[i];
array[i] = array[j];
array[j] = temp;
NSLog(@"%@",array);
/**** 当在右边查找到一个比基准数小的值时，就从i开始往后找比基准数大的值 ***/
while (i < j && [array[i] integerValue] <= key) {//如果比基准数小，继续查找
i++;
}
//如果比基准数大，则将查找到的大值调换到j的位置
NSNumber *bigTemp = array[j];
array[j] = array[i];
array[i] = bigTemp;
NSLog(@"%@",array);
}
//将基准数放到正确位置
array[i] = @(key);
/**** 递归排序 ***/
//排序基准数左边的
[self quickSortArray:array withLeftIndex:leftIndex andRightIndex:i - 1];
//排序基准数右边的
[self quickSortArray:array withLeftIndex:i + 1 andRightIndex:rightIndex];
}
4.是否是稳定算法：否
三. 二分查找(折半查找)
折半查找方法适用于不经常变动而查找频繁的有序列表
1.什么是 二分查找？
答：给一个数，要求查找出来，前提这个数组是一个升序的数组，取数组的中间值，与此数比较，若相等，则返回这个数，若找的数比中间数小，则在中间数的左侧中再找，放在再右侧找，知道找到为止。
一趟快速排序的算法是：
-
1）数组为有序2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；5）重复第3、4步，直到i=j；
- 6）然后，对k两边的数据，再分组分别进行上述的过程，直到不能再分组为止
注意：第一遍快速排序不会直接得到最终结果，只会把比k大和比k小的数分到k的两边。为了得到最后结果，需要再次对下标2两边的数组分别执行此步骤，然后再分解数组，直到数组不能再分解为止（只有一个数据），才能得到正确结果。
2.时间复杂度 和 空间复杂度
二分查找的时间复杂度：O（log n）
快速排序的空间复杂度：O（1）
3.代码
-(NSInteger)searchNumWithArray:(NSArray *)array Num:(int)num
{
if (array.count <= 0) {
return -1;
}
int low = 0;
int height = (int)array.count - 1;
while (low <= height) {
int middle = (height - low)/2 + low;
if (num == [array[middle] integerValue]) {
return middle;
}else if (num < [array[middle] integerValue]){
return middle-1;
}else{
return middle+1;
}
}
return -1;
{
if (array.count <= 0) {
return -1;
}
int low = 0;
int height = (int)array.count - 1;
while (low <= height) {
int middle = (height - low)/2 + low;
if (num == [array[middle] integerValue]) {
return middle;
}else if (num < [array[middle] integerValue]){
return middle-1;
}else{
return middle+1;
}
}
return -1;
}
四. 选择排序
1.什么是选择排序？
答：每次找到最小的数才会交换
2， 1， 5， 4， 9
第一次排序：1， 2， 5， 4， 9
第二次排序： 1， 2， 5， 4， 9
第三次排序： 1， 2， 4， 5， 9
第四次排序： 1， 2， 4， 5， 9
（1）每次排序的时候都需要寻找第n小的数据，并且和array[n-1]发生交换
（2）等到n个数据都排序好，那么选择排序结束。
2.时间复杂度 和 空间复杂度
选择排序的时间复杂度：O（n 2）
选择排序的空间复杂度：O（1）
3.代码
- (NSMutableArray *)SelectSortOC:(NSMutableArray *)arr
{
for (int i=0; i < [arr count]-1; i++) {
for (int j = i+1; j<[arr count]; j++) {
if ([arr[i] integerValue] > [arr[j] integerValue]) {
[arr exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
}
return arr;
{
for (int i=0; i < [arr count]-1; i++) {
for (int j = i+1; j<[arr count]; j++) {
if ([arr[i] integerValue] > [arr[j] integerValue]) {
[arr exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
}
return arr;
}
4.是否是稳定算法：否
五. 插入排序
1.什么是插入排序？
答：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
2.时间复杂度 和 空间复杂度
插入排序的时间复杂度：O（n 2）
插入排序的空间复杂度：O（1）
3.代码
- (NSMutableArray *)InsertSortOC:(NSMutableArray *)arr
{
for (int i=1; i < [arr count]; i++) {
for (int j=0; j < i ; j++) {
if ([arr[i] integerValue] < [arr[j] integerValue]) {
[arr exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
}
return arr;
{
for (int i=1; i < [arr count]; i++) {
for (int j=0; j < i ; j++) {
if ([arr[i] integerValue] < [arr[j] integerValue]) {
[arr exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
}
return arr;
}
4.是否是稳定算法：是
