目錄
- 常見算法
- 不用中間變量,用兩種方法交換A和B的值
- 求最大公約數(shù)
- 判斷質(zhì)數(shù)
- 字符串逆序輸出
- 排序相關(guān)算法
- 選擇排序
- 冒泡排序
- 折半查找（二分查找）
- 快速排序
- 模擬棧的操作
序言
雖然我們在平時工作中敦跌，算法用的比較少歹袁，但是面試的時候琼娘，算法考核算是一個必修課逻淌。所以熟悉算法，深刻理解本質(zhì)棠枉，對于面試就成竹在胸了明棍。
一 常用算法
1.1 不用中間變量,用兩種方法交換A和B的值
// 1.中間變量
void swap(int a, int b) {
int temp = a;
a = b;
b = temp;
}
// 2.加法
void swap(int a, int b) {
a = a + b;
b = a - b;
a = a - b;
}
// 3.異或（相同為0攒菠，不同為1. 可以理解為不進位加法）
void swap(int a, int b) {
a = a ^ b;
b = a ^ b;
a = a ^ b;
}
1.2 求最大公約數(shù)
比如20和4的最大公約數(shù)為4。18和27的最大公約數(shù)為9茎活。
/** 1.直接遍歷法 */
int maxCommonDivisor(int a, int b) {
int max = 0;
for (int i = 1; i <=b; i++) {
if (a % i == 0 && b % i == 0) {
max = i;
}
}
return max;
}
/** 2.輾轉(zhuǎn)相除法 其中a為大數(shù)昙沦，b為小數(shù) */
int maxCommonDivisor(int a, int b) {
int r;
while(a % b > 0) {
r = a % b;
a = b;
b = r;
}
return b;
}
1.3 判斷質(zhì)數(shù)
比如2,3,5,7,11,13,19等只能被1和自身整除的叫質(zhì)數(shù)
這里只用最簡單直接打判斷，一個個除载荔，看余數(shù)是否為零盾饮，如果不為零，則非質(zhì)數(shù)。
int isPrime(int n) {
for(int i = 2; i <= sqrt(n); i++) {
if(n % i == 0) {
return 0;
}
}
return 1;
}
1.4 字符串逆序輸出
直接用指針進行操作
void reverse(char s[]) {
// p指向字符串頭部
char *p = s ;
// q指向字符串尾部
char *q = s ;
while('\0' != *q) {
q++ ;
}
q-- ;
// 交換并移動指針丘损，直到p和q交叉
while(q > p) {
char t = *p;
char m = *q;
*p = m;
*q = t;
p++;
q--;
}
}
二 排序相關(guān)算法
2.1 選擇排序
選擇排序（Selection sort）是一種簡單直觀的排序算法普办。它的工作原理是每一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素徘钥，存放在序列的起始位置衔蹲，然后，再從剩余未排序元素中繼續(xù)尋找最谐蚀 （大）元素舆驶，然后放到已排序序列的末尾。以此類推而钞，直到全部待排序的數(shù)據(jù)元素排完沙廉。 選擇排序是不穩(wěn)定的排序方法。
最值出現(xiàn)在起始端
- 第1趟：在n個數(shù)中找到最小(大)數(shù)與第一個數(shù)交換位置
- 第2趟：在剩下n-1個數(shù)中找到最小(大)數(shù)與第二個數(shù)交換位置
- 重復這樣的操作...依次與第三個臼节、第四個...數(shù)交換位置
- 第n-1趟撬陵，最終可實現(xiàn)數(shù)據(jù)的升序（降序）排列。
void selectSort(int *arr, int length) {
for (int i = 0; i < length - 1; i++) { //趟數(shù)
for (int j = i + 1; j < length; j++) { //比較次數(shù)
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
2.2 冒泡排序
它重復地走訪過要排序的元素列网缝，依次比較兩個相鄰的元素袱结，如果他們的順序（如從大到小、首字母從A到Z）錯誤就把他們交換過來途凫。走訪元素的工作是重復地進行直到?jīng)]有相鄰元素需要交換垢夹，也就是說該元素已經(jīng)排序完成。
這個算法的名字由來是因為越大的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端（升序或降序排列）维费，就如同碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣果元，故名“冒泡排序”。
相鄰元素兩兩比較犀盟，比較完一趟而晒，最值出現(xiàn)在末尾
- 第1趟：依次比較相鄰的兩個數(shù)，不斷交換（小數(shù)放前阅畴，大數(shù)放后）逐個推進倡怎，最值最后出現(xiàn)在第n個元素位置
- 第2趟：依次比較相鄰的兩個數(shù)，不斷交換（小數(shù)放前贱枣，大數(shù)放后）逐個推進监署，最值最后出現(xiàn)在第n-1個元素位置
- …… ……
- 第n-1趟：依次比較相鄰的兩個數(shù)，不斷交換（小數(shù)放前纽哥，大數(shù)放后）逐個推進钠乏，最值最后出現(xiàn)在第2個元素位置
void bublleSort(int *arr, int length) {
for(int i = 0; i < length - 1; i++) { //趟數(shù)
for(int j = 0; j < length - i - 1; j++) { //比較次數(shù)
if(arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
2.3 折半查找（二分查找）
在計算機科學中，折半搜索（英語：half-interval search）春塌，也稱二分搜索（英語：binary search）晓避、對數(shù)搜索（英語：logarithmic search）簇捍，是一種在有序數(shù)組中查找某一特定元素的搜索算法。
搜索過程從數(shù)組的中間元素開始俏拱，如果中間元素正好是要查找的元素暑塑，則搜索過程結(jié)束；如果某一特定元素大于或者小于中間元素锅必，則在數(shù)組大于或小于中間元素的那一半中查找梯投，而且跟開始一樣從中間元素開始比較。如果在某一步驟數(shù)組為空况毅，則代表找不到分蓖。這種搜索算法每一次比較都使搜索范圍縮小一半 [1] 。
優(yōu)化查找時間（不用遍歷全部數(shù)據(jù)）
- 1 數(shù)組必須是有序的
- 2 必須已知min和max（知道范圍）
- 3 動態(tài)計算mid的值尔许，取出mid對應的值進行比較
- 4 如果mid對應的值大于要查找的值么鹤，那么max要變小為mid-1
- 5 如果mid對應的值小于要查找的值，那么min要變大為mid+1
已知一個有序數(shù)組, 和一個key, 要求從數(shù)組中找到key對應的索引位置
int findKey(int *arr, int length, int key) {
int min = 0, max = length - 1, mid;
while (min <= max) {
mid = (min + max) / 2; //計算中間值
if (key > arr[mid]) {
min = mid + 1;
} else if (key < arr[mid]) {
max = mid - 1;
} else {
return mid;
}
}
return -1;
}
2.4 快速排序
快速排序由C. A. R. Hoare在1962年提出味廊。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分蒸甜，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序余佛，整個排序過程可以遞歸進行柠新，以此達到整個數(shù)據(jù)變成有序序列。
該方法的基本思想是：
- 1 先從數(shù)列中取出一個數(shù)作為基準數(shù)辉巡。
- 2 分區(qū)過程恨憎，將比這個數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊郊楣。
- 3 再對左右區(qū)間重復第二步憔恳，直到各區(qū)間只有一個數(shù)。
** 一趟快速排序的算法是：**
- 1 設置兩個變量i净蚤、j钥组，排序開始的時候：i=0，j=N-1今瀑；
- 2 以第一個數(shù)組元素作為關(guān)鍵數(shù)據(jù)程梦，賦值給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； (3,4步中撬呢，沒找到符合條件的值伦吠，即3中A[j]不小于key,4中A[i]不大于key的時候改變j、i的值魂拦，使得j=j-1毛仪，i=i+1，直至找到為止芯勘。找到符合條件的值箱靴，進行交換的時候i， j指針位置不變荷愕。另外衡怀，i==j這一過程一定正好是i+或j-完成的時候，此時令循環(huán)結(jié)束）安疗。
或許很多人看了后還是很懵逼抛杨，有個哥們總結(jié)的很好
下面詳細描述
雖然快速排序稱為分治法，但分治法這三個字顯然無法很好的概括快速排序的全部步驟荐类。因此我的對快速排序作了進一步的說明：挖坑填數(shù) + 分治法
以一個數(shù)組作為示例怖现，取區(qū)間第一個數(shù)為基準數(shù)。
初始時玉罐，i = 0; j = 9; X = a[i] = 72
由于已經(jīng)將a[0]中的數(shù)保存到X中真竖，可以理解成在數(shù)組a[0]上挖了個坑，可以將其它數(shù)據(jù)填充到這來厌小。
從j開始向前找一個比X小或等于X的數(shù)恢共。當j=8，符合條件璧亚，將a[8]挖出再填到上一個坑a[0]中讨韭。a[0]=a[8]; i++; 這樣一個坑a[0]就被搞定了，但又形成了一個新坑a[8]癣蟋，這怎么辦了透硝？簡單，再找數(shù)字來填a[8]這個坑疯搅。這次從i開始向后找一個大于X的數(shù)濒生，當i=3，符合條件幔欧，將a[3]挖出再填到上一個坑中a[8]=a[3]; j--;
數(shù)組變?yōu)椋?/p>
i = 3; j = 7; X=72
再重復上面的步驟罪治，先從后向前找丽声，再從前向后找。
從j開始向前找觉义，當j=5雁社，符合條件，將a[5]挖出填到上一個坑中晒骇，a[3] = a[5]; i++;
從i開始向后找霉撵，當i=5時，由于i==j退出洪囤。
此時徒坡，i = j = 5，而a[5]剛好又是上次挖的坑瘤缩，因此將X填入a[5]崭参。
數(shù)組變?yōu)椋?/p>
可以看出a[5]前面的數(shù)字都小于它，a[5]后面的數(shù)字都大于它款咖。因此再對a[0…4]和a[6…9]這二個子區(qū)間重復上述步驟就可以了何暮。
對挖坑填數(shù)進行總結(jié)
1．i =L; j = R; 將基準數(shù)挖出形成第一個坑a[i]。
2．j--由后向前找比它小的數(shù)铐殃，找到后挖出此數(shù)填前一個坑a[i]中海洼。
3．i++由前向后找比它大的數(shù)，找到后也挖出此數(shù)填到前一個坑a[j]中富腊。
4．再重復執(zhí)行2坏逢，3二步，直到i==j赘被，將基準數(shù)填入a[i]中是整。
照著這個總結(jié)很容易實現(xiàn)挖坑填數(shù)的代碼：
//快速排序
void quick_sort(int s[], int l, int r)
{
if (l < r)
{
//Swap(s[l], s[(l + r) / 2]); //將中間的這個數(shù)和第一個數(shù)交換 參見注1
int i = l, j = r, x = s[l];
while (i < j)
{
while(i < j && s[j] >= x) // 從右向左找第一個小于x的數(shù)
j--;
if(i < j)
s[i++] = s[j];
while(i < j && s[i] < x) // 從左向右找第一個大于等于x的數(shù)
i++;
if(i < j)
s[j--] = s[i];
}
s[i] = x;
quick_sort(s, l, i - 1); // 遞歸調(diào)用
quick_sort(s, i + 1, r);
}
}
三 模擬棧的操作
- 棧是一種數(shù)據(jù)結(jié)構(gòu)，特點：先進后出
代碼實現(xiàn)
- Stack.h
/**
定義block
@param obj 回調(diào)值
*/
typedef void(^StackBlock)(id obj);
/**
模擬棧實現(xiàn) - 簡單實現(xiàn)
*/
@interface Stack : NSObject
// 初始化操作
- (instancetype)initWithNumbers:(NSArray *)numbers;
/** 入棧 @param obj 指定入棧對象 */
- (void)push:(id)obj;
/** 出棧 */
- (id)popObj;
/** 是否為空 */
- (BOOL)isEmpty;
/** 棧的長度 */
- (NSInteger)stackLength;
/** 從棧底開始遍歷 @param block 回調(diào)遍歷的結(jié)果 */
-(void)enumerateObjectsFromBottom:(StackBlock)block;
/** 從頂部開始遍歷 */
-(void)enumerateObjectsFromtop:(StackBlock)block;
/** 所有元素出棧民假，一邊出棧一邊返回元素 */
-(void)enumerateObjectsPopStack:(StackBlock)block;
/** 清空 */
-(void)removeAllObjects;
/** 返回棧頂元素 */
-(id)topObj;
@end
- Stack.m
@interface Stack ()
// 存儲棧數(shù)據(jù)
@property (nonatomic, strong) NSMutableArray *stackArray;
@end
@implementation Stack
// 初始化操作
- (instancetype)initWithNumbers:(NSArray *)numbers {
self = [super init];
if (self) {
for (NSNumber *number in numbers) {
[self.stackArray addObject:number];
}
}
return self;
}
#pragma mark - push
- (void)push:(id)obj {
[self.stackArray addObject:obj];
}
#pragma mark - get
- (id)popObj {
if ([self isEmpty]) {
return nil;
} else {
id lastObject = self.stackArray.lastObject;
[self.stackArray removeLastObject];
return lastObject;
}
}
-(id)topObj {
if ([self isEmpty]) {
return nil;
} else {
return self.stackArray.lastObject;
}
}
- (BOOL)isEmpty {
return !self.stackArray.count;
}
- (NSInteger)stackLength {
return self.stackArray.count;
}
#pragma mark - 遍歷
// 從棧底開始遍歷
-(void)enumerateObjectsFromBottom:(StackBlock)block {
[self.stackArray enumerateObjectsWithOptions:NSEnumerationConcurrent usingBlock:^(id _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
block ? block(obj) : nil;
}];
}
// 從頂部開始遍歷
-(void)enumerateObjectsFromtop:(StackBlock)block {
[self.stackArray enumerateObjectsWithOptions:NSEnumerationReverse usingBlock:^(id _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
block ? block(obj) : nil;
}];
}
// 所有元素出棧浮入，一邊出棧一邊返回元素
-(void)enumerateObjectsPopStack:(StackBlock)block {
__weak typeof(self) weakSelf = self;
NSUInteger count = self.stackArray.count;
for (NSUInteger i = count; i > 0; i --) {
if (block) {
block(weakSelf.stackArray.lastObject);
[self.stackArray removeLastObject];
}
}
}
#pragma mark - remove
-(void)removeAllObjects {
[self.stackArray removeAllObjects];
}
#pragma mark - lazy
- (NSMutableArray *)stackArray {
if (!_stackArray) {
_stackArray = [NSMutableArray array];
}
return _stackArray;
}
@end
