iOS中熟悉常见的算法

1、对以下一组数据进行降序排序（冒泡排序）。“24，17，85，13，9，54，76，45，5，63”

int main(int argc, char *argv[]) {
  int array[10] = {24, 17, 85, 13, 9, 54, 76, 45, 5, 63};
  int num = sizeof(array)/sizeof(int);
  for(int i = 0; i < num-1; i++) {
    for(int j = 0; j < num - 1 - i; j++) {
      if(array[j] < array[j+1]) {
        int tmp = array[j];
        array[j] = array[j+1];
        array[j+1] = tmp;
      }
    }
  }

  for(int i = 0; i < num; i++) {
    printf("%d", array[i]);
    if(i == num-1) {
      printf("\n");
    }
    else {
      printf(" ");
    }
  }
}

2、对以下一组数据进行升序排序（选择排序）。“86, 37, 56, 29, 92, 73, 15, 63, 30, 8”

void sort(int a[],int n)
{
  int i, j, index;
  for(i = 0; i < n - 1; i++) {
    index = i;
    for(j = i + 1; j < n; j++) {
      if(a[index] > a[j]) {
        index = j;
      }
    }
 
    if(index != i) {
      int temp = a[i];
      a[i] = a[index];
      a[index] = temp;
    }
  }
}
 
int main(int argc, const char * argv[]) {
  int numArr[10] = {86, 37, 56, 29, 92, 73, 15, 63, 30, 8};
  sort(numArr, 10);
  for (int i = 0; i < 10; i++) {
    printf("%d, ", numArr[i]);
  }
  printf("\n");
 
  return 0;
}

3、快速排序算法

void sort(int *a, int left, int right) {
  if(left >= right) {
    return ;
  }
 
  int i = left;
  int j = right;
  int key = a[left];

  while (i < j) {
    while (i < j && key >= a[j]) {
      j--;
    }
 
    a[i] = a[j];

    while (i < j && key <= a[i]) {
      i++;
    }

    a[j] = a[i];
  }
 
  a[i] = key;
  sort(a, left, i-1);
  sort(a, i+1, right);
}

4、归并排序

void merge(int sourceArr[], int tempArr[], int startIndex, int midIndex, int endIndex) {

  int i = startIndex;
  int j = midIndex + 1;
  int k = startIndex;
  while (i != midIndex + 1 && j != endIndex + 1) {
    if (sourceArr[i] >= sourceArr[j]) {
      tempArr[k++] = sourceArr[j++];
    } else {
      tempArr[k++] = sourceArr[i++];
    }
  }
 
  while (i != midIndex + 1) {
    tempArr[k++] = sourceArr[i++];
  }
 
  while (j != endIndex + 1) {
    tempArr[k++] = sourceArr[j++];
  }
 
  for (i = startIndex; i <= endIndex; i++) {
    sourceArr[i] = tempArr[i];
  }
}
 
void sort(int souceArr[], int tempArr[], int startIndex, int endIndex) {
 
  int midIndex;
  if (startIndex < endIndex) {
    midIndex = (startIndex + endIndex) / 2;
    sort(souceArr, tempArr, startIndex, midIndex);
    sort(souceArr, tempArr, midIndex + 1, endIndex);
    merge(souceArr, tempArr, startIndex, midIndex, endIndex);
  }
}
 
int main(int argc, const char * argv[]) {
  int numArr[10] = {86, 37, 56, 29, 92, 73, 15, 63, 30, 8};
  int tempArr[10];
  sort(numArr, tempArr, 0, 9);
  for (int i = 0; i < 10; i++) {
    printf("%d, ", numArr[i]);
  }
  printf("\n");
  return 0;
}

5、实现二分查找算法（编程语言不限）

int bsearchWithoutRecursion(int array[],int low,int high,int target) {
  while(low <= high) {
    int mid = (low + high) / 2;
    if(array[mid] > target)
      high = mid - 1;
    else if(array[mid] < target)
      low = mid + 1;
    else  //findthetarget
      return mid;
  }
 
  //the array does not contain the target
  return -1;
}
 
----------------------------------------
 
递归实现
 
int binary_search(const int arr[],int low,int high,int key)
{
  int mid=low + (high - low) / 2;
  if(low > high)
    return -1;
  else{
    if(arr[mid] == key)
      return mid;
    else if(arr[mid] > key)
      return binary_search(arr, low, mid-1, key);
    else
      return binary_search(arr, mid+1, high, key);
  }
}

6、如何实现链表翻转（链表逆序）？

思路：每次把第二个元素提到最前面来。

#include <stdio.h>
#include <stdlib.h>
 
typedef struct NODE {
  struct NODE *next;
  int num;
}node;
 
