排序算法 | Hexo

[TOC]

冒泡排序

public class bubbleSort {
    public static int[] BubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
            }
        }
        return arr;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {21, 34, 56, 11, 2};
        BubbleSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }

    }
}

快速排序

public class QuickSort {

    public static void quickSort(int arr[], int left, int right) {
        if (left >= right) {
            return;
        }
        int index = partition(arr, left, right);
        quickSort(arr, left, index - 1);
        quickSort(arr, index + 1, right);
    }

    public static int partition(int[] arr, int left, int right) {
        int key = arr[left];
        while (left < right) {
            while (right > left && arr[right] >= key) {
                right--;
            }
            arr[left] = arr[right];
            while (right > left && arr[left] < key) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = key;
        return left;
    }

    // 测试案例
    public static void main(String[] args) {
        int[] arr = {49, 38, 65, 97, 76, 13, 27, 49};

        quickSort(arr, 0, arr.length - 1);

        for (int i : arr) {
            System.out.print(i + ",");
        }
    }
}

时间复杂度推导

我们用T(n)来表示时间复杂度，有：

$T(n)= \left\{\begin{matrix} 2T(n/2)+n,n>1;\\ 0,n=1; \end{matrix}\right.$

解这个递推公式：

$T(n)= 2T(\frac{n}{2})+n;$

有 $T(\frac{n}{2})= 2T(\frac{n}{4})+\frac{n}{2};$ )代入上一个公式有 $T(n)= 4T(\frac{n}{4})+2n;$

有 $T(\frac{n}{4})= 2T(\frac{n}{8})+\frac{n}{4};$ )代入上一个公式有 $T(n)= 8T(\frac{n}{8})+3n;$

…

最后一层递归有 $T(\frac{n}{2^{k}})= 2T(\frac{n}{2^{k+1}})+\frac{n}{2^{k}};$ )代入上一个公式有 $T(n)= 2^{k}T(\frac{n}{2^{k}})+kn;$

已知最后一层递归时操作次数为1， $\frac{n}{2^{k}}=1$ )，有 $k=log_{2}n$

带入公式 $T(n)= 2^{k}T(\frac{n}{2^{k}})+kn$ )得 $T(n)= nT(1)+{log_{2}}n*n;$

有T(1)=0;

所以 $T(n)= n{log_{2}}n$ 即：O(nlgn);

看着好复杂，我的简单理解是，每一轮复杂度都是n，每一轮劈两半，能劈2^x=n x=logn轮，总复杂度就是nlogn

最好情况，每层左右子树都可以平均分摊，层高是n对2取log，否则倒叙输入，每层左子树只能分担一个，退化为层高n的树

插入排序

public class InsertSort {
    public static int[] insertSort(int[] arr) {
        int temp, j;
        for (int i = 1; i < arr.length; i++) {
            temp = arr[i];
            for (j = i - 1; j >= 0 && temp < arr[j]; j--) {
                arr[j + 1] = arr[j];
            }// 1 2 2 5 2
            arr[j + 1] = temp;
        }
        return arr;
    }

