java基础算法题
一、冒泡排序
[java] view plain
package sort.bubble;
import java.util.Random;
/**
* 依次比较相邻的两个数，将小数放在前面，大数放在后面
* 冒泡排序，具有稳定性
* 时间复杂度为O（n^2）
* 不及堆排序，快速排序O（nlogn，底数为2）
* @author liangge
*
*/
public class Main {
public static void main(String[] args) {
Random ran = new Random();
int[] sort = new int[10];
for(int i = 0 ; i < 10 ; i++){
sort[i] = ran.nextInt(50);
}
System.out.print("排序前的数组为");
for(int i : sort){
System.out.print(i+" ");
}
buddleSort(sort);
System.out.println();
System.out.print("排序后的数组为");
for(int i : sort){
System.out.print(i+" ");
}
}
/**
* 冒泡排序
* @param sort
*/
private static void buddleSort(int[] sort){
for(int i=1;i<sort.length;i++){
for(int j=0;j<sort.length-i;j++){
if(sort[j]>sort[j+1]){
int temp = sort[j+1];
sort[j+1] = sort[j];
sort[j] = temp;
}
}
}
}
}
二、选择排序
[java] view plain
package sort.select;
import java.util.Random;
/**
* 选择排序
* 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，
* 顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
* 选择排序是不稳定的排序方法。
* @author liangge
*
*/
public class Main {
public static void main(String[] args) {
Random ran = new Random();
int[] sort = new int[10];
for (int i = 0; i < 10; i++) {
sort[i] = ran.nextInt(50);
}
System.out.print("排序前的数组为");
for (int i : sort) {
System.out.print(i + " ");
}
selectSort(sort);
System.out.println();
System.out.print("排序后的数组为");
for (int i : sort) {
System.out.print(i + " ");
}
}
/**
* 选择排序
* @param sort
*/
private static void selectSort(int[] sort){
for(int i =0;i<sort.length-1;i++){
for(int j = i+1;j<sort.length;j++){
if(sort[j]<sort[i]){
int temp = sort[j];
sort[j] = sort[i];
sort[i] = temp;
}
}
}
}
}
三、快速排序
[java] view plain
package sort.quick;
/**
* 快速排序 通过一趟排序将要排序的数据分割成独立的两部分， 其中一部分的所有数据都比另外一部分的所有数据都要小，
* 然后再按此方法对这两部分数据分别进行快速排序， 整个排序过程可以递归进行，以此达到整个数据变成有序序列。
* @author liangge
*
*/
public class Main {
public static void main(String[] args) {
int[] sort = { 54, 31, 89, 33, 66, 12, 68, 20 };
System.out.print("排序前的数组为：");
for (int data : sort) {
System.out.print(data + " ");
}
System.out.println();
quickSort(sort, 0, sort.length - 1);
System.out.print("排序后的数组为：");
for (int data : sort) {
System.out.print(data + " ");
}
}
/**
* 快速排序
* @param sort 要排序的数组
* @param start 排序的开始座标
* @param end 排序的结束座标
*/
public static void quickSort(int[] sort, int start, int end) {
// 设置关键数据key为要排序数组的第一个元素，
// 即第一趟排序后，key右边的数全部比key大，key左边的数全部比key小
int key = sort[start];
// 设置数组左边的索引，往右移动判断比key大的数
int i = start;
// 设置数组右边的索引，往左移动判断比key小的数
int j = end;
// 如果左边索引比右边索引小，则还有数据没有排序
while (i < j) {
while (sort[j] > key && j > start) {
j--;
}
while (sort[i] < key && i < end) {
i++;
}
if (i < j) {
int temp = sort[i];
sort[i] = sort[j];
sort[j] = temp;
}
}
// 如果左边索引比右边索引要大，说明第一次排序完成，将sort[j]与key对换，
// 即保持了key左边的数比key小，key右边的数比key大
if (i > j) {
int temp = sort[j];
sort[j] = sort[start];
sort[start] = temp;
}
//递归调用
if (j > start && j < end) {
quickSort(sort, start, j - 1);
quickSort(sort, j + 1, end);
}
}
}
[java] view plain
/**
* 快速排序
*
* @param a
* @param low
* @param high
* voidTest
*/
public static void kuaisuSort(int[] a, int low, int high)
{
if (low >= high)
{
return;
}
if ((high - low) == 1)
{
if (a[low] > a[high])
{
swap(a, low, high);
return;
}
}
int key = a[low];
int left = low + 1;
int right = high;
while (left < right)
{
while (left < right && left <= high)// 左边向右
{
if (a[left] >= key)
{
break;
}
left++;
}
while (right >= left && right > low)
{
if (a[right] <= key)
{
break;
}
right--;
}
if (left < right)
{
swap(a, left, right);
}
}
swap(a, low, right);
kuaisuSort(a, low, right);
kuaisuSort(a, right + 1, high);
}
四、插入排序
[java] view plain
package sort.insert;
/**
* 直接插入排序
* 将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据
* 算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。
*/
import java.util.Random;
public class DirectMain {
public static void main(String[] args) {
Random ran = new Random();
int[] sort = new int[10];
for (int i = 0; i < 10; i++) {
sort[i] = ran.nextInt(50);
}
System.out.print("排序前的数组为");
for (int i : sort) {
System.out.print(i + " ");
}
directInsertSort(sort);
System.out.println();
System.out.print("排序后的数组为");
for (int i : sort) {
System.out.print(i + " ");
}
}
/**
* 直接插入排序
*
* @param sort
*/
private static void directInsertSort(int[] sort) {
for (int i = 1; i < sort.length; i++) {
int index = i - 1;
int temp = sort[i];
while (index >= 0 && sort[index] > temp) {
sort[index + 1] = sort[index];
index--;
}
sort[index + 1] = temp;
}
}
}
顺便添加一份，差不多的
[java] view plain
public static void charuSort(int[] a)
{
int len = a.length;
for (int i = 1; i < len; i++)
{
int j;
int temp = a[i];
for (j = i; j > 0; j--)//遍历i之前的数字
{
//如果之前的数字大于后面的数字，则把大的值赋到后面
if (a[j - 1] > temp)
{
a[j] = a[j - 1];
} else
{
break;
}
}
a[j] = temp;
}
}
把上面整合起来的一份写法：
[java] view plain
/**
* 插入排序:
*
*/
public class InsertSort {
public void sort(int[] data) {
for (int i = 1; i < data.length; i++) {
for (int j = i; (j > 0) && (data[j] < data[j - 1]); j--) {
swap(data, j, j - 1);
}
}
}
private void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
五、顺便贴个二分搜索法
[java] view plain
package search.binary;
public class Main {
public static void main(String[] args) {
int[] sort = {1,2,3,4,5,6,7,8,9,10};
int mask = binarySearch(sort,6);
System.out.println(mask);
}
/**
* 二分搜索法，返回座标，不存在返回-1
* @param sort
* @return
*/
private static int binarySearch(int[] sort,int data){
if(data<sort[0] || data>sort[sort.length-1]){
return -1;
}
int begin = 0;
int end = sort.length;
int mid = (begin+end)/2;
while(begin <= end){
mid = (begin+end)/2;
if(data > sort[mid]){
begin = mid + 1;
}else if(data < sort[mid]){
end = mid - 1;
}else{
return mid;
}
}
return -1;
}
}
‘贰’ Java算法题：判断并输出101-200中所有素数，代码中单等号与双等号的区别
这是很基础的问题
单= 是赋值运算, 把后面的值赋值给前面的参数
双= 是关系运算, 比较前后两个参数是否相同
注意如果???处, 用单等, 就是赋值运算, 将ture 赋值 给 flag, 所以if中会一直是true, 也会一直执行if中的代码
双== 就是比较了啊, 结果是真 才会执行if中代码
‘叁’ java算法题
快速排序一般来说 比较适用于数据量大的情况
public class QuickSoft {
private void swap(int a[],int i,int j)
{
int tmp=a[i];
a[i]=a[j];
a[j]=tmp;
}
private int partition(int a[],int p,int r)
{
int point = a[r];
//将小于等于point的元素移到左边区域
//将大于point的元素移到右边区域
int index=p;
for (int i = index; i < r; ++ i) {
if (a[i]-point <= 0) {
swap(a, index++, i);
}
}
swap(a,index,r);
return index;
}
public void qsort(int a[],int p,int r)
{
if(p< r)
{
//确定拆分点，并对数组元素进行移动
//这是快速排序算法的关键步骤
int q=partition(a,p,r);
//对左半段排序
qsort(a,p,q-1);
//对右半段排序
qsort(a,q+1,r);
}
}
public static void main(String[] args) {
//声明一个类
QuickSoft ms=new QuickSoft();
int len=10;
int a[]=new int[len];
//初始化a数组
System.out.println("原始数组如下：");
for(int i=0;i< a.length;i++)
{
//产生a.length个随机数
a[i] = (int)(Math.random()*100000);
System.out.println(a[i]);
}
System.out.println("---------------------");
System.out.println("第一次分组后");
ms.partition(a,0,len-1);
for(int i=0;i< a.length;i++)
{
System.out.println(a[i]);
}
System.out.println("---------------------");
//快速排序
ms.qsort(a, 0, len-1);
System.out.println("排序后的数组如下：");
for(int i=0;i< a.length;i++)
{
System.out.println(a[i]);
}
}
}
‘肆’ Java计算题，判断是否大于零，输出乘积
publicstaticvoidmain(String[]args){
//创建Scanner对象System.in表示标准化输出，也就是键盘输出
Scannersc=newScanner(System.in);
intscan_count=1;
intscan_value=0;
intproct_result=0;
Stringstr_temp="";
StringBuilderstringBuilder=newStringBuilder();
while(scan_count!=6){
System.out.println("第"+scan_count+"次输入开始:");
Stringstr=sc.next();
try{
scan_value=Integer.parseInt(str);
if(scan_value>0){
stringBuilder.append("[第"+scan_count+"次输入值]"+scan_value+"大于零！");
}elseif(scan_value==0){
stringBuilder.append("[第"+scan_count+"次输入值]"+scan_value+"等于零！");
}else{
stringBuilder.append("[第"+scan_count+"次输入值]"+scan_value+"小于零！");
}
}catch(Exceptione){
System.out.println("输入非数字,程序结束！");
return;
}
if(scan_count==1){
proct_result=scan_value;
str_temp=str;
}else{
str_temp=str_temp+"*"+str;
}
proct_result=proct_result*scan_value;
stringBuilder.append(str_temp+"="+proct_result+"
");
scan_count++;
}
System.out.println(stringBuilder.toString());
}
‘伍’ JAVA算法题
//第一种方法
publicstaticvoidmethod1(int[]array){
//先排序
for(inti=0;i<array.length;i++){
for(intj=i+1;j<array.length;j++){
if(array[i]>array[j]){
intc=array[i];
array[i]=array[j];
array[j]=c;
}
}
}
//第0位不变，2n位与2n-1位互换
for(inti=2;i<array.length;i+=2){
intc=array[i];
array[i]=array[i-1];
array[i-1]=c;
}
}
上面的方法先将数组排序，然后再把除0外的第2n位与2n-1位互换，这样可以保证奇数位的数总比两边的数字大，可以满足公式
//第二种方法
publicstaticvoidmethod2(int[]array){
//直接按0,2,1,4,3,6,5,8,7...的顺序排序
for(inti=0;i<array.length;i=nextIndex(i)){
for(intj=nextIndex(i);j<array.length;j=nextIndex(j)){
if(array[i]>array[j]){
intc=array[i];
array[i]=array[j];
array[j]=c;
}
}
}
}
publicstaticintnextIndex(inti){
returni==0?i+2:(i%2==0?i-1:i+3);
}
第二种方法在排序时直接采用除0外的第2n位与2n-1位互换的顺序排序
publicstaticvoidmain(String[]args){
int[]array=newint[]{1,5,3,4,7,5};
method1(array);
for(inti=0;i<array.length;i++){
System.out.print(i==0?"":(i%2==0?">=":"<="));
System.out.print(array[i]);
}
}结果：1<=4>=3<=5>=5<=7
虽然结果与例子不一样，但也能满足公式需求
‘陆’ 会java算法的，来教一下小弟这个题目怎么写
importjava.util.Scanner;
publicclasstest{
publicstaticvoidmain(String[]args){
Scannerreader=newScanner(System.in);
Stringcode=reader.nextLine();
Stringtemp[]=code.split("");
//System.out.print(code);
ComplexNumbera=newComplexNumber(Integer.parseInt(temp[1]),Integer.parseInt(temp[2]));
ComplexNumberb=newComplexNumber(Integer.parseInt(temp[3]),Integer.parseInt(temp[4]));
//System.out.print(aaa.toString());
if(temp[0].intern()=="*".intern())System.out.print(ComplexNumber.multiply(a,b));
elseif(temp[0].intern()=="+".intern())System.out.print(ComplexNumber.add(a,b));
}
}
文件目录格式
‘柒’ 一道java算法题提供了正确代码，不知道是不是我理解错误运行结果并不是最大值
首先理解下题意，关键是连续的子数组，比如{1，2，-1} ，连续的子数组包括{1}、{2}、{-1}、{1，2}、{2，-1}、{1，2，-1}
其次是求各子数组和的最大值，上面的算法求最大值分两部分，循环遍历所有值
curSum ：用于某一个子数组的累加和
curMaxSum：用于记录历史最大累加和
上面算法的start和end其实没用，本意是找出具体子数组，但上面算法部分情况下是无法实现的
@Test
public void test(){
// int[] num = {1,-2,3,10,-4,7,2,-5};
//int[] num = {1,-2,3,10,-4,10,2,-5};
int[] num = {-1,-2,3,4,-5,-6,-7};
System.out.println(maxSum(num));
}
public int maxSum(int[] num){
int curSum = 0;
int curMaxSum = -99999999;
int finalStart = 0;
int finalEnd = 0;
int start = 0;
for(int i=0;i<num.length;i++){
if(curSum<=0){
curSum = num[i];
start = i;
}
else{
curSum += num[i];
}
if(curSum>curMaxSum){
finalStart = start;
finalEnd = i;
curMaxSum = curSum;
}
}
for(int i = finalStart;i<=finalEnd;i++){
System.out.println(num[i]);
}
return curMaxSum;
}
‘捌’ java算法问题 排列组合 给定一组字符串,产生所有可能的集合
这是我写的一个取组合的方法：
package Combination.c3;
import java.util.ArrayList;
import java.util.List;
public class Combinations {
/*
* 设有n个元素，组合数量有2的n次方种。
* 对 0 到 2的n次方-1 中的每个数，考察其二进制位形式，位数为1代表相应元素加入
* 到组合，0则不加入该元素至组合。
*
* 取组合方法
* 参数： list ---- 原始数组
* 返回： 包含所有组合数组的数组
*/
public static List<List<Object>> getCombinations(List<Object> list) {
List<List<Object>> result = new ArrayList<List<Object>>();
long n = (long)Math.pow(2,list.size());
List<Object> combine;
for (long l=0L; l<n; l++) {
combine = new ArrayList<Object>();
for (int i=0; i<list.size(); i++) {
if ((l>>>i&1) == 1)
combine.add(list.get(i));
}
result.add(combine);
}
return result;
}
//测试
public static void main(String[] args) {
ArrayList<Object> list = new ArrayList<Object>();
list.add("a");
list.add("b");
list.add("c");
list.add("d");
list.add("e");
list.add("f");
list.add("g");
list.add("h");
list.add("i");
list.add("j");
List<List<Object>> result = getCombinations(list);
System.out.println(list.toString());
System.out.println(result.toString());
}
}
‘玖’ java基础习题里的复利计算公式
设每年购买为P，购买n年，利率为r，则第n年结束时，最后一年购买的P，变成了P(1+r)
倒数第二年：P(1+r)²，第一年 P(1+r)的n-1次方
这是个等比数列，等比数列求和总会吧？
Sn = a1 * (1-q的n次方) / (1-q)
这里q = 1+r
= P((1+r) + (1+r)²...+(1+r)的n-1次方) = P((1+r)^n-1) / (1+r -1) = P((1+r)^n-1)/r