Java 实现 11 种排序算法

package com.lanyue.sort.impl; import com.lanyue.sort.interstand.Sort; import java.lang.reflect.Constructor; /** * 内部排序-桶排序优化版 * * 与其说桶排序是一种算法，不如说桶排序是一种思维，一种策略 * 桶排序上限很高，下限也很低。算法的最终执行效率与编写代码的人的综合能力息息相关，可以说是最考验程序员能力的一种算法 * 它可以比快速排序快，也可以比 选择/插入 排序慢；它可以和冒泡排序一样省内存空间，也可以和归并排序一样耗费内存空间 * * 桶排序中 * 可以直接定义所有的桶（费空间，省时间），也可以一桶多用（省空间，费时间） * 可以将桶设置的很大，也可以设置的很小 * 可以在桶内使用堆排序、归并排序、快速排序等高阶排序，也可以使用冒泡排序，插入排序，选择排序等低阶排序 */ public class BucketSort extends Sort { // 桶的容量，每个桶种最多可以存放多少个不同的元素（去重后的个数） private final int bucketVolume = 100000; // 桶内的排序算法 private final String bucketInnerArithmetic = CountSort.class.getCanonicalName(); // 最小桶的最小值 private int startBucketSign; // 最大桶的最小值 private int endBucketSign; // 各个桶的长度 private int[] bucketLength; // 各个桶的当前索引（插入桶数据时用到） private int[] bucketCurrIndex; // 排序中需要用到的桶 private int[][] bucketData; public BucketSort(int[] data, String sortName){ super(data, sortName); } private int getMaxElement(){ int maximum = getElement(1); for (int index = 2; index <= getLength(); index++){ if (getElement(index) > maximum){ maximum = getElement(index); } } return maximum; } private int getMinElement(){ int minimum = getElement(1); for (int index = 2; index <= getLength(); index++){ if (getElement(index) < minimum){ minimum = getElement(index); } } return minimum; } // 将元素放进对应的桶 private void putElementToBucket(){ for (int index = 1; index <= getLength(); index++){ int oneDim = (getElement(index) - startBucketSign) / bucketVolume; bucketData[oneDim][bucketCurrIndex[oneDim]] = getElement(index); bucketCurrIndex[oneDim] = bucketCurrIndex[oneDim] + 1; } } private void init(){ startBucketSign = getMinElement() / bucketVolume * bucketVolume; endBucketSign = getMaxElement() / bucketVolume * bucketVolume; // 二维数组的 一维、二维 长度 int oneDim = (endBucketSign - startBucketSign) / bucketVolume + 1; int twoDim; bucketLength = new int[oneDim]; bucketCurrIndex = new int[oneDim]; bucketData = new int[oneDim][]; for (int index = 1; index <= oneDim; index++){ bucketLength[index - 1] = 0; bucketCurrIndex[index - 1] = 0; } for (int index = 1; index <= getLength(); index++){ oneDim = (getElement(index) - startBucketSign) / bucketVolume; bucketLength[oneDim] = bucketLength[oneDim] + 1; } for (int bucketSign = startBucketSign; bucketSign <= endBucketSign; bucketSign += bucketVolume){ oneDim = (bucketSign - startBucketSign) / bucketVolume ; twoDim = bucketLength[oneDim]; bucketData[oneDim] = new int[twoDim]; } } @Override public void handle() { init(); handleSort(); } private void handleSort(){ putElementToBucket(); bucketDataSort(); } private void bucketDataSort(){ int index = 1; int oneDim; for (int bucketSign = startBucketSign; bucketSign <= endBucketSign; bucketSign += bucketVolume){ // list.stream().mapToInt(Integer::valueOf).toArray(); // 对桶内的数据进行排序 oneDim = (bucketSign - startBucketSign) / bucketVolume; // auxSort(bucketData[oneDim]); auxSort(bucketData[oneDim], bucketInnerArithmetic, "桶内排序算法"); // 将桶内排序好的数据放到原数据中 copyValueFromBucketToData(index, bucketData[oneDim]); index += bucketData[oneDim].length; } } private void auxSort(int[] data, String auxArithmetic, String sortName){ try { Class sortClass = Class.forName(auxArithmetic); Constructor constructor = sortClass.getConstructor(int[].class, String.class); Sort sort = (Sort) constructor.newInstance(data, sortName); sort.handle(); } catch (Exception e) { System.out.println("[桶排序]: 未定位到指定的排序算法"); } } private void auxSort(int[] data){ new MergeSort(data, "桶内排序算法").handle(); } private void copyValueFromBucketToData(int startIndex, int[] tempData){ if (tempData.length >= 1){ for (int index = 1; index <= tempData.length; index++){ setElement(startIndex++, tempData[index - 1]); } } } }