写在最前面

只想用其中的某个算法？

如果你只是想要对应的排序算法，可删除每个排序类的以下三处

• extends SortTest
• main方法
• @Override

比如，对于冒泡排序，删除下图中框选出来的即可单独使用

类关系图

所有排序算法皆继承SortTest，SortTest主要用于测试算法排序的效果（正确率如何）

工具类NumberArrayUtil

准备一个工具类，用于产生无序的数组

• createNumberArray(int count):产生一个长度为count的数组
• createNumberArrays()：产生一定量的无序数组

public class NumberArrayUtil {private static final Random RANDOM = new Random();/*** 数组的长度包含0 ~ MAX_VAL*/private static final int MAX_VAL = 10;/*** 除了长度为0 ~ MAX_VAL长度的数组之外，再产生多少个数组*/private static final int RANDOM_ARRAY_COUNT = 20;/*** 除了长度为0 ~ MAX_VAL长度的数组之外，再产生的数组最大长度*/private static final int RANDOM_ARRAY_MAX_LENGTH = 100;/*** 产生指定长度的数组* @param count* @return*/public static int[] createNumberArray(int count){int[] res = new int[count];for (int i = 0; i < res.length; i++) {res[i] =  RANDOM.nextInt();}return res;}/*** 产生一定量的随机长度的数组* @return*/public static List<int[]> createNumberArrays(){List<int[]> res = new ArrayList<>();for (int i = 0; i < MAX_VAL; i++) {res.add(createNumberArray(i));}for (int i = 0; i < RANDOM_ARRAY_COUNT; i++) {res.add(createNumberArray(RANDOM.nextInt(RANDOM_ARRAY_MAX_LENGTH)));}return res;}/*** 判断两个数组的值是否相同* @param arr1* @param arr2* @return*/public static boolean isSameArray(int[] arr1, int[] arr2){if (arr1.length != arr2.length){return false;}for (int i = 0; i < arr1.length; i++) {if (arr1[i] != arr2[i]){return false;}}return true;}
}

用于测试排序的父类 SortTest

准备一个抽象类，用于快速测试我们写的算法，是否能完成排序

• test():子类调用，对我们实现的sort进行结果进行检验
• sort方法是抽象方法，子类需要重写，然后调用test方法，即可完成测试
• swap是交换两个索引处的值的方法，排序多会用到

public abstract class SortTest {/*** 排序方法** @param nums* @return*/public abstract int[] sort(int[] nums);/*** 用于检验排序结果*/public void test() {List<int[]> numberArrays = NumberArrayUtil.createNumberArrays();int[] sort;int errorCount = 0;for (int[] numberArray : numberArrays) {int[] copy = Arrays.copyOf(numberArray, numberArray.length);sort = sort(Arrays.copyOf(numberArray, numberArray.length));Arrays.sort(copy);if (!NumberArrayUtil.isSameArray(sort, copy)) {System.out.println(Arrays.toString(numberArray) + "排序出错,排序后的结果：\n" + Arrays.toString(sort));System.out.println();errorCount++;}}System.out.println("测试完成！共计：" + numberArrays.size() + "个，出错个数：" + errorCount);}/*** 交换** @param nums* @param i* @param j*/public void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}

冒泡排序

