数据结构算法基础
维基百科：
原地算法是指基本上不需要借助额外的数据结构就能对输入的数据进行变换的算法。不过，分配少量空间给部分辅助变量是被允许的。算法执行过程中，输入的数据往往会被输出结果覆盖。原地算法只能通过替换或交换元素的方式来修改原始的输入。不满足“原地”原则的算法也被称为非原地（not-in-place）算法或异地（out-of-place）算法。
当人们要解决一个输入规模，比如n，很大的问题时，往往会想到将该问题分解。比如将这n个输入分成k个不同的子集。如果能得到k个不同的可独立求解的子问题，而且在求出这些子问题的解之后，还可以找到适当的方法把它们的解合并成整个问题的解，那么复杂的难以解决的问题就可以得到解决。这种将整个问题分解成若干个小问题来处理的方法称为分治法。
分治算法的经典实例有：
void MaxMin(int* data, int len, int* Max, int* Min)
{
if(len == 1)
{
*Max = max(*Max, *data);
*Min = min(*Max, *data);
return;
} else if(len == 2) {
if(*data > *(data + 1)) {
*Max = max(*Max, *data);
*Min = min(*Max, *(data + 1));
} else {
*Max = max(*Max, *(data + 1));
*Min = min(*Max, *data);
}
return;
} else {
int mid = len / 2;
}
}
贪心算法是一种在每一步都做出局部最优选择的算法，希望通过一系列局部最优选择得到全局最优解。贪心算法一定可以得到局部最优解，但是局部最优解不一定是全局最优解。
贪心算法的经典实例有：
动态规划算法的经典实例有：
排序算法按照原理可分为：
基本原理：
每次将一个记录插入到已经排好序的序列中。
基本原理：
每次将一个待排序的记录按关键字大小插入到前面已经排好序的序列中，直到全部记录插入完毕。
即当从左向右、从小到大排序时，已排序序列位于左侧，然后依次将右侧未排序序列中第一个元素插入到左侧已排序序列中。
void insert_sort(int array[], int n)
{
for(int i = 1; i < n; i++)
{
for(int j = i - 1; j >= 0; j--)
{
if(array[j] > array[i])
{
swap(&array[i], &array[i]);
} else {
break;
}
}
}
}
基本原理：
从前向后(或从后向前)两两对比并按照目标顺序交换位置。每一趟均可确定未排序序列中最值元素的最终位置并使得下一趟排序中少进行一次比较。对于 n 个元素的序列需要执行 n-1 趟，对比
void bubble_sort(int *nums, int n) {
// 共计循环 n-1 趟
for(int trips = 0; trips < n - 1; trips++) {
// 从0循环到n - trips - 1
for(int i = 0; i < n - trips - 1; i++) {
if(*(nums + i) > *(nums + i + 1))
{
int temp = *(nums + i);
*(nums + i) = *(nums + i + 1);
*(nums + i + 1) = temp;
}
}
}
}
特性：
n 个元素的序列需要执行 n-1 趟。基本原理：
使用分治的基本思想，选择一个元素作为枢轴元素(pivot)，通常选择第一个或者最后一个元素，并通过元素交换使得所有左侧元素小于等于枢轴、右侧元素大于等于枢轴；并对枢轴左右两侧序列递归进行快速排序。
具体细节：
// 选择枢轴元素、处理数组并确定枢轴最终位置
int partition(int nums[], int low, int high)
{
int pivot = nums[low];
while(low < high)
{
while(low < high && nums[high] >= pivot) high --;
nums[low] = nums[high];
while(low < high && nums[low] <= pivot) low ++;
nums[high] = nums[low];
}
// 此时 low = high ，且为pivot的最终index
nums[low] = pivot;
return low;
}
void quick_sort(int nums[], int low, int high)
{
if(low < high)
{
// 选择枢轴元素并处理数组，返回枢轴元素最终位置
int pivot = partition(nums, low, high);
// 对枢轴左右未排序序列递归进行快排
quick_sort(nums, low, pivot - 1);
quick_sort(nums, pivot + 1, high);
}
}
int binary_search(int nums[], int n, int target) {
int l_index = 0, r_index = n - 1;
while(l_index <= r_index)
{
int mid = (l_index + r_index) / 2;
if(nums[mid] == target)
return mid;
else if(nums[mid] > target)
r_index = mid - 1;
else
l_index = mid + 1;
}
return -1;
}
辗转相除法是用于求两个非负整数 a 、 b 的最大公约数(gcd、Greatest Common Divisor)的方法，其基本逻辑如下：
注意：
a 必须大于等于 b 。C语言实现：
1// a must geq than b.2int gcd(int a, int b)3{4 int mod = a % b;5 if(mod)6 return gcd(b, mod);7 else8 return b;9}或者：
1// a must geq than b.2int gcd(int a, int b)3 return a % b ? gcd(b, a % b) : b;用小值乘最大公约数即可。
1int lcm(int a, int b)2 return a > b ? b * gcd(a, b) : a * gcd(b, a);