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