经常在一些技术交流群里看到一些人分享的面试题，其中频率最高的莫过于一些基本算法了。所以我就整理了几种记录一下。
本文包含“冒泡排序、选择排序、快速排序、归并排序、逆序、二分查找、求两个整数的最大公约数和最小公倍数。”
对于这些名词，百度百科给解释的十分详细，包括算法都列出了好几种语言的实现方法，不懂的可以去百度。
冒泡排序
冒泡排序算法的运作如下：（从后往前）
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。[1]
算法实现：
/**
冒泡排序
@param mutableArray 排序的目标数组
*/
- (void)bubbleSortWithMutableArray:(NSMutableArray *)mutableArray{
for (int i = 0; i < mutableArray.count-1; i++) {
for (int j = 0; j < mutableArray.count-1-i; j++) {
if ([mutableArray[j] integerValue] > [mutableArray[j+1] integerValue]) {
NSString *temp = mutableArray[j];
mutableArray[j] = mutableArray[j+1];
mutableArray[j+1] = temp;
}
}
}
NSLog(@"冒泡排序结果：%@",mutableArray);
}
选择排序
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
算法实现：
/**
选择排序
@param mutableArray 排序的目标数组
*/
- (void)selectionSortWithMutableArray:(NSMutableArray *)mutableArray{
for (int i = 0; i < mutableArray.count; i++) {
int index = i;
for (int j = i+1; j < mutableArray.count; j++) {
if ([mutableArray[index] integerValue] > [mutableArray[j] integerValue]) {
index = j;
}
}
if (index != i) {
NSString *temp = mutableArray[i];
mutableArray[i] = mutableArray[index];
mutableArray[index] = temp;
}
}
NSLog(@"选择排序结果：%@",mutableArray);
}
快速排序
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
算法实现：
/**
快速排序
@param mutableArray 排序的数组
@param leftIndex 左边索引
@param rightIndex 右边索引
*/
- (void)quickSortWithMutableArray:(NSMutableArray *)mutableArray leftIndex:(NSInteger)leftIndex rightIndex:(NSInteger)rightIndex
{
if (leftIndex >= rightIndex) {
return ;
}
NSInteger i = leftIndex;
NSInteger j = rightIndex;
//记录比较基准数
NSInteger key = [mutableArray[i] integerValue];
while (i < j) {
// 先从右边j开始查找比基准数小的值
// 如果比基准数大，继续查找
while (i < j && [mutableArray[j] integerValue] >= key) {
j--;
}
//如果比基准数小，则将查找到的小值调换到i的位置
mutableArray[i] = mutableArray[j];
// 当在右边查找到一个比基准数小的值时，就从i开始往后找比基准数大的值
// 如果比基准数小，继续查找
while (i < j && [mutableArray[i] integerValue] <= key) {
i++;
}
// 如果比基准数大，则将查找到的大值调换到j的位置
mutableArray[j] = mutableArray[i];
}
//一轮遍历完成后就能确认基准数的位置了，并调整到正确位置
mutableArray[i] = @(key);
// 排序后，从基准数位置将数据分为两部分，递归运算
[self quickSortWithMutableArray:mutableArray leftIndex:leftIndex rightIndex:i - 1];
[self quickSortWithMutableArray:mutableArray leftIndex:i + 1 rightIndex:rightIndex];
}
归并排序
归并过程为：比较a[i]和b[j]的大小，若a[i]≤b[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素b[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。
归并算法并不难理解，但代码的递归实现有点难理解，可在程序中打断点一步一步的理解。
算法实现：
/**
归并排序
@param mutableArray 排序数组
@param low 最低索引
@param high 最高索引
*/
- (void)mergeSortWithMutableArray:(NSMutableArray *)mutableArray lowIndex:(NSInteger)low highIndex:(NSInteger)high{
if (high <= low) {
return;
}
NSInteger mid = low + (high-low)/2;
[self mergeSortWithMutableArray:mutableArray lowIndex:low highIndex:mid];//左半部分排序
[self mergeSortWithMutableArray:mutableArray lowIndex:mid+1 highIndex:high];//右半部分排序
[self mergeWithMutableArray:mutableArray lowIndex:low highIndex:high midIndex:mid];
}
- (void)mergeWithMutableArray:(NSMutableArray *)mutableArray lowIndex:(NSInteger)low highIndex:(NSInteger)high midIndex:(NSInteger)mid{
NSInteger i = low,j = mid+1;
for (NSInteger k = low; k <= high; k++) {
self.mTempArr[k] = mutableArray[k];
}
for (NSInteger k = low; k <= high; k++) {
//左边的元素已经取完，取右半边的元素
if (i > mid) {
mutableArray[k] = self.mTempArr[j++];
}
//右边的元素已经取完，取左边的元素
else if (j > high) {
mutableArray[k] = self.mTempArr[i++];
}
//如果索引j的值大,那么取左边的值
else if ([self.mTempArr[j] integerValue] < [self.mTempArr[i] integerValue]) {
mutableArray[k] = self.mTempArr[j++];
}
else{
mutableArray[k] = self.mTempArr[i++];
}
}
}
逆序
就是将一串数列前后颠倒排序。
这个在iOS中直接有API，直接调用reverseObjectEnumerator就好了，十分方便。
如果不用系统自带的，也可以自己创建一个可变数组，从后往前取目标数组的值就好了。
算法实现：
/**
逆序排列
@param mutableArray 参数要为可变数组
*/
- (void)reverseSortWithMutableArray:(NSMutableArray *)mutableArray{
NSArray *reversedArray = [[mutableArray reverseObjectEnumerator] allObjects];
NSLog(@"倒序排序结果：%@",reversedArray);
}
二分法查找
假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
二分查找的前提是：数组必须是有序的。
算法实现：
/**
二分法查找
@param orderArray 遍历的数组对象 (要求数组是有序的)
@param target 目标值
@return 返回目标值在数组中的 index，如果没有返回 -1
*/
- (NSUInteger)binarySearchWithArray:(NSArray *)orderArray target:(NSInteger)target
{
if (!orderArray.count) {
return -1;
}
NSUInteger low = 0;
NSUInteger high = orderArray.count - 1;
while (low<=high) {
NSUInteger mid = low + (high-low)/2;
NSInteger num = [[orderArray objectAtIndex:mid] integerValue];
if (target == num) {
return mid;
}
else if(num > target){
high = mid -1;
}
else{
low = mid +1;
}
}
return -1;
}
最大公约数和最小公倍数
算法实现：
/**
最大公约数
@param num1 整数1
@param num2 整数2
@return 返回两个整数的最大公约数
*/
- (NSInteger)gcdWithNumber1:(NSInteger)num1 Number2:(NSInteger)num2{
while(num1 != num2){
if(num1 > num2){
num1 = num1-num2;
} else {
num2 = num2-num1;
}
}
return num1;
}
/**
最小公倍数
@param num1 整数1
@param num2 整数2
@return 返回两个整数的最小公倍数
*/
- (NSInteger)lcmWithNumber1:(NSInteger)num1 Number2:(NSInteger)num2{
NSInteger gcd = [self gcdWithNumber1:num1 Number2:num2];
// 最小公倍数 = 两整数的乘积 ÷ 最大公约数
return num1 * num2 / gcd;
}
网友评论