排序算法

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

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

思路：

案例：

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

 public static void BubbleSort(int[] arr){
        int temp = 0;
        boolean flag = false;// 表示是不是进行过交换
        for(int j=0;jarr[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(lpivot){
                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(leftl){
            quickSort(arr,l,right);
        }

    }

思路：

代码：

// 分+合方法
    public static void mergeSort(int[] arr,int left,int right,int []temp){
        if(left