<
java排序
>
上一篇

netty 下一篇

linux

空间复杂度和时间复杂度（二者合称算法的复杂度）

时间复杂度

[time][time] 时间复杂度并不是程序执行的时间，而是算法执行语句的次数。如果有多个算法，可以通过计算时间复杂度判断该算法的执行效率。

常见的时间复杂度有：

常数阶O(1),

对数阶O(log2 n),

线性阶O(n),

线性对数阶O(n log2 n),

平方阶O(n^2)，

立方阶O(n^3)

k次方阶O(n^K),

指数阶O(2^n)。

随着n的不断增大，时间复杂度不断增大，算法花费时间越多。

计算方法：

（1）选取相对增长最高的项，

（2）最高项前面的系数化为1，

（3）如果是常数项，则记做为O(1)。

如：f(n) = 2* n^3 + 2n + 100 则记做为 O(n)=n^3

空间复杂度

临时占用存储空间大小

一个算法如果追求较好的时间复杂度时，空间复杂度会变差，反之亦然。

Java排序

1.冒泡排序:时间复杂度T(n)=O(n*n)

比较相连的两个元素，把大的元素换到最右边。

第一趟排完，最后的一定是最大的元素，所以第二趟排序不需要比较最后一个数。

同理第三趟也不需要比较倒数第二个数，第j趟不需要比较j-1个数。

每一趟比较次数-1.

 @Test
    public void bubbleSort(){//冒泡排序
        private int [] arra = {6,3,8,2,9,1};
        int temp;
        for (int i =0;i<arra.length -1;i++){//外层控制多少趟
                for (int j =0 ;j<arra.length -i-1;j++){//内层控制每趟多少次
                    if(arra[j]>arra[j+1]){
                        temp = arra[j];
                        arra[j] = arra[j+1];
                        arra[j+1] = temp;
                    }
                }
            for(int m:arra){//每趟排序之后输出
                System.out.print(m);
            }
            System.out.println("==============");
        }
    }

结果是：

第1趟排序之后：362819==============

第2趟排序之后：326189==============

第3趟排序之后：231689==============

第4趟排序之后：213689==============

第5趟排序之后：123689==============

2.快速排序：

在要排序的数组array中选择一个中间值做为key（array[0]），通过一趟排序之后使数组分成两部分， 以key为中心，key的左边比key小，key的右边比key大，重复排序，直到有顺序。

一趟排序的方法：时间复杂度O(n)=(nlogn)

定义i=0,j=array.length-1,i是第一个数的下标，j是最后一个数的下标 从右往左找，找到第一个小于key的数，标记为array[j], 从左往右找，找到第一个大于key的数，标记为array[i], 如果i<j, 将array[i]与 array[j]交换， 重复这个过程，直到i=j， 然后交换array[i]和key.

在一趟排序之后，分别递归调用排序方法对key左右两边进行排序 


@Test
    public void testQuickSort(){
        private int [] arra = {6,3,8,2,9,1};
        System.out.println(Arrays.toString(arra));
        if (arra.length>0){
            quickSort(arra, 0, arra.length - 1);
        }
        System.out.println(Arrays.toString(arra));
    }

    public void quickSort(int a[],int low,int high){
        if (low > high){//递归算法的出口
            return;
        }
        //存
        int i = low;
        int j = high;
        int key = a[low];
        //完成一趟排序
        while (i < j){
            while (i< j && a[j] > key){//从右往左找到小于key的数据
                j --;
            }
            while (i<j && a[i] <= key ){//从左往右找到大于key的数据
               i ++;
            }
            if (i<j){//交换
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
        //调整key的位置
        int temp = a[i];
        a[i] = a[low];
        a[low] = temp;
        quickSort(a, low , i -1);//对key左面的快排
        quickSort(a, i+1 , high);//对key右面的快排
    }

结果： [6, 3, 8, 2, 9, 1]

[1, 2, 3, 6, 8, 9]

3.选择排序

4.二分（折半）算法查找一个元素target是否在数组内，注意：数组必须是有序的，且升续

将数组转换成有序数组，每次取数组中间值array[mid]，比较target和array[mid]的值大小，如果target比中间值大，就从中间值右部分比较，反正则在左半边比较。递归循环上述过程。

注意：二分（折半）要求数组有序，查找快，比较次数少，平均性能好；缺点是插入困难，且要求数组有序。

适用于频繁查询而不经常变动的情况。

   //返回值状态表示是否存在当前值
   public boolean testZB(int [] array,int left,int right,int target){
        Arrays.sort(array);//先给数组排序
        if(left > right || array[right]< target|| array[left]>target){
           return false;
        }
        System.out.println("数组："+ Arrays.toString(array));
        int mid = (right+left)/2;
        if(array[mid] == target){
            System.out.println("mid："+ mid);
            return true;
        }else if(array[mid] > target){
            return testZB(array, left, mid - 1, target);
        }else {// if(array[mid] < target)
            return testZB(array, mid + 1, right, target);
        }
    }

    //测试方法
    @org.junit.Test
    public void test1(){
        int a []= {9,2,1,4,5,3,6,8,7};
        boolean is = testZB(a, 0, a.length - 1, 4);//注意是长度-1
        System.out.println("存在？: "+(is));
    }

[time]：https://blog.csdn.net/halotrriger/article/details/78994122

Top
Foot