算法（四）、时间复杂度、排序、查找
一、时间复杂度
1、 常数阶O(1)
package test;public class CCC {public static void main(String[] args) {int sum=100;int n=100;sum = sum+n;System.out.println(sum);}} 2、线性阶O(n)
package test;public class CCC { public static void main(String[] args) { int sum=0; int n=100; for(int i=1;i<=n;i++){ sum = sum+i; } System.out.println(sum); }} 3、 对数阶O(Log2 n)
package test;public class CCC { public static void main(String[] args) { int n=100; for(int i=1;i<=n;i++){ i=i*2; System.out.println(i); } }} 4、 平方阶O(n2)
例1：
int sum=0;int n=100;for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ sum = sum+i; }}System.out.println(sum);
例2：
int n=100;for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++){ System.out.println(j); }} 当i=1时执行n次，i=2时执行n-1次，......当i=n-1时执行了1次，总共执行的次数为：
因此为时间复杂度为：O(n2)
**5、 时间复杂对耗费时间由小到大排序：**
二、常用算法
总结了以下几种常用算法：找出最大值、冒泡排序、选择排序、快速排序、插入排序、希尔排序
2、遍历数组，找出数组中的最大值
public class Abc{ int[] b=new int[10]; void B(){ for(int i=0;i =max){ max=b[i]; } } System.out.println("数组的最大值为："+max); }} 3、冒泡排序
import java.util.Arrays;public class Def { public static void DDD(){ int[] d={15,6,3,89,54,34}; System.out.println("原始数组为："+Arrays.toString(d)); for(int i=0;i<=d.length;i++){ for(int j=0;j d[j+1]){ int t=d[j]; d[j]=d[j+1]; d[j+1]=t; } } } System.out.println("冒泡后数组为："+Arrays.toString(d)); }} 4、选择排序
package test;public class CCC {public static void main(String[] args) {int[] abc={1,76,54,100,65,34,2,19,40};System.out.print("快速排序前数组为：");for(int num:abc){System.out.print(num+" ");}for(int i=1;i 5、快速排序
package cn.qiuuuu.test;public class sortQuick { public static void sort(int array[],int low,int high){ int i,j; int index; if(low>=high){ return; } i=low; j=high; index=array[i]; while(i =index){ j--; } if(i 6、插入排序
public static int[] insertSort(int[] a){ for (int i = 1; i < a.length; i++) { //待插入元素 int temp = a[i]; int j; for (j = i-1; j>=0; j--) { //将大于temp的往后移动一位 if(a[j]>temp){ a[j+1] = a[j]; }else{ break; } } a[j+1] = temp;//插入进来 } for(int i=0;i 7、希尔排序
int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,33,85,29};int d = a.length/2; //设置增量while(true){ for(int i=0;i a[j+d]){ temp=a[j]; a[j]=a[j+d]; a[j+d]=temp; } }}if(d==1){break;} d--; } 三、查找算法
1、二分查找/折半查找
public class BinarySearch { public static void main(String[] args){ int[] arr={1,2,3,4,5}; Arrays.sort(arr); binarySearch(arr,4,0,arr.length-1); System.out.println(binarySearch(arr,4,0,arr.length-1)); System.out.println(arr[binarySearch(arr,4,0,arr.length-1)]); } public static int binarySearch(int[] arr,int key,int left,int right){ if(key arr[right]||left>right){ return -1; } int middle=(left+right)/2; if(arr[middle] key){ return binarySearch(arr,key,left,middle-1); }else{ return middle; } }}
2、