数据结构与算法之非比较排序算法总结

原创
2020/03/13 14:57
阅读数 261

非比较算法:

计数排序

是一种通过统计数组中每个元素数据个数的排序算法。通过统计数组中每个元素的数据个数,再按照统计后的结果,从小的数值开始按照个数重新构造出新的数组,从而完成对原数组的排序。计数排序需要一块新的数组,其大小和数组最大元素相同。

执行规则:
  1. 确定数组元素的最大和最下边界。
  2. 统计数组中每个元素出现的次数,存入新的数组中。
  3. 按照新数组的个数回填原有数组完成排序。
计数排序
public static int[] countingsorted(int[] sourceArray) {
    // 对 arr 进行拷贝,不改变参数内容
    int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

    int maxValue = getMaxValue(arr);

    return sort(arr, maxValue);
}
获取数组中元素的最大值
private static int getMaxValue(int[] arr) {
    int maxValue = arr[0];
    for (int value : arr) {
        if (maxValue < value) {
            maxValue = value;
        }
    }
    return maxValue;
}
构造数组
private static int[] sort(int[] arr, int maxValue) {
    int bucketLen = maxValue + 1;
    int[] bucket = new int[bucketLen];

    for (int value : arr) {
        bucket[value]++;
    }
    //构造出新的数组
    int sortedIndex = 0;
    for (int j = 0; j < bucketLen; j++) {
        while (bucket[j] > 0) {
            arr[sortedIndex++] = j;
            bucket[j]--;
        }
    }
    return arr;
}

基数排序

通过对比数据的个位,十位,百位将数据不断的调整位置直到排序完成。
 
执行顺序:
  1. 按照个位数据进行排序。(将数据按照顺序放入桶中。)
  2. 按照十位数据进行排序,当10位相同时,不可破坏上一步个位数据的排序。(从桶中依次弹出,重新按照规则放入桶中。在10位相同时,会因个位不同受到弹出的顺序不同。)
  3. 以次类推,直到各位排序完成。
基数排序
public static int[] radixSorted(int[] sourceArray) {
    // 对 arr 进行拷贝,不改变参数内容
    int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

    int maxDigit = getMaxDigit(arr);
    return radixSort(arr, maxDigit);
}
获取最高位数
private static int getMaxDigit(int[] arr) {
    int maxValue = getMaxValue(arr);
    return getNumLenght(maxValue);
}
获取最大值
private static int getMaxValue(int[] arr) {
    int maxValue = arr[0];
    for (int value : arr) {
        if (maxValue < value) {
            maxValue = value;
        }
    }
    return maxValue;
}
protected static int getNumLenght(long num) {
    if (num == 0) {
        return 1;
    }
    int lenght = 0;
    for (long temp = num; temp != 0; temp /= 10) {
        lenght++;
    }
    return lenght;
}
基数排序
private static int[] radixSort(int[] arr, int maxDigit) {
    int mod = 10;
    int dev = 1;

    for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        // 考虑负数的情况,这里扩展一倍队列数,其中 [0-9]对应负数,[10-19]对应正数 (bucket + 10)
        int[][] counter = new int[mod * 2][0];

        for (int j = 0; j < arr.length; j++) {
            int bucket = ((arr[j] % mod) / dev) + mod;
            counter[bucket] = arrayAppend(counter[bucket], arr[j]);
        }

        int pos = 0;
        for (int[] bucket : counter) {
            for (int value : bucket) {
                arr[pos++] = value;
            }
        }
    }

    return arr;
}
数组扩容,保存数据
private static int[] arrayAppend(int[] arr, int value) {
    arr = Arrays.copyOf(arr, arr.length + 1);
    arr[arr.length - 1] = value;
    return arr;
}

桶排序

将要排序的数据按照一定的规则映射到一定数量的桶中,对桶内数据排序后,在构造出原有数组。
桶的数量要尽量多,并且映射规则要尽可能的将数据均匀的映射到不同的桶中。
 
执行顺序:
  1. 将要排序的数据按规则映射到桶之中。
  2. 对每个桶之中的元素单独排序。
  3. 按照桶的顺序及桶内元素的数据重新构造排序后的数组。
桶排序
public static int[] bucketSorted(int[] sourceArray) {
    // 对 arr 进行拷贝,不改变参数内容
    int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

    return bucketSort(arr, 5);
}
排序
private static int[] bucketSort(int[] arr, int bucketSize) {
        if (arr.length == 0) {
            return arr;
        }

        int minValue = arr[0];
        int maxValue = arr[0];
        for (int value : arr) {
            if (value < minValue) {
                minValue = value;
            } else if (value > maxValue) {
                maxValue = value;
            }
        }

        int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
        int[][] buckets = new int[bucketCount][0];

        // 利用映射函数将数据分配到各个桶中
        for (int i = 0; i < arr.length; i++) {
            int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
            buckets[index] = arrAppend(buckets[index], arr[i]);
        }

        int arrIndex = 0;
        for (int[] bucket : buckets) {
            if (bucket.length <= 0) {
                continue;
            }
            // 对每个桶进行排序,这里使用了插入排序
            InsertionSort.insertionSorted(bucket, StatusCode.MIX_SORT);
//            bucket = insertSort.sort(bucket);
            for (int value : bucket) {
                arr[arrIndex++] = value;
            }
        }

        return arr;
    }
}
桶排序
private static int[] arrAppend(int[] arr, int value) {
    arr = Arrays.copyOf(arr, arr.length + 1);
    arr[arr.length - 1] = value;
    return arr;
}

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部