数据结构与算法

一排序
- 1.简单选择排序
- 2.插入排序
- 3.归并排序
- - （1）归并排序的应用-1.小和问题
  - （2）归并排序的应用-2.剑指 Offer 51. 数组中的逆序对
- 4.快速排序
- - （1）基础版本
  - （2）三路快排
- 5.堆排序
- - 堆结构的应用-实现限制移动距离的排序
- 6.基数排序
- 排序总结

一排序 1.简单选择排序

public class SelectSort01 {
    private SelectSort01(){}//私有化构造函数（不让创建对象，直接用）

    public static void selectsort(int[] a){
        int i, j, min;;
        for (i = 0; i

2.插入排序

public class Insert01 {
    private Insert01(){}

    public static > void insert(E[] arr){
        for(int i = 1;i=0&&t.compareTo(arr[j-1])<0;j--){
                   arr[j] = arr[j - 1];//后移
               }
               arr[j] = t;
           }
        }
    }

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

    public static void main(String[] args) {
        Integer[] arr = {4, 22, 74,6,8, 9,3};
        insert(arr);
        for(int i:arr){
            System.out.print(i+" ");
        }
    }
}

3.归并排序

public class Merge {
    public static void mergeSort(int[] arr) {
        mergeSort(arr, 0, arr.length - 1);
    }

    private static void mergeSort(int[] arr, int l, int r) {
        if (r <= l) {
            return;
        }
        int mid = l + ((r - l) >> 1);
        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, r);
        //可以在有序情况下不进行merge从而提升效率
        if (arr[mid]-arr[mid + 1] > 0) {
            merge(arr, l, mid, r);
        }
    }

    private static void merge(int[] arr, int l, int mid, int r) {
        //辅助数组
        int[] help = new int[r - l + 1];
        int i = 0;
        int p1 = l;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= r) {
            help[i++] = arr[p1]-arr[p2] <= 0 ? arr[p1++] : arr[p2++];
        }
        while (p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while (p2 <= r) {
            help[i++] = arr[p2++];
        }
        //回填到原数组
        for (int j = 0; j < help.length; j++) {
            arr[l + j] = help[j];
        }
    }
}

（1）归并排序的应用-1.小和问题

public class SmallAdd {
    public static int getAdd(int[] arr) {
        return process(arr, 0, arr.length-1);
    }

    public static int process(int[] arr, int l, int r) {
        if (l >= r) {
            return 0;
        }
        int mid = l + ((r - l) >> 1);
        return process(arr, l, mid)
                + process(arr, mid + 1, r)
                + merge(arr, l, mid, r);
    }

    private static int merge(int[] arr, int l, int mid, int r) {
        int[] arr1 = new int[r - l + 1];
        int i = 0;
        int p1 = l;
        int p2 = mid + 1;
        int res = 0;
        while (p1 <= mid && p2 <= r) {
            if (arr[p1] < arr[p2]) {//相等时候是吧右边的放入新数组！！！
                res += (r - p2 + 1) * arr[p1];
                arr1[i++] = arr[p1++];
            } else {
                res += 0;//!!!
                arr1[i++] = arr[p2++];
            }
        }
        while (p1 <= mid) {
            arr1[i++] = arr[p1++];
        }
        while (p2 <= r) {
            arr1[i++] = arr[p2++];
        }
        for (int j = 0; j < arr1.length; j++) {
            arr[l + j] = arr1[j];
        }
        return res;
    }

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

（2）归并排序的应用-2.剑指 Offer 51. 数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:
输入: [7,5,6,4]
输出: 5

限制：
0 <= 数组长度 <= 50000

class Solution {
    public int reversePairs(int[] nums) {
        if(nums.length<2){
            return 0;
        }
        int process = merge(nums, 0, nums.length - 1);
        return process;
    }

    public static int merge(int[] arr,int l,int r){
        if (l >= r) {
            return 0;
        }
        int mid = l + ((r - l) >> 1);
        return merge(arr,l,mid)+merge(arr,mid+1,r)+process(arr,l,r,mid);
    }

    public static int process(int[] arr, int l, int r,int mid) {

        int p1 = l;
        int p2 = mid + 1;
        int res = 0;
        int i = 0;
        int[] ints = new int[r - l + 1];
        //从大到小排序
        while (p1 <= mid && p2 <= r) {
            if (arr[p1] > arr[p2]) {
                res +=(r-p2+1);
                ints[i++] = arr[p1++];
            } else {
                res +=0;
                ints[i++] = arr[p2++];
            }
        }
        while (p1 <= mid) {
            ints[i++] = arr[p1++];
        }
        while (p2 <= r) {
            ints[i++] = arr[p2++];
        }
        for (int j = 0; j <  ints.length; j++) {
            arr[l + j] = ints[j];
        }
        return res;
    }
}

4.快速排序（1）基础版本

public class Sort {
    public static void sortMain(int[]arr) {
        Random random = new Random();
        sort(arr,0,arr.length-1,random);
    }

    public static void sort(int arr[], int low, int high,Random random) {
        if (low < high) {
            int p = partition(arr, low, high,random);
            sort(arr, low, p - 1,random);
            sort(arr, p + 1, high,random);
        }
    }

    public static int partition(int arr[], int low, int high,Random random) {
        int nextInt = low + random.nextInt(high - low + 1);
        int pivot = arr[nextInt];//随机位置作为中枢
        arr[nextInt] = arr[low];
        arr[low] = pivot;
        while (low < high) {
            while (low < high && arr[high] >= pivot) {
                high--;
            }
            arr[low] = arr[high];
            while (low < high && arr[low] <= pivot) {
                low++;
            }
            arr[high] = arr[low];
        }
        arr[low] = pivot;
        return low;
    }