node *createLinkList(int length) {
  if (length <= 0) {
    return NULL;
  }
 
  node *head,*p,*q;
  int number = 1;
  head = (node *)malloc(sizeof(node));
  head->num = 1;
  head->next = head;
  p = q = head;
  while (++number <= length) {
    p = (node *)malloc(sizeof(node));
    p->num = number;
    p->next = NULL;
    q->next = p;
    q = p;
  }
 
  return head;
}
 
 
void printLinkList(node *head) {
  if (head == NULL) {
    return;
  }
 
  node *p = head;
  while (p) {
    printf("%d ", p->num);
    p = p -> next;
  }
 
  printf("\n");
}
 
 
node *reverseFunc1(node *head) {
  if (head == NULL) {
    return head;
  }
 
  node *p,*q;
  p = head;
  q = NULL;
  while (p) {
    node *pNext = p -> next;
    p -> next = q;
    q = p;
    p = pNext;
  }
 
  return q;
}
 
 
int main(int argc, const char * argv[]) {
  node *head = createLinkList(7);
  if (head) {
    printLinkList(head);
    node *reHead = reverseFunc1(head);
    printLinkList(reHead);
    free(reHead);
  }
 
  free(head);
  return 0;
}

7、实现一个字符串“how are you”的逆序输出（编程语言不限）。如给定字符串为“hello world”,输出结果应当为“world hello”。

int spliterFunc(char *p) {
  char c[100][100];
  int i = 0;
  int j = 0;
 
  while (*p != '\0') {
    if (*p == ' ') {
      i++;
      j = 0;
    } else {
      c[i][j] = *p;
      j++;
    }

    p++;
  }
 
  for (int k = i; k >= 0; k--) {
    printf("%s", c[k]);
    if (k > 0) {
      printf(" ");
    } else {
      printf("\n");
    }
  }
 
  return 0;
}

8、给定一个字符串，输出本字符串中只出现一次并且最靠前的那个字符的位置？如“abaccddeeef”,字符是b,输出应该是2。

char *strOutPut(char *);
int compareDifferentChar(char, char *);
 
int main(int argc, const char * argv[]) {
  char *inputStr = "abaccddeeef";
  char *outputStr = strOutPut(inputStr);
  printf("%c \n", *outputStr);
  return 0;
}
 
char *strOutPut(char *s) {
  char str[100];
  char *p = s;
  int index = 0;
  while (*s != '\0') {
    if (compareDifferentChar(*s, p) == 1) {
      str[index] = *s;
      index++;
    }
    s++;
  }
  return &str;
}
 
int compareDifferentChar(char c, char *s) {
  int i = 0;
  while (*s != '\0' && i<= 1) {
    if (*s == c) {
      i++;
    }
    s++;
  }
 
  if (i == 1) {
    return 1;
  } else {
    return 0;
  }
}

9、打印2-100之间的素数

int main(int argc, const char * argv[]) {
  for (int i = 2; i < 100; i++) {
    int r = isPrime(i);
    if (r == 1) {
      printf("%ld ", i);
    }
  }
  return 0;
}

int isPrime(int n)
{
  int i, s;
  for(i = 2; i <= sqrt(n); i++)
    if(n % i == 0) return 0;
  return 1;
}

10、求两个整数的最大公约数。

int gcd(int a, int b) {
  int temp = 0;
  if (a < b) {
    temp = a;
    a = b;
    b = temp;
  }
 
  while (b != 0) {
    temp = a % b;
    a = b;
    b = temp;
  }
 
  return a;
}

iOS中熟悉常见的算法

1、 对以下一组数据进行降序排序（冒泡排序）。“24，17，85，13，9，54，76，45，5，63”

2、 对以下一组数据进行升序排序（选择排序）。“86, 37, 56, 29, 92, 73, 15, 63, 30, 8”

3、 快速排序算法

4、 归并排序

5、 实现二分查找算法（编程语言不限）

6、 如何实现链表翻转（链表逆序）？

7、 实现一个字符串“how are you”的逆序输出（编程语言不限）。如给定字符串为“hello world”,输出结果应当为“world hello”。

8、 给定一个字符串，输出本字符串中只出现一次并且最靠前的那个字符的位置？如“abaccddeeef”,字符是b,输出应该是2。

9、 打印2-100之间的素数

10、 求两个整数的最大公约数。

1、对以下一组数据进行降序排序（冒泡排序）。“24，17，85，13，9，54，76，45，5，63”

2、对以下一组数据进行升序排序（选择排序）。“86, 37, 56, 29, 92, 73, 15, 63, 30, 8”

3、快速排序算法

4、归并排序

5、实现二分查找算法（编程语言不限）

6、如何实现链表翻转（链表逆序）？

7、实现一个字符串“how are you”的逆序输出（编程语言不限）。如给定字符串为“hello world”,输出结果应当为“world hello”。

8、给定一个字符串，输出本字符串中只出现一次并且最靠前的那个字符的位置？如“abaccddeeef”,字符是b,输出应该是2。

9、打印2-100之间的素数

10、求两个整数的最大公约数。