Java 中的十大排序算法
1、冒泡排序
public class BubbleSort { public static int[] sort(int[] array) { if (array.length == 0) return array; /*循环数组长度的次数*/ for (int i = 0; i < array.length; i++){ /*从第0个元素开始，依次和后面的元素进行比较 * j < array.length - 1 - i表示第[array.length - 1 - i] * 个元素已经冒泡到了合适的位置，无需进行比较，可以减少比较次数*/ for (int j = 0; j < array.length - 1 - i; j++){ /*如果第j个元素比后面的第j+1元素大，交换两者的位置*/ if (array[j + 1] < array[j]) { int temp = array[j + 1]; array[j + 1] = array[j]; array[j] = temp; } PrintArray.print(array); } System.out.println("---------------"); //PrintArray.print(array); } return array; } public static void main(String[] args) { PrintArray.print(PrintArray.SRC); System.out.println("============================================"); int[] dest = BubbleSort.sort(PrintArray.SRC); PrintArray.print(dest); }}2、选择排序
public class ChoiceSort { public static int[] sort(int[] array) { if (array.length == 0) return array; for (int i = 0; i < array.length; i++) { int minIndex=i;/*最小数的下标，每个循环开始总是假设第一个数最小*/ for (int j = i; j < array.length; j++) { if (array[j] < array[minIndex]) /*找到最小的数*/ minIndex = j; /*将最小数的索引保存*/ } System.out.println("最小数为："+array[minIndex]); /*交换最小数和i当前所指的元素*/ int temp = array[minIndex]; array[minIndex] = array[i]; array[i] = temp; PrintArray.print(array); System.out.println("---------------"); } return array; } public static void main(String[] args) { PrintArray.print(PrintArray.SRC); System.out.println("============================================"); int[] dest = ChoiceSort.sort(PrintArray.SRC); PrintArray.print(dest); }}3、插入排序
public class InsertionSort { public static int[] sort(int[] array) { if (array.length == 0) return array; int currentValue;/*当前待排序数据，该元素之前的元素均已被排序过*/ for (int i = 0; i < array.length - 1; i++) { int preIndex = i;/*已被排序数据的索引*/ currentValue = array[preIndex + 1]; System.out.println("待排序元素索引:"+(i + 1)+"，值为：" +currentValue+ ",已被排序数据的索引:"+preIndex); /*在已被排序过数据中倒序寻找合适的位置，如果当前待排序数据比比较的元素要小， 将比较的元素元素后移一位*/ while (preIndex >= 0 && currentValue < array[preIndex]) { //将当前元素后移一位 array[preIndex + 1] = array[preIndex]; preIndex--; PrintArray.print(array); } /*while循环结束时，说明已经找到了当前待排序数据的合适位置，插入*/ array[preIndex + 1] = currentValue; System.out.println("本轮被插入排序后的数组"); PrintArray.print(array); System.out.println("--------------------"); } return array; } public static void main(String[] args) { PrintArray.print(PrintArray.SRC); System.out.println("============================================"); int[] dest = InsertionSort.sort(PrintArray.SRC); PrintArray.print(dest); }}4、希尔排序
public class ShellSort { public static int[] sort(int[] array) { int len = array.length; /*按增量分组后，每个分组中，temp代表当前待排序数据，该元素之前的元素均已被排序过*/ /*gap指用来分组的增量，会依次递减*/ int currentValue, gap = len / 2; while (gap > 0) { for (int i = gap; i < len; i++) { currentValue = array[i]; /*组内已被排序数据的索引*/ int preIndex = i - gap; /*在组内已被排序过数据中倒序寻找合适的位置，如果当前待排序数据比比较的元素要小， 并将比较的元素元素在组内后移一位*/ while (preIndex >= 0 && array[preIndex] > currentValue) { array[preIndex + gap] = array[preIndex]; preIndex -= gap; } /*while循环结束时，说明已经找到了当前待排序数据的合适位置，插入*/ array[preIndex + gap] = currentValue; } System.out.println("本轮增量【"+gap+"】排序后的数组"); PrintArray.print(array); System.out.println("--------------------"); gap /= 2; } return array; } public static void main(String[] args) { PrintArray.print(PrintArray.SRC); System.out.println("============================================"); int[] dest = ShellSort.sort(PrintArray.SRC); PrintArray.print(dest); }}5、归并排序
public class MergeSort { public static int[] sort(int[] array) { if (array.length < 2) return array; /*切分数组，然后递归调用*/ int mid = array.length / 2; int[] left = Arrays.copyOfRange(array, 0, mid); int[] right = Arrays.copyOfRange(array, mid, array.length); return merge(sort(left), sort(right)); } /** * 归并排序——将两段排序好的数组结合成一个排序数组 * * @param left * @param right * @return */ public static int[] merge(int[] left, int[] right) { int[] result = new int[left.length + right.length]; for (int index = 0, i = 0, j = 0; index < result.length; index++) { if (i >= left.length)/*左边数组已经取完，完全取右边数组的值即可*/ result[index] = right[j++]; else if (j >= right.length)/*右边数组已经取完，完全取左边数组的值即可*/ result[index] = left[i++]; else if (left[i] > right[j])/*左边数组的元素值大于右边数组，取右边数组的值*/ result[index] = right[j++]; else/*右边数组的元素值大于左边数组，取左边数组的值*/ result[index] = left[i++]; } System.out.print("左子数组:"); PrintArray.print(left); System.out.print("右子数组:"); PrintArray.print(right); System.out.print("合并后数组:"); PrintArray.print(result); System.out.println("--------------------"); return result; } public static void main(String[] args) { PrintArray.print(PrintArray.SRC); System.out.println("============================================"); int[] dest = MergeSort.sort(PrintArray.SRC); PrintArray.print(dest); }}6、快速排序
public class QuickSort { public static int[] sort(int[] array, int start, int end) { if (array.length < 1 || start < 0 || end >= array.length || start > end) return null; /*数据分割成独立的两部分时，从哪儿分区的指示器*/ int zoneIndex = partition(array, start, end); if (zoneIndex > start) sort(array, start, zoneIndex - 1); if (zoneIndex < end) sort(array, zoneIndex + 1, end); System.out.println("本轮排序后的数组"); PrintArray.printIndex(array,start,end); System.out.println("--------------------"); return array; } /** * 快速排序算法——partition * @param array * @param start * @param end * @return */ public static int partition(int[] array, int start, int end) { int pivot = (int) (start + Math.random() * (end - start + 1)); System.out.println("开始下标："+start+",结束下标:"+end+",基准数下标：" +pivot+",元素值:"+array[pivot]); /*zoneIndex是分割指示器 从业务上来说：比基准数小的，放到指示器的左边，比基准数大的，放到指示器的右边， * 但在实际实现时，通过移动比基准数小的元素和分割指示器本身也可以达到一样的效果*/ int zoneIndex = start - 1; swap(array, pivot, end);/*将基准数和数组尾元素交换位置*/ for (int i = start; i <= end; i++){ if (array[i] <= array[end]) {/*当前元素小于等于基准数*/ zoneIndex++;/*首先分割指示器累加*/ if (i > zoneIndex)/*当前元素在分割指示器的右边时，交换当前元素和分割指示器元素*/ swap(array, i, zoneIndex); } System.out.println("zoneIndex："+zoneIndex+",i:"+i); PrintArray.printIndex(array,start,end); } System.out.println("---------------"); return zoneIndex; } /** * 交换数组内两个元素 * @param array * @param i * @param j */ public static void swap(int[] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } public static void main(String[] args) { PrintArray.print(PrintArray.SRC); System.out.println("============================================"); int[] dest = QuickSort.sort(PrintArray.SRC,0,PrintArray.SRC.length-1); PrintArray.print(dest); }}7、堆排序
public class HeapSort { //声明全局变量，用于记录数组array的长度； private static int len; public static int[] sort(int[] array) { len = array.length; if (len < 1) return array; //1.构建一个最大堆 buildMaxHeap(array); //2.循环将堆首位（最大值）与末位交换，然后在重新调整最大堆 while (len > 0) { swap(array, 0, len - 1); len--; adjustHeap(array, 0); PrintArray.print(array); System.out.println("--------------------"); } return array; } /** * 建立最大堆 * * @param array */ public static void buildMaxHeap(int[] array) { //从最后一个非叶子节点开始向上构造最大堆 for (int i = (len/2-1); i >= 0; i--) { adjustHeap(array, i); } System.out.println("构造完成最大堆"); PrintArray.print(array); System.out.println("============================================"); } /** * 调整使之成为最大堆 * * @param array * @param i */ public static void adjustHeap(int[] array, int i) { int maxIndex = i; int left = 2*i+1; int right = 2*(i+1); //如果有左子树，且左子树大于父节点，则将最大指针指向左子树 if (left < len && array[left] > array[maxIndex]) maxIndex = left; //如果有右子树，且右子树大于父节点，则将最大指针指向右子树 if (right < len && array[right] > array[maxIndex]) maxIndex = right; //如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。 if (maxIndex != i) { swap(array, maxIndex, i); adjustHeap(array, maxIndex); } } /** * 交换数组内两个元素 * @param array * @param i * @param j */ public static void swap(int[] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } public static void main(String[] args) { PrintArray.print(PrintArray.SRC); System.out.println("============================================"); int[] dest = HeapSort.sort(PrintArray.SRC); PrintArray.print(dest); }}8、计数排序
public class CountingSort { public static int[] sort(int[] array) { if (array.length == 0) return array; /*寻找数组中最大值，最小值 * bias:偏移量,用以定位原始数组每个元素在计数数组中的下标位置*/ int bias, min = array[0], max = array[0]; for (int i = 1; i < array.length; i++) { if (array[i] > max) max = array[i]; if (array[i] < min) min = array[i]; } bias = 0 - min; /*获得计数数组的容量*/ int[] counterArray = new int[max - min + 1]; Arrays.fill(counterArray, 0); /*遍历整个原始数组，将原始数组中每个元素值转化为计数数组下标， 并将计数数组下标对应的元素值大小进行累加*/ for (int i = 0; i < array.length; i++) { counterArray[array[i] + bias]++; } System.out.println("计数数组为："); PrintArray.print(counterArray); System.out.println("============================================"); int index = 0;/*访问原始数组时的下标计数器*/ int i = 0;/*访问计数数组时的下标计数器*/ /*访问计数数组，将计数数组中的元素转换后，重新写回原始数组*/ while (index < array.length) { /*只要计数数组中当前下标元素的值不为0，就将计数数组中的元素转换后，重新写回原始数组*/ if (counterArray[i] != 0) { array[index] = i - bias; counterArray[i]--; index++; } else i++; PrintArray.print(counterArray); PrintArray.print(array); System.out.println("--------------------"); } return array; } final static int[] src = {5,4,5,0,3,6,2,0,2,4,3,3}; public static void main(String[] args) { PrintArray.print(src); System.out.println("============================================"); int[] dest = CountingSort.sort(src); PrintArray.print(dest); }}9、桶排序
public class BucketSort { /** * * @param array * @param bucketSize BucketSize，作为每个桶所能放置多少个不同数值 * （例如当BucketSize==5时，该桶可以存放｛1,2,3,4,5｝这几种数字， * 但是容量不限，即可以存放100个3）； * @return */ public static ArrayList<Integer> sort(ArrayList<Integer> array, int bucketSize) { if (array == null || array.size() < 2) return array; int max = array.get(0), min = array.get(0); // 找到最大值最小值 for (int i = 0; i < array.size(); i++) { if (array.get(i) > max) max = array.get(i); if (array.get(i) < min) min = array.get(i); } /*获得桶的数量*/ int bucketCount = (max - min) / bucketSize + 1; /*构建桶*/ ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount); ArrayList<Integer> resultArr = new ArrayList<>(); for (int i = 0; i < bucketCount; i++) { bucketArr.add(new ArrayList<Integer>()); } /*将原始数组中的数据分配到桶中*/ for (int i = 0; i < array.size(); i++) { bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i)); } /*看看桶中数据的分布*/ for (int i = 0; i < bucketArr.size(); i++) { System.out.print("第"+i+"个桶包含数据："); PrintArray.printObject(bucketArr.get(i)); } for (int i = 0; i < bucketCount; i++) { if (bucketSize == 1) { for (int j = 0; j < bucketArr.get(i).size(); j++) resultArr.add(bucketArr.get(i).get(j)); } else { if (bucketCount == 1) bucketSize--; /*对桶中的数据再次用桶进行排序*/ ArrayList<Integer> temp = sort(bucketArr.get(i), bucketSize); for (int j = 0; j < temp.size(); j++) resultArr.add(temp.get(j)); } } return resultArr; } public static void main(String[] args) { ArrayList<Integer> array = new ArrayList<>(); array.add(86); array.add(11); array.add(77); array.add(23); array.add(32); array.add(45); array.add(58); array.add(63); array.add(93); array.add(4); array.add(37); array.add(22); PrintArray.printObject(array); System.out.println("============================================"); ArrayList<Integer> dest = BucketSort.sort(array,2); PrintArray.printObject(dest); }}10、基数排序
public class RadixSort { public static int[] sort(int[] array) { if (array == null || array.length < 2) return array; /*找出最大数*/ int max = array[0]; for (int i = 1; i < array.length; i++) { max = Math.max(max, array[i]); } /*先算出最大数的位数*/ int maxDigit = 0; while (max != 0) { max /= 10; maxDigit++; } int mod = 10, div = 1; /*构建桶*/ ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>(); for (int i = 0; i < 10; i++) bucketList.add(new ArrayList<Integer>()); /*按照从右往左的顺序，依次将每一位都当做一次关键字，然后按照该关键字对数组排序， 每一轮排序都基于上轮排序后的结果*/ for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) { /*遍历原始数组，投入桶中*/ for (int j = 0; j < array.length; j++) { int num = (array[j] % mod) / div; bucketList.get(num).add(array[j]); } /*桶中的数据写回原始数组，清除桶，准备下一轮的排序*/ int index = 0; for (int j = 0; j < bucketList.size(); j++) { for (int k = 0; k < bucketList.get(j).size(); k++) array[index++] = bucketList.get(j).get(k); bucketList.get(j).clear(); } } return array; } public static void main(String[] args) { PrintArray.print(PrintArray.SRC); System.out.println("============================================"); int[] dest = RadixSort.sort(PrintArray.SRC); PrintArray.print(dest); }}关于PrintArray类
public class PrintArray { public final static int[] SRC = {86,11,77,23,32,45,58,63,93,4,37,22}; public static void print(int[] array){ for(int i :array){ System.out.print(i+" "); } System.out.println(""); } public static void printIndex(int[] array,int begin ,int end){ for(int i=begin;i<=end;i++){ System.out.print(array[i]+" "); } System.out.println(""); } public static void printObject(ArrayList<Integer> array){ for(int i :array){ System.out.print(i+" "); } System.out.println(""); } public static void printObjectIndex(ArrayList<Integer> array,int begin ,int end){ for(int i=begin;i<=end;i++){ System.out.print(array.get(i)+" "); } System.out.println(""); }}