public class BubbleSort extends SortTest{public static void main(String[] args) {new BubbleSort().test();}/*** 排序方法** @param nums* @return*/@Overridepublic int[] sort(int[] nums) {//排序次数boolean isSwap;for (int i = 0; i < nums.length - 1; i++) {//选出第i大的isSwap = false;for (int j = 0; j < nums.length - 1 - i; j++) {if (nums[j] > nums[j + 1]){swap(nums, j, j + 1);isSwap = true;}}if (!isSwap){break;}}return nums;}
}

堆排序

public class HeapSort extends SortTest {public static void main(String[] args) {new HeapSort().test();}/*** 排序方法** @param nums* @return*/@Overridepublic int[] sort(int[] nums) {//初始化一个大顶堆buildMaxHeap(nums);//堆的大小，每次减少一个for (int i = nums.length - 1; i > 0; i--) {//和最后面交换swap(nums, 0, i);//构建堆,长度-1，最后一个放最大的heapify(nums, 0, i);}return nums;}private void buildMaxHeap(int[] nums) {//从倒数第二层最后一个往前，依次构建堆int len = nums.length;for (int i = len / 2 - 1; i >= 0; i--) {heapify(nums, i, len);}}/*** 构建堆** @param nums* @param index 起始索引* @param len   有效长度*/private void heapify(int[] nums, int index, int len) {if (index >= nums.length){return;}int left = 2 * index + 1;int right = 2 * index + 2;//当前节点和其两个子节点，最大值处对应的索引int maxIndx = index;//是否子节点比当前节点大if (left < len && nums[left] > nums[maxIndx]) {maxIndx = left;}if (right < len && nums[right] > nums[maxIndx]) {maxIndx = right;}//和子节点交换，并对子节进行重新构建堆if (maxIndx != index) {swap(nums, index, maxIndx);heapify(nums, maxIndx, len);}}
}

插入排序

public class InsertSort extends SortTest{/*** 排序方法** @param nums* @return*/@Overridepublic int[] sort(int[] nums) {//遍历for (int i = 1; i < nums.length; i++) {int tmp = nums[i];//如果比当前值大，都应该往后移动int j = i - 1;while (j >= 0 && nums[j] > tmp){nums[j + 1] = nums[j];j--;}nums[j + 1] = tmp;}return nums;}public static void main(String[] args) {new InsertSort().test();}
}

归并排序

public class MergeSort extends SortTest {public static void main(String[] args) {new MergeSort().test();}/*** 排序方法** @param nums* @return*/@Overridepublic int[] sort(int[] nums) {sort(nums, 0, nums.length - 1);return nums;}private void sort(int[] nums, int left, int right) {//结束：if (right <= left) {return;}int mid = left + (right - left) / 2;//分成两个部分，分别排序sort(nums, left, mid);sort(nums, mid + 1, right);//归并int[] marge = marge(Arrays.copyOfRange(nums, left, mid + 1), Arrays.copyOfRange(nums, mid + 1, right + 1));System.arraycopy(marge, 0, nums, left, marge.length);}private int[] marge(int[] nums1, int[] nums2) {int[] res = new int[nums1.length + nums2.length];//已经添加的个数int index = 0;//两个指针int i = 0, j = 0;while (i < nums1.length && j < nums2.length) {//谁小，谁加入;//i或j增加if (nums1[i] > nums2[j]) {res[index++] = nums2[j++];} else {res[index++] = nums1[i++];}}//如果添加完了就结束if (index == res.length) {return res;}//没添加完，把某个数组剩余的部分拷贝进去if (i < nums1.length) {for (; i < nums1.length; i++) {res[index++] = nums1[i];}} else {for (; j < nums2.length; j++) {res[index++] = nums2[j];}}return res;}
}

快速排序

public class QuickSort extends SortTest{public static void main(String[] args) {new QuickSort().test();}/*** 排序方法** @param nums* @return*/@Overridepublic int[] sort(int[] nums) {sort(nums, 0, nums.length - 1);return nums;}private void sort(int[] nums, int left, int right) {//结束：if (left >= right){return;}//排序//基准int val = nums[left];int i = left, j = right;while (i < j){//右边先移动while (j > i && nums[j] >= val){j--;}//换到左边nums[i] = nums[j];//左边移动while (i < j && nums[i] <= val){i++;}//换到右边nums[j] = nums[i];}nums[i] = val;//排左边sort(nums, left, i - 1);//排右边sort(nums, i + 1, right);}
}

选择排序

public class SelectionSort extends SortTest{/*** 排序方法** @param nums* @return*/@Overridepublic int[] sort(int[] nums) {//要选n-1次for (int i = 0; i < nums.length - 1; i++) {//每次找最小的放前面int min = nums[i];int index = i;for (int j = i + 1; j < nums.length; j++) {if (min > nums[j]){min = nums[j];index = j;}}//交换swap(nums, i, index);}return nums;}public static void main(String[] args) {new SelectionSort().test();}
}

希尔排序

public class ShellSort extends SortTest {public static void main(String[] args) {new ShellSort().test();}/*** 排序方法** @param nums* @return*/@Overridepublic int[] sort(int[] nums) {//步长int step = nums.length;for (int i = step; i > 0; i /= 2) {//以步长为i进行快速排序for (int j = 0; j < step; j++) {//对第j组进行排序，步长是isort(nums, j, i);}}return nums;}/*** 希尔排序，对第startIndex组进行排序** @param nums* @param startIndex 起始索引* @param step       步长*/private void sort(int[] nums, int startIndex, int step) {for (int i = startIndex + step; i < nums.length; i += step) {int tmp = nums[i];//一直向前找，找到一个比当前值小的值int j = i - step;while (j >= 0 && nums[j] > tmp) {nums[j + step] = nums[j];j -= step;}//插入在其后面nums[j + step] = tmp;}}
}