面试中常用的几个基本算法整理记录
- 二分查找
<pre>
递归方法: binarySearch1
int binarySearch1(int a[], int low, int high, int findNum) {
int mid = (low + high) / 2;
if (low > high) {
return -1;
} else {
if (a[mid] > findNum) {
binarySearch1(a, low, mid - 1, findNum);
} else if (a[mid] < findNum) {
binarySearch1(a, mid + 1, high, findNum);
} else {
return mid;
}
}
}
</pre>
<pre>
非递归方法: binarySearch2
int binarySearch2(int a[] , int low , int high , int findNum) {
while (low <= high)
{
int mid = ( low + high) / 2; //此处一定要放在while里面
if (a[mid] < findNum)
low = mid + 1;
else if (a[mid] > findNum)
high = mid - 1;
else
return mid;
}
return -1;
}
</pre>
- 二分查找
-
- 排序
<pre>
// 冒泡排序
void bubble_sort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j] = temp;
}
}
}
}
</pre>
<pre>
// 插入排序
void insert(int *a,int n) {
int i,j,key;
for(i=1;i<n;i++) { //控制需要插入的元素
key=a[i]; //key为要插入的元素
for(j=i;j>0 && a[j-1]>key;j--){ //查找要插入的位置,循环结束,则找到插入位置
a[j] = a[j-1]; //移动元素的位置.供要插入元素使用
}
a[j] = key; //插入需要插入的元素
}
}
</pre>
<pre>
// 快速排序
int Partition(int a[], int low, int high) {
int first = low;
int last = high;
int key = a[low]; //取第一个元素作为基准元
while (first < last) {
while (first < last && a[last] >= key)
last--;
a[first] = a[last];
while (first < last && a[first] <= key)
first++;
a[last] = a[first];
}
a[first] = key; //基准元居中
return first;
}
void QsortCommon(int a[] , int low, int high) {
if (low >= high) return; //递归出口
int partition = Partition(a, low, high); //将 >= x 的元素交换到右边区域，将 <= x 的元素交换到左边区域
QsortCommon(a, low, partition - 1);
QsortCommon(a, partition + 1, high);
}
</pre>
前几种代码就能看懂，直接说说快速排序
一. 快速排序的基本思想快速排序使用分治的思想，通过一趟排序将待排序列分割成两部分，其中一部分记录的关键字均比另一部分记录的关键字小。之后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
二. 快速排序的三个步骤
选择基准：在待排序列中，按照某种方式挑出一个元素，作为 “基准”（pivot）；
分割操作：以该基准在序列中的实际位置，把序列分成两个子序列。此时，在基准左边的元素都比该基准小，在基准右边的元素都比基准大；
递归地对两个序列进行快速排序，直到序列为空或者只有一个元素；
三. 选择基准元的方式
对于分治算法，当每次划分时，算法若都能分成两个等长的子序列时，那么分治算法效率会达到最大。也就是说，基准的选择是很重要的。选择基准的方式决定了两个分割后两个子序列的长度，进而对整个算法的效率产生决定性影响。
最理想的方法是，选择的基准恰好能把待排序序列分成两个等长的子序列。
- 排序
