算法基础（二）

huozhonghun 2019-04-01 原文

算法基础（二）

例一

给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。
要求额外空间复杂度O(1)，时间复杂度O(N)

   public  static void partition(int[] arr, int l, int num) {
        int index=-1;
        while(l<arr.length){
            if(arr[l]<num)  swap(arr,++index,l++);
            else  l++;
        }
    }
    public static void swap(int[] arr, int i, int j){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }

例一(升级版)

给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。
要求额外空间复杂度O(1)，时间复杂度O(N）

  public static void partition(int[] arr, int l, int num) {
        int sindex=l-1;//前指标
        int eindex=arr.length;//后指标
        while(l<eindex){
            if(arr[l]<num)
                swap(arr,++sindex,l++);
            else if(arr[l]==num)
                l++;
            else
                swap(arr,--eindex,l);
         }
    }

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

通过上面的例子引入经典快排

时间复杂度O(N*logN)，额外空间复杂度O(logN)

　　public static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    public static void quickSort(int[] arr, int l, int r) {
        if (l < r) {
　　　　　　　//加上下面一行就变成随机快排
            //swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
            int[] p = partition(arr, l, r);
            quickSort(arr, l, p[0] - 1);
            quickSort(arr, p[1] + 1, r);
        }
    }

    public static int[] partition(int[] arr, int l, int r) {
        int less = l - 1;
        int more = r;
        while (l < more) {
            if (arr[l] < arr[r]) {
                swap(arr, ++less, l++);
            } else if (arr[l] > arr[r]) {
                swap(arr, --more, l);
            } else {
                l++;
            }
        }
        swap(arr, more, r);
        return new int[] { less + 1, more };
    }

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

堆排序

时间复杂度O(N*logN)，额外空间复杂度O(1)

建堆的过程，时间复杂度为O(N)　　

优先级队列结构，就是堆结构

public static void headSort(int[] arr){
        if(arr==null||arr.length<2)
            return;
        for (int i = 0; i < arr.length; i++) {
            headInsert(arr,i);//建成大根堆
        }
        int headSize=arr.length;
        swap(arr,0,--headSize);
        //堆顶和堆底交换，堆底元素移出比较
        while (headSize>0){
            heapify(arr,0,headSize);//重新调整成大根堆
            swap(arr,0,--headSize);
        }
    }

    //建大根堆
    public static void headInsert(int[] arr, int index) {
        while(arr[index]>arr[(index-1)/2]){
            swap(arr,index,(index-1)/2);
            index=(index-1)/2;
        }
    }
    //变成大根堆
    public static void heapify(int[] arr, int index, int size) {
        int left = index * 2 + 1;//根节点的左节点
        while (left < size) {//左节点没超过范围，一直作比较
            int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;//找出左节点和右节点较大的元素
            largest = arr[largest] > arr[index] ? largest : index;//再与根节点比较，找出较大的元素
            if (largest == index) {//如果较大的元素还是根节点，节束，不用交换
                break;
            }
            swap(arr, largest, index);
            index = largest;//根节点移到交换的子节点，继续交换
            left = index * 2 + 1;
        }
    }
    public static void swap(int[] arr, int i, int j){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }