基础篇要点分为三部分:1.算法、2.数据结构、3.基础设计模式(单例模式)
算法要求:
不但要掌握各个算法的含义,代码逻辑,更要能通过自己理解的角度对代码有一个清楚的认识,能使用自己的语言口述算法。
算法描述:
算法实现:
public static int binarySearch(int[] a, int t) {
int l = 0, r = a.length - 1, m;
while (l <= r) {
m = (l + r) / 2;
if (a[m] == t) {
return m;
} else if (a[m] > t) {
r = m - 1;
} else {
l = m + 1;
}
}
return -1;
}
其它考法
对于前两个题目,记得一个简要判断口诀:奇数二分取中间,偶数二分取中间靠左。对于后一道题目,需要知道公式:
n = [log2(N)] + 1;
(其中 2 为底数 n 为查找次数,N 为元素个数)
算法描述
算法实现
public static void bubble(int[] a) {
for (int j = 0; j < a.length - 1; j++) {
// 一轮冒泡
boolean swapped = false; // 是否发生了交换
for (int i = 0; i < a.length - 1 - j; i++) {
System.out.println("比较次数" + i);
if (a[i] > a[i + 1]) {
Utils.swap(a, i, i + 1);// 交换位置,大的往后排
swapped = true;
}
}
// 第一轮冒泡下来,最大元素排到最后
System.out.println("第" + j + "轮冒泡" + Arrays.toString(a));
if (!swapped) {
break;
}
}
}
public static void bubble_v2(int[] a) {
int n = a.length - 1;
while (true) {
int last = 0; // 表示最后一次交换索引位置
for (int i = 0; i < n; i++) {
System.out.println("比较次数" + i);
if (a[i] > a[i + 1]) {
Utils.swap(a, i, i + 1);
last = i;
}
}
n = last;
System.out.println("第轮冒泡" + Arrays.toString(a));
if (n == 0) {
break;
}
}
}
void bubble_sort(int arr[], int len) {
int i, j, temp;
for (i = 0; i < len - 1; i++){
for (j = 0; j < len - 1 - i; j++){
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
算法描述
算法实现
public static void selection(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
// i 代表每轮选择最小元素要交换到的目标索引
int s = i; // 代表最小元素的索引
for (int j = s + 1; j < a.length; j++) {
if (a[s] > a[j]) s = j; // j 元素比 s 元素还要小, 更新 s
}
if (s != i) {
swap(a, s, i);
}
System.out.println(Arrays.toString(a));
}
}
void swap(int *a,int *b){
int temp = *a;
*a = *b;
*b = temp;
}
void selection_sort(int arr[], int len){
int i,j;
for (i = 0 ; i < len - 1 ; i++){
int min = i;
for (j = i + 1; j < len; j++){
if (arr[j] < arr[min]) min = j;
}
swap(&arr[min], &arr[i]);
}
}
与冒泡排序比较
算法描述
算法实现
// 修改了代码与希尔排序一致
public static void insert(int[] a) {
for (int i = 1; i < a.length; i++) {
int t = a[i]; // 代表待插入的元素值
int j = i; // 已排序部分最后元素的索引
System.out.println(j);
while (j > 0 && t < a[j - 1]) {
a[j] = a[j - 1]; // j-1 是上一元素索引,若 > t,后移
j--;
}
if (j != i) a[j] = t; // 找到比 t 小的了,就插入在 j 这个位置
System.out.println(Arrays.toString(a) + " " + j);
}
}
void insertion_sort(int arr[], int len){
int i,j,temp;
for (i=1;i<len;i++){
temp = arr[i];
j=i-1;
while((j>=0) && (arr[j]>temp)) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = temp;
}
}
与选择排序比较
算法描述
算法实现
private static void shell(int[] a) {
for (int gap = a.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < a.length; i++) {
int t = a[i]; // 代表待插入的元素值
int j = i;
while (j >= gap && t < a[j - gap]) {
// 每次与上一个间隙为 gap 的元素进行插入排序
a[j] = a[j - gap]; // j-gap 是上一个元素索引,如果 > t,后移
j -= gap;
}
a[j] = t;
System.out.println(Arrays.toString(a) + " gap:" + gap);
}
}
}
void shell_sort(int arr[], int len) {
int gap, i, j;
int temp;
for (gap = len >> 1; gap > 0; gap >>= 1){
for (i = gap; i < len; i++) {
temp = arr[i];
for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
arr[j + gap] = arr[j];
arr[j + gap] = temp;
}
}
}
算法描述