算法

算法

• n!的弱上界是n^n，因此增长速度非常快，这意味着单位时间内可求解的问题很小，换言之，超慢
• 2^n这样的指数函数增长非常快，这种算法可以认为超慢
• o(n2)和o(n 3)增长很快，算法很慢，至少优化到nlgn,o(n2)的有冒泡排序，直接插入排序，选择排序
• nlgn可以认为是及格的算法吧，一般分治法可以缩小层数为lgn,而每层的复杂度一般为o(n)，例如归并排序算法、快速排序算法
• o(n)叫做线性算法，这种算法比较优香。或者问题本身比较简单，比如求连续求和最大子数组的线性解
• o(sqrt(n)）当然比o(n）更快，不是没有，但这种很少
• lgn就是很优秀的算法了，比如二分查找法，但是这种算法往往对输入数据的格式是有要求的，二分查找要求输入数据有序

选择排序

冒泡排序：
for (int i=0;i for (int j = 0;j int temp;
if(arr[j]>arr[j+1])
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
快速排序
public class QuickSort {
public static void main(String[] args) {
int[] arr= getRandom(5,9,1);
System.out.println(Arrays.toString(arr));
quickSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
//三个区间
public static int[] partition2(int[] arr,int begin,int end){

    int pivot =arr[begin];<br />        int left = begin+1;<br />        int eq=left;<br />        int right = end;
    while (left<=right){<br />            if (arr[left]<pivot){<br />                int temp = arr[left];<br />                arr[left] = arr[eq];<br />                arr[eq]=temp;
            left++;<br />                eq++;<br />            }else if(arr[left]==pivot){<br />                left++;<br />            }else if(arr[left]>pivot){<br />                int temp = arr[left];<br />                arr[left] = arr[right];<br />                arr[right]=temp;<br />                right--;<br />            }<br />        }<br />        arr[begin]=arr[eq-1];<br />        arr[eq-1]=pivot;<br />        int[] result={eq-2,right+1};<br />        return result;<br />    }<br />    public static int partition(int[] arr,int begin,int end){
    //优化：三值取中，， begin mid end 三个值 选取大小为中间的那个<br />        int mid = begin+((end-begin)>>1);<br />        int midValue=0;<br />        if(arr[begin]<arr[end]&&arr[end]>arr[mid]){<br />            midValue=end;<br />        }else if (arr[begin]>arr[end]&&arr[begin]>arr[mid]){<br />            midValue=begin;<br />        }else if(arr[mid]>arr[begin]&&arr[mid]>arr[end]){<br />            midValue=mid;<br />        }<br />        int temp = arr[midValue];<br />        arr[midValue]=arr[begin];<br />        arr[begin]=temp;
    int pivot=arr[begin];<br />        int left=begin+1;<br />        int right=end;<br />        while (left<=right) {<br />            while (left<=right&&arr[left] <= pivot) {<br />                left++;<br />            }<br />            while (left<=right&&arr[right] > pivot) {<br />                right--;<br />            }<br />            if (left<right) {<br />                temp = arr[left];<br />                arr[left] = arr[right];<br />                arr[right] = temp;<br />            }<br />        }<br />        arr[begin]=arr[right];<br />        arr[right]=pivot;<br />        return right;<br />    }<br />    public static void quickSort(int[] arr,int begin,int end){<br />        if(begin<end) {<br />            int index = partition(arr, begin, end);<br />            quickSort(arr, begin, index - 1);<br />            quickSort(arr, index + 1, end);
        /*int[] q=partition2(arr,begin,end);<br />            quickSort(arr,begin,q[0]);<br />            quickSort(arr,q[1],end);*/<br />        }<br />    }
public static int[] getRandom(int length,int max,int min){<br />        if (length<0||max<min)<br />        {<br />            return null;<br />        }<br />        Random r= new Random();<br />        int[] arr= new int[length];
    for (int i =0;i<length;i++)<br />        {<br />            arr[i]=r.nextInt(max)+min;<br />        }<br />        return arr;<br />    }<br />}