一，排序算法：冒泡排序，选择排序，快速排序，归并排序，插入排序，堆排序，希尔排序
冒泡排序：会重复的比较数组中相邻的两个元素，如果一个元素比另一个大或者小，就交换这两个元素的位置
NSMutableArray *arr_M = [NSMutableArray arrayWithObjects:@1,@4,@2,@3,@5,nil];
//遍历`数组的个数`次
for (int i = 0; i < arr_M.count; ++i) {
//遍历数组的每一个`索引`（不包括最后一个,因为比较的是j+1）
for (int j = 0; j < arr_M.count-1; ++j) {
//根据索引的`相邻两位`进行`比较`
if (arr_M[j] < arr_M[j+1]) {
[arr_M exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
}
NSLog(@"最终结果：%@",arr_M);
选择排序:先假设arr[i]为最小，再逐一比较，若遇到比之小的就交换。
for (int i = 0; i < num; i ++) {
for (int j = i + 1 ; j < num - 1; j ++) {
if (array[i] > array[j]) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
}
快速排序：设要排序的数组是mutableArray对象，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一次快速排序。
- (void)viewDidLoad {
[super viewDidLoad];
NSMutableArray *arr = [[NSMutableArray alloc] initWithObjects:@(6), @(1),@(2),@(5),@(9),@(4),@(3),@(7),nil];
[self quickSortArray:arr withLeftIndex:0 andRightIndex:arr.count - 1];
NSLog(@"%@",arr);
}
- (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];
}
归并排序:归并排序是建立在归并操作上的一种有效的排序算法，算法主要采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序的算法复杂度为O（N*logN），需要的额外的空间跟数组的长度N有关系，实现归并排序最简单的方法是将两个数组重新整合到第三个数组中。通常对于一个数组我们对前半部分进行排序，然后进行后半部分进行排序，实现原地归并操作，不过需要额外的空间存储数组。假设数据中有8个元素，先分为四组进行比较，之后分为两组进行比较，最后分为一组进行比较，这样就衍生出来两种方法，一种是自顶向下的归并排序，一种是自底向上的归并排序。
-(void)mergeSort:(NSMutableArray *)arr lowIndex:(NSInteger)low highIndex:(NSInteger)high{
if (high<=low) {
return;
}
NSInteger mid=low+(high-low)/2;
[self mergeSort:arr lowIndex:low highIndex:mid];//左半部分排序
[self mergeSort:arr lowIndex:mid+1 highIndex:high];//右半部分排序
[self merge:arr lowIndex:low highIndex:high midIndex:mid];
}
merge操作，就是对数组进行比较:
-(void)merge:(NSMutableArray *)dataSource lowIndex:(NSInteger)low highIndex:(NSInteger)high midIndex:(NSInteger)mid{
NSInteger i=low,j=mid+1;
for (NSInteger k=low; k<=high; k++) {
self.tempArr[k]=dataSource[k];
}
for (NSInteger k=low; k<=high; k++) {
//左边的元素已经取完，取右半边的元素
if (i>mid) {
dataSource[k]= self.tempArr[j++];
}
//右边的元素已经取完，取左边的元素
else if (j>high) {
dataSource[k]= self.tempArr[i++];
}
//如果索引j的值大,那么取左边的值
else if ([self.tempArr[j] integerValue]<[self.tempArr[i] integerValue]) {
dataSource[k]=self.tempArr[j++];
}
else{
dataSource[k]=self.tempArr[i++];
}
}
}
合并的时候需要给临时数组赋值:
MySort *sort=[[MySort alloc]init];
NSMutableArray *tempArr=[[NSMutableArray alloc]initWithCapacity:10];
for (NSInteger i=0; i<8; i++) {
[tempArr addObject:[NSNull null]];
}
NSMutableArray *arr=[[NSMutableArray alloc]initWithCapacity:10];
[arr addObject:@"16"];
[arr addObject:@"3"];
[arr addObject:@"2"];
[arr addObject:@"18"];
[arr addObject:@"19"];
[arr addObject:@"10"];
[arr addObject:@"4"];
[arr addObject:@"25"];
sort.tempArr=tempArr;
[sort mergeSort:arr lowIndex:0 highIndex:arr.count-1];
for (NSInteger i=0; i<[arr count]; i++) {
NSLog(@"数值:%@",arr[i]);
}
插入排序:直接插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其keyword大小插入到前面已经排好序的子序列中的适当位置，直到所有记录插入完毕为止。
设数组为a[0…n-1]。
初始时。a[0]自成1个有序区，无序区为a[1..n-1]。令i=1将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。i++并反复第二步直到i==n-1。
int array[] = {3,2, 6, 9, 8, 5, 7, 1, 4};
//为了添加可移植性(採取sizeof())计算数组元素个数count
int count = sizeof(array) /sizeof(array[0]);
//逐个记录,插入有序数列
for (int i = 1; i < count; i++) {
int j = i; //j是一个坑， 确定坑的位置，再把数从坑里取出来，注意顺序
int temp = array[i]; //temp 是从坑里取数
//把a[i]插入有序序列
while (j > 0 && temp < array[j -1]) { //j > 0 防止越界。写&&前面效率更高
array[j] = array[j - 1];
j--;
}
array[j] = temp;
}
for (int i = 0; i < count; i++) {
printf("[%2d]: %d\n", i, array[i]);
}
堆排序:堆排序(Heap Sort) 就是利用堆(假设利用大堆顶)进行排序的方法。它的基本思想是，将待排序的序列构成一个大顶堆。此时，整个序列的最大值就是堆顶的根节点。将它移走(其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值)，然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次小值。如此反复执行，便能得到一个有序序列了。
- (void)heapSort:(NSMutableArray *)list
{
NSInteger i ,size;
size = list.count;
//找出最大的元素放到堆顶
for (i= list.count/2; i>=0; i--) {
[self createBiggesHeap:list withSize:size beIndex:i];
}
while(size > 0){
[list exchangeObjectAtIndex:size-1 withObjectAtIndex:0]; //将根(最大) 与数组最末交换
size -- ;//树大小减小
[self createBiggesHeap:list withSize:size beIndex:0];
}
NSLog(@"%@",list);
}
- (void)createBiggesHeap:(NSMutableArray *)list withSize:(NSInteger) size beIndex:(NSInteger)element
{
NSInteger lchild = element *2 + 1,rchild = lchild+1; //左右子树
while (rchild < size) { //子树均在范围内
if (list[element]>=list[lchild] && list[element]>=list[rchild]) return; //如果比左右子树都大，完成整理
if (list[lchild] > list[rchild]) { //如果左边最大
[list exchangeObjectAtIndex:element withObjectAtIndex:lchild]; //把左面的提到上面
element = lchild; //循环时整理子树
}else{//否则右面最大
[list exchangeObjectAtIndex:element withObjectAtIndex:rchild];
element = rchild;
}
lchild = element * 2 +1;
rchild = lchild + 1; //重新计算子树位置
}
//只有左子树且子树大于自己
if (lchild < size && list[lchild] > list[element]) {
[list exchangeObjectAtIndex:lchild withObjectAtIndex:element];
}
}
希尔排序:希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
void shellSort (NSMutableArray *array) {
int count = (int)array.count;
//初始增量为数组长度的一半，然后每次除以2取整
for (int increment = count/2; increment>0; increment /=2) {
//初始下标设为第一个增量的位置，然后递增
for (int i = increment; i<count; i++) {
//获取当前位置
int j = i;
//然后将此位置之前的元素，按照增量进行跳跃式比较
while (j-increment>=0 && array[j]<array[j-increment]) {
[array exchangeObjectAtIndex:j withObjectAtIndex:j-increment];
j-=increment;
}
}
}
}
二，查找算法：顺序查找，二分查找，二叉树查找，哈希查找
顺序查找
条件：无序或有序队列。
原理：按顺序比较每个元素，直到找到关键字为止。
时间复杂度：O(n)
二分查找
条件：有序数组
原理：查找过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；
如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
如果在某一步骤数组为空，则代表找不到。
这种搜索算法每一次比较都使搜索范围缩小一半。
时间复杂度：O(logn)
哈希查找
条件：先创建哈希表（散列表）
原理：根据键值方式(Key value)进行查找，通过散列函数，定位数据元素。
时间复杂度：几乎是O(1)，取决于产生冲突的多少。
二叉树查找
什么是二叉树？
在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”，左子树和右子树同时也是二叉树。二叉树的子树有左右之分，并且次序不能任意颠倒。二叉树是递归定义的，所以一般二叉树的相关题目也都可以使用递归的思想来解决，当然也有一些可以使用非递归的思想解决，我下面列出的一些算法有些采用了递归，有些是非递归的。
什么是二叉排序树？
二叉排序树又叫二叉查找树或者二叉搜索树，它首先是一个二叉树，而且必须满足下面的条件：
1）若左子树不空，则左子树上所有结点的值均小于它的根节点的值；
2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值
3）左、右子树也分别为二叉排序树
4）没有键值相等的节点（？可能是因为不好处理键值相等的节点到底是左节点还是右节点吧）
三，例子
1，给定一个字符串，逆序输出
NSString *string = @"chenweidada";
NSMutableString *newString = [[NSMutableString alloc] initWithCapacity:string.length];
for (int i = string.length - 1; i >= 0; i--) {
unichar ch = [string characterAtIndex:i];
[newString appendFormat:@"%c", ch];
}
网友评论