    public static void main(String[] args) {
        int a[] = {5, 23, 7, 8, 1, 65, 68, 90, 34, 3, 0};
        sortMain(a);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
    }
}

（2）三路快排

public class QuickSort {
    //三路排序实现快排
    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int l, int r) {
        if (l < r) {
            //l + !!!!
            int rand = l + (int) Math.random() * (r - l + 1);
            swap(arr, rand, r);//枢纽放在最后面
            int[] p = partition(arr, l, r);
            quickSort(arr, l, p[0] - 1);
            quickSort(arr, p[1] + 1, r);
        }
    }

    private static int[] partition(int[] arr, int l, int r) {
        //因为l指向的是第一个数，所以边界值应当是l-1
        //因为r指向的数是枢纽，所以有边界是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 temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

    public static void main(String[] args) {
        int[] a = {5, 3, 6, 7, 8, 1, 4};
        sort(a);
        for (int i : a) {
            System.out.println(i);
        }
    }
}

5.堆排序

public class Test01 {
    public static void heapSort(int[] arr) {
        if (arr == null && arr.length < 2) {
            return;
        }

        //实现大根堆
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }
        //上面的实现大根堆是一个一个插入，逐步实现大根堆
        //也可以直接用从上到下有序化直接全部实现
        //直接全部排序的效率要高一点
        

        //最大的数和末位数交换，实现排序
        int heapSize = arr.length;
        swap(arr, 0, --heapSize);
        while (heapSize > 0) {
            //冲新调整
            heapify(arr, 0, heapSize);
            swap(arr, 0, --heapSize);
        }
    }

    //从上到下恢复大根堆
    private static void heapify(int[] arr, int i, int heapSize) {
        int left = i * 2 + 1;
        //如有孩子
        while (left < heapSize) {
            int bigest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            bigest = arr[i] > arr[bigest] ? i : bigest;
            //若i还是最大的那个
            if (bigest == i) {
                break;
            } else {
                swap(arr, i, bigest);
                i = bigest;
                left = i * 2 + 1;
            }
        }
    }

//从下到上形成大根堆
    private static void heapInsert(int[] arr, int i) {
        //当比父节点大，实现swap
        while (arr[i] > arr[(i - 1) / 2]) {
            swap(arr, i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }

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

    public static void main(String[] args) {
        int[] a = {5, 2, 7, 1, 6, 0, 7, 4, 2, 1};
        heapSort(a);
        for (int i : a) {
            System.out.print(i+" ");
        }
    }
}

堆结构的应用-实现限制移动距离的排序

import java.util.PriorityQueue;

public class Test01 {
    public static void heapSort(int[] arr,int k) {
        //小根堆
        PriorityQueue small = new PriorityQueue<>();

        //按k+1个数范围（前k+1个数的移动范围最大为k）依次确定位置
        int i = 0;
        for (; i <= k; i++) {
            small.add(arr[i]);
        }
        int j = 0;
        //出一个，进一个，保证k
        for (; i < arr.length;i++, j++) {
            arr[j] = small.poll();
            small.add(arr[i]);
        }

        //剩下的依次弹出排序
        while (!small.isEmpty()) {
            arr[j++] = small.poll();
        }
    }


    public static void main(String[] args) {
        int[] a = {2,1,3,4,5,7,6};
        heapSort(a,3);
        for (int i : a) {
            System.out.print(i+" ");
        }
    }
}

6.基数排序

public class RadixSort {
    
    public static void radixSort(int[] nums) {
        if (nums == null || nums.length < 2) {
            return ;
        }
        //maxbits(nums)得到最大十进制数的位数
        radixSort(nums, 0, nums.length-1, maxbits(nums));
    }

    private static void radixSort(int[] nums, int L, int R, int maxbits) {
        //辅助空间
        int[] bucket = new int[R - L + 1];
        //桶数
        final int radix = 10;

        //入桶
        for (int i = 1; i <= maxbits; i++) {//有多少位，进出多少次桶
            int[] count = new int[radix];//初始化桶
            for (int j = L; j <= R; j++) {
                int digit = getDigit(nums[j], i);//得到第i位的数
                count[digit]++;//入桶
            }
            //基数排序的优化，把<=i位的数累加
            for (int k = 1; k < radix; k++) {
                count[k] = count[k - 1] + count[k];
            }
            //从右向左出桶
            for (int t = R; t >= L ; t--) {
                int digit = getDigit(nums[t], i);//得到按第i个位置出桶
                bucket[--count[digit]] = nums[t];//出桶的数放在辅助数组的第（数量-1个位置）
            }
            //还原到num数组，进行下一次入桶
            for (int m = L; m <= R; m++) {
                nums[m] = bucket[m];
            }
        }
    }

    //得到第i位的数
    private static int getDigit(int num, int i) {
        return (num / (int) Math.pow(10, i - 1)) % 10;
    }

    private static int maxbits(int[] nums) {
        //得到最大的数
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            max = Math.max(max, nums[i]);
        }

        //计算最大数的位数
        int res = 0;
        while (max != 0) {
            res++;
            max /= 10;
        }
        return res;
    }

    public static void main(String[] args) {
        int[] n = {55, 2, 5, 765, 8, 114, 797, 310};
        radixSort(n);
        for (int i = 0; i < n.length; i++) {
            System.out.print(n[i]+" ");
        }
    }
}

排序总结

数据结构与算法

Java相关栏目本月热门文章