    public static void main(String[] args) {
      //  Set<Integer> set=new HashSet<>();
        int[] arr = {3, 1, 2, 5};
        insertSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

归并排序

public class test {
    public static int[] sort(int[] a,int low,int high){
        int mid = (low+high)/2;
        if(low<high){
            sort(a,low,mid);
            sort(a,mid+1,high);
            //左右归并
            merge(a,low,mid,high);
        }
        return a;
    }

    public static void merge(int[] a, int low, int mid, int high) {
        int[] temp = new int[high-low+1];
        int i= low;
        int j = mid+1;
        int k=0;
        // 把较小的数先移到新数组中
        while(i<=mid && j<=high){
            if(a[i]<a[j]){
                temp[k++] = a[i++];
            }else{
                temp[k++] = a[j++];
            }
        }
        // 把左边剩余的数移入数组
        while(i<=mid){
            temp[k++] = a[i++];
        }
        // 把右边边剩余的数移入数组
        while(j<=high){
            temp[k++] = a[j++];
        }
        // 把新数组中的数覆盖nums数组
        for(int x=0;x<temp.length;x++){
            a[x+low] = temp[x];
        }
    }

    public static void main(String[] args) {
        int[] arr={2,1,5,4};
        sort(arr,0,arr.length-1);
        for(int a:arr)
        System.out.println(a);

    }

}

堆排序

建堆的时间复杂度

首先要理解怎么计算这个堆化过程所消耗的时间，可以直接画图去理解；

        假设高度为k，则从倒数第二层右边的节点开始，这一层的节点都要执行子节点比较然后交换（如果顺序是对的就不用交换）；倒数第三层呢，则会选择其子节点进行比较和交换，如果没交换就可以不用再执行下去了。如果交换了，那么又要选择一支子树进行比较和交换；

        那么总的时间计算为：s = 2^( i - 1 )  *  ( k - i )；其中 i 表示第几层，2^( i - 1) 表示该层上有多少个元素，( k - i) 表示子树上要比较的次数，如果在最差的条件下，就是比较次数后还要交换；因为这个是常数，所以提出来后可以忽略；

        S = 2^(k-2) * 1 + 2^(k-3)*2.....+2*(k-2)+2^(0)*(k-1)  ===> 因为叶子层不用交换，所以i从 k-1 开始到 1；

        这个等式求解，我想高中已经会了：等式左右乘上2，然后和原来的等式相减，就变成了：

        S = 2^(k - 1) + 2^(k - 2) + 2^(k - 3) ..... + 2 - (k-1)

        除最后一项外，就是一个等比数列了，直接用求和公式：S = {  a1[ 1-  (q^n) ] }  / (1-q)；

        S = 2^k -k -1；又因为k为完全二叉树的深度，所以 (2^k) <=  n < (2^k  -1 )，总之可以认为：k = logn （实际计算得到应该是 log(n+1) < k <= logn ）;

        综上所述得到：S = n - longn -1，所以时间复杂度为：O(n)

更改堆元素后重建堆时间：O(nlogn)

       推算过程：

      1、循环  n -1 次，每次都是从根节点往下循环查找，所以每一次时间是 logn，总时间：logn(n-1) = nlogn  - logn ；

public class HeapSort {
    public static void heapSort(int[] arr) {
        for (int i = arr.length / 2 - 1; i >= 0; i--)
            downjust(arr, i, arr.length);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " :");
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            swap(arr, i, 0);
            downjust(arr, 0, i);
        }
    }

    private static void downjust(int[] arr, int low, int high) {
        int i = low, j = i * 2 + 1, temp = arr[i];
        while (j < high) {
            if (j + 1 < high && arr[j] < arr[j + 1])
                j++;
            if (arr[j] > temp) {
                swap(arr, i, j);
                i = j;
                j = i * 2 + 1;
            } else break;
        }

    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;

    }

    public static void main(String[] args) {
        int[] nums = {110, 16, 7, 3, 20, 17, 8};
        heapSort(nums);
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }
}

时间复杂度：

选择排序

public class SelectSort {
    //选择排序：每次从待排序的元素中选出最小值
    //选择排序：每次从待排序的元素中选出最小值  
    public static void selectionSort(int[] arr){
        for(int i = 0; i < arr.length - 1; i++){
            int min = i;
            for(int j = i + 1; j < arr.length; j++){
                //将a[i]和a[i+1...N-1]中的最小元素交换
                if(arr[j] < arr[min]){//升序排列
                    min = j;
                }
            }
            if(min != i){
                int temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }
        }
    
    }

    public static void main(String[] args) {
        int[] array = {3,2,4,1,5,0};
        selectionSort(array);
        System.out.println(array);
    }
}

希尔排序

public class shellSort {
    public static void main(String[] args) {
        int[] arr = new int[]{1,8,3,4,2,0,5,6,3,2,8,9};
        shell(arr);
        System.out.println(Arrays.toString(arr));

    }

    /**
     * 希尔排序
     * @param arr 要排序的数组
     */
    public static void shell(int[] arr){

        //希尔排序实际上是直接插入排序的升级版本，在直接插入排序的算法中，如果越到后面突然出现某个比较小的值
        //这个时候排序的步骤就越长，希尔排序就是为了解决这个问题，先大致的排一下，然后拍的过程中用的是直接插入排序算法

        //首先计算步长
        for(int d = arr.length/2;d>0;d = d/2){
            //开始直接排序算法
            //先来一轮直接排序
            for(int i = d;i < arr.length;i++){
                //然后开始交换
                for(int j = i - d;j >=0; j = j-d){
                    if(arr[j] > arr[j+d]){
                        int temp = arr[j];
                        arr[j] = arr[j+d];
                        arr[j+d] = temp;
                    }
                }
            }
        }
    }
}

洗牌算法

笔试时，遇到一个算法题：差不多是在n个不同的数中随机取出不重复的m个数。洗牌算法是将原来的数组进行打散，使原数组的某个数在打散后的数组中的每个位置上等概率的出现，刚好可以解决该问题。

该算法是经典洗牌算法。它的proof如下：

对于arr[i],洗牌后在第n-1个位置的概率是1/n（第一次交换的随机数为i）
在n-2个位置概率是[(n-1)/n] * [1/(n-1)] = 1/n，（第一次交换的随机数不为i，第二次为arr[i]所在的位置（注意，若i=n-1，第一交换arr[n-1]会被换到一个随机的位置））
在第n-k个位置的概率是[(n-1)/n] * [(n-2)/(n-1)] … [(n-k+1)/(n-k+2)] *[1/(n-k+1)] = 1/n

该算法的基本思想和 Fisher 类似，每次从未处理的数据中随机取出一个数字，然后把该数字放在数组的尾部，即数组尾部存放的是已经处理过的数字。
算法步骤为：
    1. 建立一个数组大小为 n 的数组 arr，分别存放 1 到 n 的数值；
    2. 生成一个从 0 到 n - 1 的随机数 x；
    3. 输出 arr 下标为 x 的数值，即为第一个随机数；
    4. 将 arr 的尾元素和下标为 x 的元素互换；
    5. 同2，生成一个从 0 到 n - 2 的随机数 x；
    6. 输出 arr 下标为 x 的数值，为第二个随机数；
    7. 将 arr 的倒数第二个元素和下标为 x 的元素互换；
	……
如上，直到输出 m 个数为止

public class hello {
    public static void main(String[] args){
        int[] arr = {5,1,2,6,7,8,93,67,8,3,86,4,6,8,45,86};
        flushArr(arr);
        for(int num : arr){
            System.out.print(num + " ");
        }
    }

    public static void flushArr(int[] arr){
        for (i = arr.length - 1; i > 0; i--)
        {  
            //随机数生成器，范围[0, i]  
            int rand = (new Random()).nextInt(i+1);  

            int temp = arr[i];  
            arr[i] = arr[rand];  
            arr[rand] = temp;  
        }  
    }

    public static int createRandom(int end){
        return (new Random().nextInt(end));
    }

}

最短路径

[[1,1,0,1],
 [1,0,1,0],
 [1,1,1,1],
 [1,0,1,1]]
 1 表示可以经过某个位置，求解从 (0, 0) 位置到 (tr, tc) 位置的最短路径长度。

static int min=Integer.MAX_VALUE;
   static class Pair{
       int key;
       int value;
       public Pair(int key,int value) {
           this.key=key;
           this.value=value;
       }
       public int getKey() {
           return (int) this.key;
       }
       public int getValue() {
           return (int) this.value;
       }
   }
   public static void main(String[] args) {
       int [][]grids= {{1,2},
                       {1,1}};
       minPathLength(grids, 1, 1);
       System.out.println(min);

   }
   public static void minPathLength(int[][] grids, int tr, int tc) {
       final int[][] direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
       int[][] s=new int[2][2];
       for(int i=0;i<2;i++)
       {
           for(int j=0;j<2;j++)
           {
               s[i][j]=300;
           }
       }
       s[0][0]=1;

       final int m = grids.length, n = grids[0].length;
       Queue<Pair> queue = new LinkedList<>();
       queue.add(new Pair(0, 0));
       int pathLength = 0;
       while (!queue.isEmpty()) {
           int size = queue.size();
           while (size-- > 0) {
               Pair cur = queue.poll();
               int cr = cur.getKey(), cc = cur.getValue();
               grids[cr][cc] = 0; // 标记
               for (int[] d : direction) {
                   int nr = cr + d[0], nc = cc + d[1];
                   if (nr < 0 || nr >= m || nc < 0 || nc >= n || s[nr][nc]<=s[cr][cc]+grids[nr][nc]) {
                       continue;
                   }
                   s[nr][nc]=s[cr][cc]+grids[nr][nc];
                   queue.add(new Pair(nr, nc));
               }
           }
       }
       min=Math.min(min,s[1][1]);
   }

不同的数字

一个有序数组，有重复的数，平方后，数组当中有多少不同的数字,例子，[-1，3，3]，返回结果 2.

例子，[-1，-1，1，1]，返回结果 1. nums = {-2,-1,0,1,2,3} 返回4

public int findDiff(int[] nums) {
    int res = 0;
    int left = 0;
    int right = nums.length - 1;
    int pre = - 1;
   
    while (left < right) {
        if (Math.abs(nums[left]) > Math.abs(nums[right])) {
            if (pre != Math.abs(nums[left]) {
                res++;
                pre = Math.abs(nums[left];
            }
            left++;
        } else {
            if (pre != abs(nums[right]) {
                res++;
                pre = abs(nums[right];
            }
            right--;
        }
    }
    return res;
}

leetcode hard

股票问题

4 中位数

10 正则匹配

23 合并K个

41 缺失第一个正数

44 通配符匹配

124 二叉树最大路径和

146 LRU