常用算法.md

常用简单算法

1. 判断质数

效率最高

bool isPrime(int num) {
  if (num == 2 || num == 3)
    return true;
  if (num % 6 != 1 && num % 6 != 5)
    return false;
  for (int i = 5; i*i <= num; i += 6) {
    if (num % i == 0 || num % (i+2) == 0)
      return false;
  }
  return true;
}

暴力求解

bool isPrime(int num) {
  for (int i = 2; i < sqrt(num); i++) {
    if (num % i == 0)
      return false;
  }
  return true;
}

2. 判断2的整数次幂

是否是2的整数次幂

bool isPower(int num) {
  return num & (num - 1) == 0;
}

计算一个数字的二进制表示中1的个数

int countOne(int num) {
  int count = 0;
  while(data) {
    data = data & (data - 1);
    count++;
  }
  return count;
}

3. 最大公约数和最小公倍数

最大公约数：辗转相除

int gcd(int n1, int m1) {
  int n = n1 > m1 ? n1 : m1;
  int m = n1 < m1 ? n1 : m1;
  if (n % m == 0)
    return m;
  while(m) {
    int r = n % m;
    n = m; 
    m = r;
  }
  return n;
}

最大公约数：更相减损

int gcd(int n1, int m1) {
  int n = n1 > m1 ? n1 : m1;
  int m = n1 < m1 ? n1 : m1;
  if (n % m == 0)
    return m;
  return f1(m, n - m);
}

最小公倍数：gcd法

int lcm(int n1, int m1) {
  return n1 * n2 / gcd(n1, m1);
}

4. 排序

选择排序

void selection_sort(int arr[], int len) {
  for (int i = 0; i < len - 1; i++) {
    int min = i;
    for (int j = i + 1; j < len; j++) {
      if (arr[min] > arr[j])
        min = j;
      temp = arr[min];
      arr[min] = arr[i];
      arr[i] = temp;
    }
  }
}

冒泡排序

void bubble_sort(int arr[], int len) {
  for (int i = 0; i < len; i++) {
    for (int j = 0; j < len - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

快速排序

typedef struct _Range {
  int start, end;
} Range;
Range new_Range(int s, int e) {
  Range r;
  r.start = s;
  r.end = e;
  return r;
}
void swap(int *x, int *y) {
  int t = *x;
  *x = *y;
  *y = t;
}
void quick_sort(int arr[], const int len) {
  Range r[len];
  int p = 0;
  r[p++] = new_Range(0, len - 1);
  while (p) {
    Range range = r[--p];
    if (range.start >= range.end)
      continue;
    int mid = arr[range.end];
    int left = range.start, right = range.end - 1;
    while (left < right) {
      while (arr[left] < mid && left < right)
        left++;
      while (arr[right] >= mid && left < right)
        right--;
      swap(&arr[left], &arr[right]);
    }
    if (arr[left] >= arr[range.end])
      swap(&arr[left], &arr[range.end]);
    else
      left++;
    r[p++] = new_Range(range.start, left - 1);
    r[p++] = new_Range(left + 1, range.end);
  }
}

edit: Serein