排序算法总结网站首页 技术教程

排序算法总结

无与伦比的jyk 2025-03-24 12:01:02

简介排序算法总结

堆结构

完全二叉树

左孩子 2*i+1

右孩子2*i+2

父节点 i-1/2

大根堆

每棵子树最大值是头结点的值

小根堆

每棵子树最小值是头结点的值

heapInsert方法

O(log N)

与父节点比较（i-1）/2

public static void headInsert(int []arr,int index){
    while(arr[index] > arr[(i-1)/2]){
        swap(arr,index,(index-1)/2);
        index = (index - 1)/2;
   }
}

heapify方法

O(log N)

public static void heapify(int[] arr,int index,int heapSize){
    int left = index * 2 +1;
    while(left < heapSize){
        int largest = left + 1 < heapSize && 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;
        
    }
}

heapSort方法

public static void heapSort(int[] arr){
    if(arr == null || arr.length < 2){
        return;
    }
    for(int i = 0;i < arr.length;i++){ //O(N)
        heapInsert(arr,i);  //O(logN)
    }
    int  heapSize = arr.length;
    swap(arr,0,--heapSize);
    while(heapSize > 0){         //O(N)
        heapify(arr,0,heapSize); //O(logN)
        swap(arr,0,--heapSize);  //O(1)
    }
}

题目

一个几乎有序的数组，几乎有序是指，如果把数组排好序，每个元素移动的距离不超过k，并且k相对数组来说较小，选择一个合适的排序算法

public class Code04{
    priorityQueue<Integer>heap = new PriorityQueue<>();
    int index = 0;
    for(;index <=
        Math.min(arr.length,k);index++){
        heap.add(arr[index]);
    }
    int i = 0;
    for(;index < arr.length;i++,index++){
        heap.add(arr[index]);
        arr[i] = heap.poll();
    }
    while(!heap.isEmpty()){
        arr[i++] = heap.poll();
    }
}

系统自带的堆结构相当于一个黑盒，支持add或者poll的基础操作，不支持以很小的代价调整其中一个数还维持堆结构，手写的可以，所以某些情况要手写堆结构来提高效率

计数排序

不基于比较排序

对于特殊数据可以使用计数排序，例如针对员工年龄进行排序，假设员工年龄范围为0-100岁，那么准备一个0-100的数组，遍历一遍原数组，在计数数组中按顺序记录年龄出现的频次，再将词频还原成有序的数组，本质上是一种特殊的桶排序

时间复杂度为O(N)

基数排序

将数据从左往右依次按照个位数大小放桶，再按顺序倒出来，先进先出，再按照十位数依次进桶，按顺序倒出来，最后按照百位数进桶，倒出来排好序

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


    public static int maxbits(int[] arr)
    {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length - 1; i++) {
            max = Math.max(max, arr[i]);
        }
        int res = 0;
        while (max != 0) {
            res++;
            max /= 10;
        }
        return res;
    }


    public static void radixSort(int[] arr, int L, int R, int digit)
    {
        final int radix = 10;
        int i, j = 0;
        int[] bucket = new int[R - L + 1];

        for (int d = 1; d <= digit; d++) {
            int[] count = new int[radix];
            for (i = L; i <= R; i++) {
                j = getDigit(arr[i], d);
                count[j]++;
            }
            for (i = 1; i < radix; i++) {
                count[i] = count[i] + count[i - 1];
            }
            for (i = R; i >= L; i--) {
                j = getDigit(arr[i], d);
                bucket[count[j] - 1] = arr[i];
                count[j]--;
            }
            for (i = L, j = 0; i <= R; i++, j++) {
                arr[i] = bucket[j];
            }
        }
    }

    public static int getDigit(int x, int d)
    {
        return ((x / ((int)Math.pow(10, d - 1))) % 10);
    }