算法的时间复杂度

算法的时间复杂度和时间频度

时间频度

时间频度：一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。[举例说明]

时间复杂度中T(n) 表达式中的常数项、低次项、系数，可以忽略（随着n不断变大）

时间复杂度

算法的空间复杂度

排序算法（SortAlgorithm）

冒泡排序

思路：

案例：

如果我们发现在其中的一趟排序中没有交换，可以提前结束交换（优化）
代码：

 public static void BubbleSort(int[] arr){
        int temp = 0;
        boolean flag = false;// 表示是不是进行过交换
        for(int j=0;j<arr.length-1;j++){
            for (int i = 0; i < arr.length-1-j; i++) {
                // 如果前面的数比后面的数大就交换
                if(arr[i]>arr[i+1]){
                    temp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = temp;
                    flag = true;
                }
            }
//            System.out.println("第"+ (j+1) + "次排序后的结果：");
//            System.out.println(Arrays.toString(arr));

            if(flag == false){
                System.out.println("没有发生交换了");
                break;
            }else{
                flag = false;
            }
        }
    }

选择排序

思路：


代码：

 public static void selectSort(int[] arr){

        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            int min = arr[i];
            for (int j = i+1; j < arr.length; j++) {
                if(min>arr[j]){
                    min = arr[j];
                    minIndex = j;
                }
            }
            if(minIndex!=i){
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }

    }

插入排序

思路：

最差的时候： 每个数都要迁移index-1位置，n越大就越久
代码：

 public static void insertSort(int[] arr){
        int insertVal = 0;
        int insertIndex = 0;
        for (int i = 1; i < arr.length; i++) {
            insertVal = arr[i];
            insertIndex = i-1;  // 待插入数前面的下标
            while(insertIndex>=0 && insertVal < arr[insertIndex]){ // 保证这个insertVal 不越界 && 插入的位置还没找到
                arr[insertIndex + 1] = arr[insertIndex];// 让值后移
                insertIndex--;
            }
            if(insertIndex+1 != i){
                arr[insertIndex + 1] = insertVal;// 插入的位置找到是insertIndex+1
//                System.out.println(Arrays.toString(arr));
            }
        }
    }

希尔排序(缩小增量排序)

思路：

示意图：

效果是尽量避免一个数移动多次的情况

代码：

public static void shellSort_Displacement(int[] arr) {
        // gap ：步长
        for (int gap = arr.length / 2; gap > 0; gap = gap / 2) {
            for (int i = gap; i < arr.length; i++) {
                // 从gap个元素，逐个对其所在的组进行直接插入排序
                int j = i;
                int temp = arr[j];
                if (arr[j] < arr[j - gap]) {
                    while (j - gap >= 0 && temp < arr[j - gap]) {
                        // 移动
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    // 退出while后找到了差插入的位置
                    arr[j] = temp;
                }

            }

//            System.out.println(Arrays.toString(arr));
        }


    }

public static void shellSort_Swap(int[]arr){
        // gap ：步长
        for (int gap = arr.length/2;gap>0;gap = gap/2  ) {
            int temp = 0;
            for (int i = gap; i < arr.length; i++) {
                for (int j = i-gap; j >=0 ; j-=gap) {
                    if(arr[j]>arr[j+gap]){
                        temp = arr[j];
                        arr[j] = arr[j+gap];
                        arr[j+gap] = temp;
                    }
                }
            }

//            System.out.println(Arrays.toString(arr));
        }
    }

快速排序

思路：

代码：

public static void quickSort(int []arr,int left,int right){
        int l  = left;
        int r = right;
        // 中轴
        int pivot = arr[(left+right)/2];
        int temp = 0;// 交换时候使用
        // while循环的目的是为了让比pivot小的去左边，pivot大的去右边
        while(l<r){
            // 在pivot左边一直找，找到大于等于pivot的值，才退出
            while(arr[l]<pivot){
                l+=1;
            }
            // 在pivot右边一直找，找到小于等于pivot的值，才退出
            while(arr[r]>pivot){
                r-=1;
            }
            // 若果l>=r成立，说明pivot的左右两边的值，已经按照左边全部小于pivot，右边全部大于pivot排好了
            if(l>=r){
                break;
            }

            // 交换
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            // 交换完了，arr[l] == pivot的值相等。前移一步
            if(arr[l] == pivot){
                r-=1;
            }

            // 交换完了，arr[r] == pivot的值相等，r后移
            if(arr[r] == pivot){
                l+=1;
            }
            // （前后移） 退出循环，没必要进行操作了
        }

        // 如果l == r,必须l++,r--; 否则会出现栈溢出
        if(l == r){
            l+=1;
            r-=1;
        }

        // 向左递归
        if(left<r){
            quickSort(arr,left,r);
        }

        // 向右递归
        if(right>l){
            quickSort(arr,l,right);
        }

    }

归并排序

思路：

代码：

// 分+合方法
    public static void mergeSort(int[] arr,int left,int right,int []temp){
        if(left<right){
            int mid = (left+right)/2;
            // 先向左递归分解
            mergeSort(arr,left,mid,temp);
            // 然后向右分解
            mergeSort(arr,mid+1,right,temp);
            // 每分解一次就合并一次
            merge(arr,left,mid,right,temp);
        }
    }

    /**
     *
     * @param arr    要排序的数组
     * @param left
     * @param mid     中间索引
     * @param right
     * @param temp      中转数组
     */
    public static void merge(int []arr,int left,int mid,int right,int []temp){
//        System.out.println("xxx");
        int i = left; // 初始化左边序列的初始索引
        int j =  mid+1;// 初始化右边序列的初始索引
        int t = 0;

        //(1)
        // 先把左右两边的（有序）的数据按照规则填到数组里面
        // 直到两边的有序序列有一边处理完为止
        while(i<=mid && j<=right){
            // 左边有序序列的当前元素小于等于右边元素
            if(arr[i] <= arr[j]){
                temp[t++] = arr[i++];
            }else{
                temp[t++] = arr[j++];
            }

        }

        //(2)
        // 把有剩余数据的一边数据依次完全填充到temp

        while(i<=mid){
            temp[t++] = arr[i++];
        }

        while(j<=right){
            temp[t++] = arr[j++];
        }

        //(3)
        // 将temp数组的元素拷贝到arr
        // 并不是每次都拷贝所有数据到原来的数组 从下往治
        t = 0;
        int tempLeft = left;
//        System.out.println("tempLeft = "+ tempLeft+",right = "+right);
        while(tempLeft <= right){
            arr[tempLeft++] = temp[t++];
        }


    }