iOS算法集合(一)
排序
- 冒泡排序
void bublleSort(int *arr, int length) {
for(int i = 0; i < length - 1; i++) { //趟数
for(int j = 0; j < length - i - 1; j++) { //比较次数
if(arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
- 二分排序
public void barnarySort(int arr[]){
for(int i=0;i<arr.length;i++){
int min=0;
int end=i-1;
int start=0;
int tmp=arr[i];
while(start<=end){
min=(start+end)/2;
if(arr[min]>tmp){
end=min-1;
}else{
start=min+1;
}
}
for(int j=i-1;j>end;j--){
data[j+1]=data[j];
}
data[end+1]=tmp;
}
}
- 快速排序
+ (void)quickSort:(NSMutableArray *)m low:(int)low high:(int)high{
if (low >= high) {
return;
}
int i = low;
int j = high;
id key = m[i];
while (i<j) {
while (i<j && [m[j] intValue] >= [key intValue]) {
j--;
}
if (i == j) { // 当key是目前最小的数时，会出现i=j的情况，
break;
}
m[i++] = m[j]; // i++ 会减少一次m[i]和key的比较
while (i < j && [m[i] intValue] <= [key intValue]) {
i++;
}
if (i == j) { // 当key是目前最大的数时(m[j]的前面)，会出现i=j的情况
break;
}
m[j--] = m[i]; //j-- 会减少一次m[j]和key的比较
}
m[i] = key;
[self quickSort: m low: low high: i-1];
[self quickSort: m low: i+1 high: high];
// NSLog(@"快速排序 %@",m);
}
二分查找
public int getIndex(int arr[],int x){
int start=0;
int end=arr.length-1;
int min=0;
while(start<=end){
min=(strat+end)/2;
if(x==arr[min]){
return min;
} esle if(x<arr[min]){
end=min-1;
}else if(x>arr[min){
start=min+1;
}
}
return -1;
}
字符串反转
给定字符串 “hello,world”,实现将其反转。输出结果：dlrow,olleh
- (void)charReverse
{
NSString * string = @"hello,world";
NSLog(@"%@",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)]];
}
NSLog(@"reverString:%@",reverString);
//C
char ch[100];
memcpy(ch, [string cStringUsingEncoding:NSUTF8StringEncoding], [string length]);
//设置两个指针，一个指向字符串开头，一个指向字符串末尾
char * begin = ch;
char * end = ch + strlen(ch) - 1;
//遍历字符数组，逐步交换两个指针所指向的内容，同时移动指针到对应的下个位置，直至begin>=end
while (begin < end) {
char temp = *begin;
*(begin++) = *end;
*(end--) = temp;
}
NSLog(@"reverseChar[]:%s",ch);
}
链表反转
反转前：1->2->3->4->NULL 反转后：4->3->2->1->NULL
/** 定义一个链表 */
struct Node {
NSInteger data;
struct Node * next;
};
- (void)listReverse
{
struct Node * p = [self constructList];
[self printList:p];
//反转后的链表头部
struct Node * newH = NULL;
//头插法
while (p != NULL) {
//记录下一个结点
struct Node * temp = p->next;
//当前结点的next指向新链表的头部
p->next = newH;
//更改新链表头部为当前结点
newH = p;
//移动p到下一个结点
p = temp;
}
[self printList:newH];
}
/**
打印链表
@param head 给定链表
*/
- (void)printList:(struct Node *)head
{
struct Node * temp = head;
printf("list is : ");
while (temp != NULL) {
printf("%zd ",temp->data);
temp = temp->next;
}
printf("\n");
}
/** 构造链表 */
- (struct Node *)constructList
{
//头结点
struct Node *head = NULL;
//尾结点
struct Node *cur = NULL;
for (NSInteger i = 0; i < 10; i++) {
struct Node *node = malloc(sizeof(struct Node));
node->data = i;
//头结点为空，新结点即为头结点
if (head == NULL) {
head = node;
}else{
//当前结点的next为尾结点
cur->next = node;
}
//设置当前结点为新结点
cur = node;
}
return head;
}
有序数组合并
将有序数组 {1,4,6,7,9} 和 {2,3,5,6,8,9,10,11,12} 合并为{1,2,3,4,5,6,6,7,8,9,9,10,11,12}
- (void)orderListMerge
{
int aLen = 5,bLen = 9;
int a[] = {1,4,6,7,9};
int b[] = {2,3,5,6,8,9,10,11,12};
[self printList:a length:aLen];
[self printList:b length:bLen];
int result[14];
int p = 0,q = 0,i = 0;//p和q分别为a和b的下标，i为合并结果数组的下标
//任一数组没有达到s边界则进行遍历
while (p < aLen && q < bLen) {
//如果a数组对应位置的值小于b数组对应位置的值,则存储a数组的值，并移动a数组的下标与合并结果数组的下标
if (a[p] < b[q]) result[i++] = a[p++];
//否则存储b数组的值，并移动b数组的下标与合并结果数组的下标
else result[i++] = b[q++];
}
//如果a数组有剩余，将a数组剩余部分拼接到合并结果数组的后面
while (++p < aLen) {
result[i++] = a[p];
}
//如果b数组有剩余，将b数组剩余部分拼接到合并结果数组的后面
while (q < bLen) {
result[i++] = b[q++];
}
[self printList:result length:aLen + bLen];
}
- (void)printList:(int [])list length:(int)length
{
for (int i = 0; i < length; i++) {
printf("%d ",list[i]);
}
printf("\n");
}
HASH算法
-
哈希表 例：给定值是字母a，对应ASCII码值是97，数组索引下标为97。 这里的ASCII码，就算是一种哈希函数，存储和查找都通过该函数，有效地提高查找效率。
-
在一个字符串中找到第一个只出现一次的字符。如输入”abaccdeff”，输出’b’ 字符(char)是一个长度为8的数据类型，因此总共有256种可能。每个字母根据其ASCII码值作为数组下标对应数组种的一个数字。数组中存储的是每个字符出现的次数。
- (void)hashTest
{
NSString * testString = @"hhaabccdeef";
char testCh[100];
memcpy(testCh, [testString cStringUsingEncoding:NSUTF8StringEncoding], [testString length]);
int list[256];
for (int i = 0; i < 256; i++) {
list[i] = 0;
}
char *p = testCh;
char result = '\0';
while (*p != result) {
list[*(p++)]++;
}
p = testCh;
while (*p != result) {
if (list[*p] == 1) {
result = *p;
break;
}
p++;
}
printf("result:%c",result);
}
求无序数组中的中位数
中位数：当数组个数n为奇数时，为(n + 1)/2，即是最中间那个数字；当n为偶数时，为(n/2 + (n/2 + 1))/2,即是中间两个数字的平均数。 首先要先去了解一些几种排序算法:iOS排序算法 思路:
- 排序算法+中位数 首先用冒泡排序、快速排序、堆排序、希尔排序等排序算法将所给数组排序，然后取出其中位数即可。
- 利用快排思想
资源来自—简书作者：Theendisthebegi
