用两种方法交换A和B
// 中间变量法
- (void)exchangeA:(int)a andB:(int)b{
int temp = a;
a = b;
b = temp;
}
// 加法
- (void)exchangeA:(int)a andB:(int)b{
a = a + b;
b = a - b;
a = a - b;
}
求最大公约数
// 直接遍历法
- (int)LargestCommonDivisorMinNum:(int)a maxNum:(int)b{
int max = 0;
for (int i = 1; i <=b; i++) {
if (a % i == 0 && b % i == 0) {
max = i;
}
}
return max;
}
// 辗转相除法
- (int)LargestCommonDivisorMinNum:(int)a maxNum:(int)b{
int r = a % b;
if (r > 0) {
a = b;
b = r;
}
return b;
}
求最小公倍数
最小公倍数 = (a * b)/最大公约数
模拟栈操作
创建一个可变数组 stackArray
入栈操作：[self.stackArray addObject:obj];
出战操作：如果栈为空，返回nil，否则返回self.stackArray.lastObject
排序算法
冒泡：相邻元素进行比较，按照升序或者降序，交换两个相邻元素的位置 是一种“稳定排序算法”
最好的时间复杂度为O(n)
最坏的时间复杂度为O(n^2)
平均时间复杂度为O(n^2)
// 升序
- (void)bubbleSortWithArray:(NSMutableArray *)array {
for (int i = 0; i < array.count - 1; i++) {
//外层for循环控制循环次数
for (int j = 0; j < array.count - 1 - i; j++) {
//内层for循环控制交换次数
if ([array[j] integerValue] > [array[j + 1] integerValue]) {
[array exchangeObjectAtIndex:j withObjectAtIndex:j + 1];
}
}
}
}
// 降序
- (void)bubbleSortWithArray:(NSMutableArray *)array {
for (int i = 0; i < array.count - 1; i++) {
//外层for循环控制循环次数
for (int j = 0; j < array.count - 1 - i; j++) {
//内层for循环控制交换次数
if ([array[j] integerValue] < [array[j + 1] integerValue]) {
[array exchangeObjectAtIndex:j withObjectAtIndex:j + 1];
}
}
}
}
选择:将已排序部分定义在左端，然后选择未排序部分的最小元素和未排序部分的第一个元素交换。
最好的时间复杂度为O(n^2)
最坏的时间复杂度为O(n^2)
平均时间复杂度为O(n^2)
// 升序
- (void)bubbleSortWithArray:(NSMutableArray *)array {
for (int i = 0; i < array.count - 1; i++) {
for (int j = i + 1; j < array.count; j++) { //比较次数
if ([array[i] integerValue] > [array[j] integerValue]) {
id temp = array[i] ;
array[i] = array[j];
array[j] = temp;
}
}
}
}
快速:是对冒泡排序的一种改进。设要排序的数组是mutableArray对象，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一次快速排序。
1．先从数列中取出一个数作为基准数;
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边;
3．再对左右区间重复第二步，直到各区间只有一个数。
最好的时间复杂度为O(nlog2n)
最坏的时间复杂度为O(n^2)
平均时间复杂度为O(nlog2n)
NSMutableArray *arr = [NSMutableArray arrayWithObjects:@3,@8,@1,@12, nil];
[self quickSortArray:arr withLeftIndex:0 andRightIndex:arr.count-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(n)
最坏的时间复杂度为O(n^2)
平均时间复杂度为O(n^2)
- (void)bubbleSortWithArray:(NSMutableArray *)array {
//插入排序的原理：始终定义第一个元素为有序的，将元素逐个插入到有序排列之中，其特点是要不断的
//移动数据，空出一个适当的位置，把待插入的元素放到里面去。
for (int i = 0; i < array.count; i++) {
NSNumber *temp = array[i];
//temp 为待排元素 i为其位置 j为已排元素最后一个元素的位置（即取下一个元素，在已经排好序的元素序列中从后向前扫描）
int j = i-1;
//当j < 0 时， i 为第一个元素 该元素认为已经是排好序的 所以不进入while循环
// [array[j] compare:temp] == NSOrderedDescending与[array[j] intValue] > [temp intValue] 作用相同
while (j >= 0 && [array[j] compare:temp] == NSOrderedDescending) {
//如果已经排好序的序列中元素大于新元素，则将该元素往右移动一个位置
[array replaceObjectAtIndex:j+1 withObject:array[j]];
j--;
}
//跳出while循环时，j的元素小于或等于i的元素(待排元素)。插入新元素 i= j+1
[array replaceObjectAtIndex:j+1 withObject:temp];
}
NSLog(@"插入排序排序中:%@",array);
}
希尔:是插入排序的一种又称“缩小增量排序”，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。
算法思想 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
// 起始间隔值gap设置为总数的一半，直到 gap==1 结束
-(void)shellSort:(NSMutableArray *)list{
int gap = (int)list.count / 2; // 初始增量
while (gap >= 1) {
for(int i = gap ; i < [list count]; i++){
NSInteger temp = [[list objectAtIndex:i] intValue];
int j = i;
// 以下就是一个直接插入比较算法,只是直接插入比较的增量为1,希尔排序的增量为gap罢了
// j >= gap 因为增量为gap,所以只有当j >= 增量时,才有必要进行比较
// [j - gap] 因为gap为增量,每次都是以增量为跨度进行比较的
while (j >= gap && temp < [[list objectAtIndex:(j - gap)] intValue]) {
// 将比较大的数据移动到j位置上
[list replaceObjectAtIndex:j withObject:[list objectAtIndex:j-gap]];
// 往前移动增量个数,进行比较
j -= gap;
}
// 将待排序值插入j位置上
[list replaceObjectAtIndex:j withObject:[NSNumber numberWithInteger:temp]];
}
gap = gap / 2;
}
NSLog(@"====%@",list);
}
归并:就是利用归并的思想实现的排序方法。它的原理是假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或者1的有序子序列；再两两归并，......，如此反复，直到得到一个长度为n的有序序列为止，这种排序方法称为归并排序。[递归和非递归的方法]
- (void)megerSortAscendingOrderSort:(NSMutableArray *)ascendingArr
{
//tempArray数组里存放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(@"归并升序排序结果：%@", tempArray[0]);
}
- (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;
}
折半查找（二分查找）:当数据量很大适宜采用该方法。
采用二分法查找时，数据需是排好序的。
基本思想：假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较，如果当前位置值等于x，则查找成功；若x小于当前位置值，则在数列的前半段 中查找；若x大于当前位置值则在数列的后半段中继续查找，直到找到为止。
- (NSInteger)binarySearch:(NSArray *)source target:(NSInteger)target {
if (source.count == 0) {
return -1;
}
NSInteger start = 0;
NSInteger end = source.count - 1;
NSInteger mid = 0;
while (start + 1 < end) {
mid = start + (end - start) / 2;
if ([source[mid] integerValue] == target) { // 相邻就退出
return mid;
} else if ([source[mid] integerValue] < target) {
start = mid;
} else {
end = mid;
}
}
if ([source[start] integerValue] == target) {
return start;
}
if ([source[end] integerValue] == target) {
return end;
}
return -1;
}
基数:是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。
- (void)radixAscendingOrderSort:(NSMutableArray *)ascendingArr
{
NSMutableArray *buckt = [self createBucket];
NSNumber *maxnumber = [self listMaxItem:ascendingArr];
NSInteger maxLength = numberLength(maxnumber);
for (int digit = 1; digit <= maxLength; digit++) {
for (NSNumber *item in ascendingArr) {
NSInteger baseNumber = [self fetchBaseNumber:item digit:digit];
NSMutableArray *mutArray = buckt[baseNumber];
[mutArray addObject:item];
}
NSInteger index = 0;
for (int i = 0; i < buckt.count; i++) {
NSMutableArray *array = buckt[i];
while (array.count != 0) {
NSNumber *number = [array objectAtIndex:0];
ascendingArr[index] = number;
[array removeObjectAtIndex:0];
index++;
}
}
}
NSLog(@"基数升序排序结果：%@", ascendingArr);
}
- (NSMutableArray *)createBucket {
NSMutableArray *bucket = [NSMutableArray array];
for (int index = 0; index < 10; index++) {
NSMutableArray *array = [NSMutableArray array];
[bucket addObject:array];
}
return bucket;
}
- (NSNumber *)listMaxItem:(NSArray *)list {
NSNumber *maxNumber = list[0];
for (NSNumber *number in list) {
if ([maxNumber integerValue] < [number integerValue]) {
maxNumber = number;
}
}
return maxNumber;
}
NSInteger numberLength(NSNumber *number) {
NSString *string = [NSString stringWithFormat:@"%ld", (long)[number integerValue]];
return string.length;
}
- (NSInteger)fetchBaseNumber:(NSNumber *)number digit:(NSInteger)digit {
if (digit > 0 && digit <= numberLength(number)) {
NSMutableArray *numbersArray = [NSMutableArray array];
NSString *string = [NSString stringWithFormat:@"%ld", [number integerValue]];
for (int index = 0; index < numberLength(number); index++) {
[numbersArray addObject:[string substringWithRange:NSMakeRange(index, 1)]];
}
NSString *str = numbersArray[numbersArray.count - digit];
return [str integerValue];
}
return 0;
}
堆排序:
- (void)heapsortAsendingOrderSort:(NSMutableArray *)ascendingArr
{
NSInteger endIndex = ascendingArr.count - 1;
ascendingArr = [self heapCreate:ascendingArr];
while (endIndex >= 0) {
// NSLog(@"将list[0]:%@与list[(endIndex)]:%@交换", ascendingArr[0], ascendingArr[endIndex]);
NSNumber *temp = ascendingArr[0];
ascendingArr[0] = ascendingArr[endIndex];
ascendingArr[endIndex] = temp;
endIndex -= 1;
ascendingArr = [self heapAdjast:ascendingArr withStartIndex:0 withEndIndex:endIndex + 1];
}
NSLog(@"堆排序结果：%@", ascendingArr);
}
- (NSMutableArray *)heapCreate:(NSMutableArray *)array
{
NSInteger i = array.count;
while (i > 0) {
array = [self heapAdjast:array withStartIndex:i - 1 withEndIndex:array.count];
i -= 1;
}
return array;
}
- (NSMutableArray *)heapAdjast:(NSMutableArray *)items withStartIndex:(NSInteger)startIndex withEndIndex:(NSInteger)endIndex
{
NSNumber *temp = items[startIndex];
NSInteger fatherIndex = startIndex + 1;
NSInteger maxChildIndex = 2 * fatherIndex;
while (maxChildIndex <= endIndex) {
if (maxChildIndex < endIndex && [items[maxChildIndex - 1] floatValue] < [items[maxChildIndex] floatValue]) {
maxChildIndex++;
}
if ([temp floatValue] < [items[maxChildIndex - 1] floatValue]) {
items[fatherIndex - 1] = items[maxChildIndex - 1];
} else {
break;
}
fatherIndex = maxChildIndex;
maxChildIndex = fatherIndex * 2;
}
items[fatherIndex - 1] = temp;
return items;
}
字符串反转
- (NSString *)charReverse:(NSString *)string{
NSMutableString * reverString = [NSMutableString stringWithString:string];
for (NSInteger i = 0; i < (string.length + 1)/2; i++) {
[reverString replaceCharactersInRange:NSMakeRange(i, 1) withString:[string substringWithRange:NSMakeRange(string.length - i - 1, 1)]];
[reverString replaceCharactersInRange:NSMakeRange(string.length - i - 1, 1) withString:[string substringWithRange:NSMakeRange(i, 1)]];
}
return reverString;
}
网友评论