- 1.排序算法
- 1.1冒泡排序
- 1.2选择排序
- 1.3插入排序
- 1.4希尔排序
- 1.5归并排序
- 1.6快速排序
- 1.7计数排序
- 1.8基数排序
- 2.经典算法面试题
- 2.1鸡兔同笼问题(穷举法)
- 2.2斐波那契问题
- 2.3打印100以内除了尾数为3,5,7的所有数
- 2.4求猴子大王
- 2.5古典问题：生兔子问题
- 2.6打印水仙花数
- 2.7回文问题
- 2.8二分法查找
- 2.9完数问题
- 2.10杨辉三角
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个，即需要进行length-1次。
第一次是对n个数进行n-1次比较，进行到最后第n个的一个是最大的；
第二次是对n-1个数进行n-2次比较，进行到最后第n-1个的一个是最大的；
…
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
示例代码:
public class Bubble_sort {
public static void main(String[] args) {
//冒泡排序算法
int[] num=new int[]{10,21,8,16,7,23,12};
//需进行length-1次冒泡
for(int i = 0; i < num.length-1;i++){
for(int j=0;jnum[j+1]) {
int temp=num[j];
num[j]=num[j+1];
num[j+1]=temp;
}
}
}
System.out.println("从小到大排序后的结果是:");
for(int i=0;i
代码结果:
从小到大排序后的结果是:
7 8 10 12 16 21 23
1.2选择排序
选择排序原理即是，遍历元素找到一个最小（或最大）的元素，把它放在第一个位置，然后再在剩余元素中找到最小（或最大）的元素，把它放在第二个位置，依次下去，完成排序。
选择排序的时间复杂度为 O(n^2)。
第一次需要检查n个元素，但随后检查的元素数依次为n - 1, n – 2, …, 2和1。平均每次检查的元素数为1/2 * n， 因此运行时间为 n * 1/2 * n，简单地写作 O(n^2)。
示例代码:
public class SelectionSort {
public static void main(String[] args) {
int[] num = new int[] { 5, 3, 6, 2, 10, 18, 1 };
selectSort(num);
System.out.println("从小到大排序的结果为: "+ Arrays.toString(num));
}
public static void selectSort(int[] num) {
for (int i = 0; i < num.length - 1; i++) {
int minIndex = i; // 用来记录最小值的索引位置，默认值为i
for (int j = i + 1; j < num.length; j++) {
if (num[j] < num[minIndex]) {
minIndex = j; // 遍历 i+1~length 的值，找到其中最小值的位置
}
}
// 交换当前索引 i 和最小值索引 minIndex 两处的值
if (i != minIndex) {
int temp = num[i];
num[i] = num[minIndex];
num[minIndex] = temp;
}
// 执行完一次循环，当前索引 i 处的值为最小值，直到循环结束即可完成排序
}
}
}
执行结果:
从小到大排序的结果为: [1, 2, 3, 5, 6, 10, 18]
1.3插入排序
插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
示例代码:
public class InsertionSort {
public static void main(String[] args){
int[] num1 = {2,3,5,1,23,6,78,34};
int[] num2 = sort(num1);
System.out.println("从小到大排序的结果为: "+ Arrays.toString(num2));
}
public static int[] sort(int[] num1){
for(int i=1; i0; j--){
if(num1[j]
输出结果:
从小到大排序的结果为: [1, 2, 3, 5, 6, 23, 34, 78]
1.4希尔排序
希尔排序也成为“缩小增量排序”，其基本原理是，现将待排序的数组元素分成多个子序列，使得每个子序列的元素个数相对较少，然后对各个子序列分别进行直接插入排序，待整个待排序列“基本有序”后，最后在对所有元素进行一次直接插入排序。因此，我们要采用跳跃分割的策略：将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。希尔排序是对直接插入排序算法的优化和升级。
所谓的基本有序，就是小的关键字基本在前面，大的基本在后面，不大不小的基本在中间，例如｛2,1,3,6,4,7,5,8,9,｝就可以称为基本有序了。但像｛1,5,9,3,7,8,2,4,6｝这样，9在第三位，2在倒数第三位就谈不上基本有序。
希尔排序的关键并不是随便分组后各自排序，而是将相隔某个“增量”的记录组成一个子序列，实现跳跃式移动，使得排序的效率提高。需要注意的是，增量序列的最后一个增量值必须等于1才行。另外，由于记录是跳跃式的移动，希尔排序并不是一种稳定的排序算法。
希尔排序最好时间复杂度和平均时间复杂度都是O(nlogn)，最坏时间复杂度为 O(n^2)。
示例代码
public class ShellSort {
public static void main(String[] args) {
int[] arr = new int[] { 26, 53, 67, 48, 57, 13, 48, 32, 60, 50 };
shellSortSmallToBig(arr);
System.out.println("从小到大排序的结果为: "+Arrays.toString(arr));
}
public static void shellSortSmallToBig(int[] arr) {
int j = 0;
int temp = 0;
for (int increment = arr.length / 2; increment > 0; increment /= 2) {
for (int i = increment; i < arr.length; i++) {
temp = arr[i];
for (j = i - increment; j >= 0; j -= increment) {
if (temp < arr[j]) {
arr[j + increment] = arr[j];
} else {
break;
}
}
arr[j + increment] = temp;
}
}
}
}
输出结果:
从小到大排序的结果为: [13, 26, 32, 48, 48, 50, 53, 57, 60, 67]
1.5归并排序
归并排序是一种概念上最简单的排序算法，与快速排序一样，归并排序也是基于分治法的。归并排序将待排序的元素序列分成两个长度相等的子序列，为每一个子序列排序，然后再将他们合并成一个子序列。合并两个子序列的过程也就是两路归并。
归并排序是一种稳定的排序算法，归并排序的主要问题在于它需要一个与待排序数组一样大的辅助数组空间。由于归并排序每次划分时两个子序列的长度基本一样，所以归并排序最好、最差和平均时间复杂度都是nlog2n。
示例代码:
public class MergeSort {
//两路归并算法，两个排好序的子序列合并为一个子序列
public static void merge(int[] a, int left, int mid, int right) {
int[] tmp = new int[a.length];//辅助数组
int p1 = left, p2 = mid + 1, k = left;//p1、p2是检测指针，k是存放指针
while (p1 <= mid && p2 <= right) {
if (a[p1] <= a[p2])
tmp[k++] = a[p1++];
else
tmp[k++] = a[p2++];
}
while (p1 <= mid) tmp[k++] = a[p1++];//如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
while (p2 <= right) tmp[k++] = a[p2++];//同上
//复制回原素组
for (int i = left; i <= right; i++)
a[i] = tmp[i];
}
public static void mergeSort(int[] a, int start, int end) {
if (start < end) {//当子序列中只有一个元素时结束递归
int mid = (start + end) / 2;//划分子序列
mergeSort(a, start, mid);//对左侧子序列进行递归排序
mergeSort(a, mid + 1, end);//对右侧子序列进行递归排序
merge(a, start, mid, end);//合并
}
}
public static void main(String[] args) {
int[] arr = {49, 38, 65, 97, 76, 13, 27, 50};
mergeSort(arr, 0, arr.length - 1);
System.out.println("从小到大排序的结果为: " + Arrays.toString(arr));
}
}
输出结果:
从小到大排序的结果为: [13, 27, 38, 49, 50, 65, 76, 97]
1.6快速排序
快速排序（Quicksort）使用分治思想对冒泡排序作了改进，效率非常高。
其基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
从快速排序的基本思想可以分析出其实现思路：
一、选取一个枢轴元素（也叫基准元素）
二、将数组分割成两部分，一部分数据都小于或等于枢轴元素，另一部分数据都大于枢轴元素
三、对分割的子数组递归地执行步骤一二，直到无法分割
示例代码:
public class QuickSort {
public static void sort(int a[], int low, int hight) {
int i, j, index;
if (low > hight) {
return;
}
i = low;
j = hight;
index = a[i]; // 用子表的第一个记录做基准
while (i < j) { // 从表的两端交替向中间扫描
while (i < j && a[j] >= index)
j--;
if (i < j)
a[i++] = a[j];// 用比基准小的记录替换低位记录
while (i < j && a[i] < index)
i++;
if (i < j) // 用比基准大的记录替换高位记录
a[j--] = a[i];
}
a[i] = index;// 将基准数值替换回 a[i]
sort(a, low, i - 1); // 对低子表进行递归排序
sort(a, i + 1, hight); // 对高子表进行递归排序
}
public static void quickSort(int a[]) {
sort(a, 0, a.length - 1);
}
public static void main(String[] args) {
int arr[] = { 49, 38, 65, 97, 76, 13, 27, 49 };
quickSort(arr);
System.out.println("从小到大排序的结果为: " + Arrays.toString(arr));
}
}
输出结果:
从小到大排序的结果为: [13, 27, 38, 49, 49, 65, 76, 97]
1.7计数排序
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
- 找出待排序的数组中最大和最小的元素；
- 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
- 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
- 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
示例代码:
public class CountingSort {
public static int[] countingSort(int[] array) {
if (array.length == 0)
return array;
int bias, min = array[0], max = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > max)
max = array[i];
if (array[i] < min)
min = array[i];
}
bias = 0 - min;
int[] bucket = new int[max - min + 1];
Arrays.fill(bucket, 0);
for (int i = 0; i < array.length; i++) {
bucket[array[i] + bias]++;
}
int index = 0, i = 0;
while (index < array.length) {
if (bucket[i] != 0) {
array[index] = i - bias;
bucket[i]--;
index++;
} else
i++;
}
return array;
}
public static void main(String[] args) {
int[] arr = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };
countingSort(arr);
System.out.println("从小到大排序的结果为: " + Arrays.toString(arr));
}
}
输出结果:
从小到大排序的结果为: [1, 2, 3, 4, 5, 6, 7, 8, 9]
1.8基数排序
首先说一下，我发现好多人写的基数排序只能排序正整数，其实只要处理下就可以排序含有负数的了，就是我们排序前先把所有的数整体变大（就是减上最小的负数，也就是加了），都变成正数，然后排序好之后，在减下来（加上最小的负数，也就减了）就好了。
基数排序就是按数位排序可分为LSD（从最低位[也就是个位]开始排序）和MSD（从最高位开始排序），下面写的事LSD基数排序。
基数排序就是把数按位考虑，让后我们一位数只能是[0，9]，就是我们在考虑某位（个位、百位· · ·）的时候就只看这个位的数，放到在[0，9]相应的位置，然后顺序取出，最后再按其它位这样操作（上面说了要不从低位开始到高位，要不就是从高位到低位）
示例代码:
public class RadixSort {
public static void main(String[] args) {
//定义整型数组
int[] arr = {21,56,88,195,354,1,35,12,6,7};
//调用基数排序函数
lsd_RadixSort(arr,3);
//输出排序后的数组
System.out.println("从小到大排序的结果为: " + Arrays.toString(arr));
}
//arr是要排序的数组，max是数组中最大的数有几位
public static void lsd_RadixSort(int[] arr,int max) {
//count数组用来计数
int[] count = new int[arr.length];
//bucket用来当桶（在下面你就理解了什么是桶了），放数据，取数据
int[] bucket = new int[arr.length];
//k表示第几位，1代表个位，2代表十位，3代表百位
for(int k=1;k<=max;k++) {
//把count置空，防止上次循环的数据影响
for(int i=0;i=0;i--) {
int j = getFigure(arr[i],k);
bucket[count[j]-1] = arr[i];
count[j]--;
}
//将桶中的数据取出来，赋值给arr
for(int i=0,j=0;i
输出结果:
从小到大排序的结果为: [1, 6, 7, 12, 21, 35, 56, 88, 195, 354]
2.经典算法面试题
2.1鸡兔同笼问题(穷举法)
已知:鸡兔共35只,共94只脚,那么鸡和兔各几只?
示例代码:
public class SameCage {
public static void main(String[] args) {
//循环变量j,控制小鸡的个数: 0到35递增
//循环变量t,控制兔子的个数: 35到0递减
for(int j=0,t=35; j<=35; j++,t--) {//如果有多个小条件,用逗号隔开
//保证脚的数量是94
if(j*2 + t*4 == 94) {
System.out.println("鸡："+j+"， 兔："+t);
}
}
}
}
输出结果:
鸡：23， 兔：12
2.2斐波那契问题
已知:斐波那契数列的前几个数分别为0,1,1,2,3,5…从第三项开始,每一项都等于前两项的和.请接收用户输入的整数n,求出此数列的前n项.
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……
其规律很明显，从第3个数开始，每个数都等于它前两个数的和。
下面我们可以通过用户输入的数字n来输出斐波那契数列的前n项
示例代码:
public class Faibonacci {
public static void main(String[] args) {
System.out.println("请输入您要测试的数:");
int n = new Scanner(System.in).nextInt();
//判断n是否是不正常的范围
if(n<1){
System.out.println("输入数据有误！！！");
}
//n==1
if(n==1){
System.out.println(0);
}
//n==2
if(n==2){
System.out.println(0+"t"+1);
}
//n==3
if(n==3){
System.out.println(0+"t"+1+"t"+1);
}
//拼接前n项
if(n>3){
System.out.print(0+"t"+1+"t"+1+"t");
}
//循环输出后面的数据
int f1=1;
int f2=1;
int next=0;
for(int i=4;i<=n;i++){
next=f1+f2;
f1=f2;
f2=next;
System.out.print(next+"t");
}
}
}
2.3打印100以内除了尾数为3,5,7的所有数
示例代码:
public class ForContinue {
public static void main(String[] args) {
System.out.println("结果为:");
for(int i=1;i<=100;i++) {
int y = i%10;//100以内的数,通过取余求出尾数
if(y==3 || y==5 || y==7) {
continue;//如果尾数为3 5 7 ,则跳过后面的打印,进行下一轮循环
}
System.out.print(" "+i);
}
}
}
输出结果:
结果为:
1 2 4 6 8 9 10 11 12 14 16 18 19 20 21 22 24 26 28 29 30 31 32 34 36 38 39 40 41 42 44 46 48 49 50 51 52 54 56 58 59 60 61 62 64 66 68 69 70 71 72 74 76 78 79 80 81 82 84 86 88 89 90 91 92 94 96 98 99 100
2.4求猴子大王
15个猴子围成一圈选大王,依次1-7循环报数,报到7的猴子被淘汰,直到最后一只猴子称为大王,问:哪只猴子会成为大王?
示例代码:
public class MonkeyKing {
public static void main(String[] args) {
//1.定义长度为15的数组保存猴子,boolean类型是为了判断猴子是否存活
boolean[] b=new boolean[15];
//2.依次遍历每一只猴子
//true---未淘汰 false---已淘汰
for(int i=0;i1){//判断条件
//7.检测猴子是否已淘汰
if(b[index]){
//8.报数
num++;
//9.判断报数是否为7
if(num==7){
b[index]=false;//为7淘汰
monkeyLeft--;//猴子数减一
num=0;//报数归零
}
}
//10.下标移动
index++;
//11.围成一圈---最后一个置为0
if(index==15){
index=0;
}
}
//遍历数组,找到最后活着的那个猴子王
for(int i=0;i
输出结果:
5
2.5古典问题：生兔子问题
有一对兔子，从出生后第3个月起都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月兔子的对数为多少？
程序分析：前两个月兔子的对数为1
从第三个月开始，兔子的对数变成了 2 3 5 8 13 21 …
示例代码:
public class GetRabbitNum {
public static void main(String[] args) {
System.out.println("请输入要判断的月数：");
int month = new Scanner(System.in).nextInt();
System.out.println("第"+month+"月兔子的对数为："+getSum(month));
}
public static int getSum(int month) {
//如果是前两个月，还是1对兔子
if(month == 1 || month == 2) {
return 1;
}else {
//从第三个开始，兔子按照2 3 5 8 13 21变化
return getSum(month-1)+getSum(month-2);
}
}
}
输出结果:
请输入要判断的月数：
12
第12月兔子的对数为：144
2.6打印水仙花数
水仙花数：是指一个三位数，其各位数字立方和等于该数字本身
例如：153就是一个水仙花数，因为153 = 1³ + 5³ + 3³
示例代码:
public class GetDaffodilNum {
public static void main(String[] args) {
//1.遍历所有的三位数
for (int i = 100; i < 1000; i++) {
//2.调用自定义方法判断是不是水仙花数
if(isAim(i)) {
//3.如果是水仙花数，就打印
System.out.println(i);
}
}
}
//4.自定义判断水仙花数的方法
public static boolean isAim(int a) {
int x = a/100;
int y = a/10%10;
int z = a%10;
if(a == x*x*x+y*y*y+z*z*z) {
return true;
}
return false;
}
}
输出结果:
153
370
371
407
2.7回文问题
需求,如果一个用户输入的数据,从前到后或者从后到前读到的内容都是一样的,我们就称这种数据为"回文",比如123321 或者 12321 或者上海自来水来自海上等等
示例代码:
public class TestNumber {
public static void main(String[] args) {
System.out.println("请输入一个字符串:");
String s = new Scanner(System.in).nextLine();
if(!stringJudge(s)){
System.out.println(s + "不是回文字符串");
}else{
System.out.println(s + "是回文字符串");
}
}
//判断字符串是否回文
private static boolean stringJudge(String str) {
for (int i = 0; i < str.length() - i - 1; i++){
if(str.charAt(i) == str.charAt(str.length() - i - 1)){
continue;
}else{
return false;
}
}
return true;
}
}
输出结果1:
请输入一个字符串:
12321
12321是回文字符串
输出结果2:
请输入一个字符串:
我是中国人
我是中国人不是回文字符串
2.8二分法查找
二分法查找（Binary Search）也称折半查找，是指当每次查询时，将数据分为前后两部分，再用中值和待搜索的值进行比较，如果搜索的值大于中值，则使用同样的方式（二分法）向后搜索，反之则向前搜索，直到搜索结束为止。
二分法使用的时候需要注意：二分法只适用于有序的数据，也就是说，数据必须是从小到大，或是从大到小排序的。
示例代码:
public class dichotomizingSearch {
public static void main(String[] args) {
// 二分法查找
int[] binaryNums = {1, 6, 15, 18, 27, 50};
int findValue = 27;
int binaryResult = binarySearch(binaryNums, 0, binaryNums.length - 1, findValue);
System.out.println("元素第一次出现的位置（从0开始）：" + binaryResult);
}
private static int binarySearch(int[] nums, int start, int end, int findValue) {
if (start <= end) {
// 中间位置
int middle = (start + end) / 2;
// 中间的值
int middlevalue = nums[middle];
if (findValue == middlevalue) {
// 等于中值直接返回
return middle;
} else if (findValue < middlevalue) {
// 小于中值，在中值之前的数据中查找
return binarySearch(nums, start, middle - 1, findValue);
} else {
// 大于中值，在中值之后的数据中查找
return binarySearch(nums, middle + 1, end, findValue);
}
}
return -1;
}
}
2.9完数问题
题目：一个数如果恰好等于它的因子之和，这个数就称为"完数"。
例如6=1＋2＋3.编程找出1000以内的所有完数。
程序分析：关键是找出数的所以因子，注意因子包含1！不包含本身,但是1不是完数。
示例代码:
public class PerfectNumber{
public static void main(String args[]){
int i,j;
int sum=0;
for(i=1;i<=1000;i++) {
for(j=1;j
输出结果:
6
28
496
2.10杨辉三角
- 他的两条斜边都是数字1组成，其余的数等于他肩上的两数之和
- 每行数字左右对称，由1开始，逐渐增大
- 第n行的数字个数为n
- 第n行的数字之和为2^n-1;
示例代码:
public class TriangleArray {
public static void main(String[] args) {
final int NMAX = 10;
// allocate triangular array
int[][] odds = new int[NMAX + 1][];
for (int n = 0; n <= NMAX; n++)
odds[n] = new int[n + 1];
// fill triangular array
for (int n = 0; n < odds.length; n++)
for (int k = 0; k < odds[n].length; k++) {
int lotteryOdds = 1;
for (int i = 1; i <= k; i++)
lotteryOdds = lotteryOdds * (n - i + 1) / i;
odds[n][k] = lotteryOdds;
}
for (int[] row : odds)
{
for (int odd : row)
System.out.printf("%4d", odd);
System.out.println();
}
}
}
输出结果:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
未完待续…
