零：引言
为了方便在程序种测试算法的步骤和正确性，为此写了一个通用的代码如下，方便于在main方法里进行调试
package com.lcyy.day_07; import java.util.ArrayList; public class PrintArray { public final static int[] SRC = {86,39,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(""); } }
一：冒泡排序
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为相关的元素会经由交换慢慢“浮”到数列的顶端。
算法代码：
package com.lcyy.day_07; /** * @author: dlwlrma * @data 2024年07月21日 23:07 * @Description: TODO:手撕十大排序算法----冒泡排序 * 核心思想：1、比较相邻的元素。如果第一个比第二个大(小)，就交换它们两个； * 2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大(小)的数； * 3、针对所有的元素重复以上的步骤，除了最后一个； * 重复步骤1~2，直到排序完成。 */ public class BubbleSort { //核心算法如下 public int[] sortArray(int[] nums){ //防御性编程，先判断数组元素是否为空 if(nums.length == 0){ return nums; } //从第0个元素开始进行比较，nums.length-1-i 表示第nums[nums.length-1-i]个元素已经是比较合适的冒泡位置无需在比较，可以减少比较次数 for (int i = 0; i < nums.length; i++) { for (int j = 0; j < nums.length-1-i; j++) { if(nums[j+1]>nums[j]){ int temp = nums[j+1]; nums[j+1] = nums[j]; nums[j] = temp; } PrintArray.print(nums); } System.out.println("-----------------"); } return nums; } public static void main(String[] args) { PrintArray.print(PrintArray.SRC); System.out.println("========================="); int[] nums = new BubbleSort().sortArray(PrintArray.SRC); PrintArray.print(nums); } }
二：选择排序
选择排序的思想其实和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面。但是过程不同，冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择。
其实选择排序可以看成冒泡排序的优化，因为其目的相同，只是选择排序只有在确定了最大（小）的前提下才进行交换，大大减少了交换的次数。
算法代码：
package com.lcyy.day_07; /** * @author: dlwlrma * @data 2024年07月21日 23:30 * @Description: TODO:手撕十大算法----选择排序 * 核心思想：首先，找到数组中最大（小）的那个元素； * 其次，将它和数组的第一个元素交换位置（如果第一个元素就是最大（小）元素那么它就和自己交换）； * 再次，在剩下的元素中找到最大（小）的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。 */ public class ChoiceSort { public int[] sortArray(int[] nums){ //防御型编程 if (nums.length == 0) { return nums; } //遍历元素 for (int i = 0; i < nums.length; i++) { //最小数的下标 int minIndex = i; for (int j = i; j < nums.length ; j++) { if(nums[j] < nums[minIndex]){ //交换下标，并将新的最小下标保存起来 minIndex = j; } } System.out.println("该轮最小数为："+nums[minIndex]); //交换最小数和i当前所指的元素 int temp = nums[minIndex]; nums[minIndex] = nums[i]; nums[i] = temp; PrintArray.print(nums); System.out.println("--------------------"); } return nums; } public static void main(String[] args) { PrintArray.print(PrintArray.SRC); System.out.println("========================="); int[] nums = new ChoiceSort().sortArray(PrintArray.SRC); PrintArray.print(nums); } }
三：插入排序
插入排序不是通过交换位置而是通过比较找到合适的位置插入元素来达到排序的目的的。相信大家都看过打麻将，在摸牌的时候，拿到一张牌，找到一个合适的位置插入。举个例子，我们手里有3万,4万,6万,8万这几张牌，我们收到5万这张牌，把6万,8万往后移，然后把5万放到原理6万的位置，这个原理其实和插入排序是一样的。
package com.lcyy.day_07; /** * @author: dlwlrma * @data 2024年07月21日 23:59 * @Description: TODO:手撕十大算法----插入排序 * 核心思想：对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。 * 为了给要插入的元素腾出空间，我们需要将插入位置之后的已排序元素在都向右移动一位。 */ public class InsertionSort { public int[] sortArray(int[] nums){ if(nums.length == 0){ return nums; } //当前待排序数据，该元素之前的元素已经被排过 int currentValue; for (int i = 0; i < nums.length-1; i++) { //已被排序数据的索引 int preIndex = i; currentValue = nums[preIndex + 1]; System.out.println("待排序数据索引："+(i+1)+",值为："+currentValue+",已被排序数据的索引为："+preIndex); //在已经被排序过的数据中倒序寻找合适的位置，如果当前待排序数据比比较的元素要小，将比较的元素向后移动一位 while(preIndex >= 0 && currentValue < nums[preIndex]){ //将元素向后移动一位 nums[preIndex + 1] = nums[preIndex]; preIndex--; PrintArray.print(nums); } //当while结束时，说明已经找到了合适的位置，并插入 nums[preIndex + 1] = currentValue; System.out.println("本轮被插入排序后的数组为："); PrintArray.print(nums); System.out.println("-----------------------"); } return nums; } public static void main(String[] args) { PrintArray.print(PrintArray.SRC); System.out.println("========================="); int[] nums = new InsertionSort().sortArray(PrintArray.SRC); PrintArray.print(nums); } }
四：希尔排序
一种基于插入排序的快速的排序算法(请大家先学习插入排序，了解基本的插入排序的思想。对于大规模乱序数组插入排序很慢，因为元素只能一点一点地从数组的一端移动到另一端。例如，如果主键最小的元素正好在数组的尽头，要将它挪到正确的位置就需要N-1 次移动。
希尔排序为了加快速度简单地改进了插入排序，也称为缩小增量排序，同时该算法是冲破O(n^2）的第一批算法之一。核心算法：
package com.lcyy.day_07; /** * @author: dlwlrma * @data 2024年07月22日 19:49 * @Description: TODO:手撕十大排序算法----希尔排序 * 核心思想：希尔排序是把待排序数组按一定增量的分组，对每组使用直接插入排序算法排序； * 然后缩小增量继续分组排序，随着增量逐渐减少，每组包含的元素越来越多，当增量减至 1 时，整个数组恰被分成一组，排序便完成了。 * 这个不断缩小的增量，就构成了一个增量序列。 */ public class ShellSort { public int[] sortArray(int[] nums){ int len = nums.length; int currentValue, temp = len/2; while(temp>0){ for (int i = temp; i <len ; i++) { currentValue = nums[i]; int perIndex = i-temp; while(perIndex>=0 && nums[perIndex]>currentValue){ nums[perIndex+temp] = nums[perIndex]; perIndex = perIndex - temp; } nums[perIndex +temp] = currentValue; } System.out.println("本轮增量{"+temp+"}排序后的数组"); PrintArray.print(nums); System.out.println("---------------------------"); temp/=2; } return nums; } public static void main(String[] args) { PrintArray.print(PrintArray.SRC); System.out.println("============================================"); int[] dest = new ShellSort().sortArray(PrintArray.SRC); PrintArray.print(dest); } }
希尔排序的增量序列
从理论上说，只要一个数组是递减的，并且最后一个值是1，都可以作为增量序列使用。有没有一个步长序列,使得排序过程中所需的比较和移动次数相对较少,并且无论待排序列记录数有多少,算法的时间复杂度都能渐近最佳呢？但是目前从数学上来说，无法证明某个序列是“最好的”。
常用的增量序列有：
希尔增量序列 ：{N/2, (N / 2)/2, ..., 1}，其中N为原始数组的长度，这是最常用的序列，但却不是最好的
Hibbard序列：{2^k-1, ..., 3,1}
Sedgewick序列：{... , 109 , 41 , 19 , 5，1} 表达式为9*4i-9*2i+1 或者 4i-3*2i+1
五：计数排序
计数排序是一个排序时不比较元素大小的排序算法。
计数排序对一定范围内的整数排序时候的速度非常快，一般快于其他排序算法。但计数排序局限性比较大，只限于对整数进行排序，而且待排序元素值分布较连续、跨度小的情况。
如果一个数组里所有元素都是整数，而且都在0-K以内。那对于数组里每个元素来说，如果能知道数组里有多少项小于或等于该元素，就能准确地给出该元素在排序后的数组的位置。
核心算法：
package com.lcyy.day_07; import java.util.Arrays; /** * @author: dlwlrma * @data 2024年07月22日 20:56 * @Description: TODO:手撕十大排序算法----计数排序 */ public class CountingSort { public int[] sortArray(int[] nums) { if (nums.length == 0) return nums; /*寻找数组中最大值，最小值 * bias:偏移量,用以定位原始数组每个元素在计数数组中的下标位置*/ int bias, min = nums[0], max = nums[0]; for (int i = 1; i < nums.length; i++) { if (nums[i] > max) max = nums[i]; if (nums[i] < min) min = nums[i]; } bias = 0 - min; /*获得计数数组的容量*/ int[] counterArray = new int[max - min + 1]; Arrays.fill(counterArray, 0); /*遍历整个原始数组，将原始数组中每个元素值转化为计数数组下标， 并将计数数组下标对应的元素值大小进行累加*/ for (int i = 0; i < nums.length; i++) { counterArray[nums[i] + bias]++; } System.out.println("计数数组为："); PrintArray.print(counterArray); System.out.println("============================================"); int index = 0;/*访问原始数组时的下标计数器*/ int i = 0;/*访问计数数组时的下标计数器*/ /*访问计数数组，将计数数组中的元素转换后，重新写回原始数组*/ while (index < nums.length) { /*只要计数数组中当前下标元素的值不为0，就将计数数组中的元素转换后，重新写回原始数组*/ if (counterArray[i] != 0) { nums[index] = i - bias; counterArray[i]--; index++; } else i++; PrintArray.print(counterArray); PrintArray.print(nums); System.out.println("--------------------"); } return nums; } 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 = new CountingSort().sortArray(src); PrintArray.print(dest); } }
六：桶排序
桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，利用某种函数的映射关系将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序）。
基本步骤是：
- 根据输入建立适当个数的桶，每个桶可以存放某个范围内的元素；
- 将落在特定范围内的所有元素放入对应的桶中；
- 对每个非空的桶中元素进行排序，可以选择通用的排序方法，比如插入、快排；
- 按照划分的范围顺序，将桶中的元素依次取出。排序完成。
桶排序利用函数的映射关系，减少了几乎所有的比较工作。实际上，桶排序的f(k)值的计算，其作用就相当于快排中划分，已经把大量数据分割成了基本有序的数据块(桶)。然后只需要对桶中的少量数据做先进的比较排序即可。
核心算法：
package com.lcyy.day_07; import java.util.ArrayList; /** * @author: dlwlrma * @data 2024年07月22日 21:00 * @Description: TODO:手撕十大排序算法----桶排序 */ public class BucketSort { /** * * @param array * @param bucketCap 桶的容量，即每个桶所能放置多少个不同数值 * @return */ public static ArrayList<Integer> sort(ArrayList<Integer> array, int bucketCap) { 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) / bucketCap + 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) / bucketCap).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 (bucketCap == 1) { for (int j = 0; j < bucketArr.get(i).size(); j++) resultArr.add(bucketArr.get(i).get(j)); } else { if (bucketCount == 1) bucketCap--; System.out.println("对第"+i+"桶中的数据再次用桶进行排序----"); /*对桶中的数据再次用桶进行排序*/ ArrayList<Integer> temp = sort(bucketArr.get(i), bucketCap); 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); } }
七：基数排序
常见的数据元素一般是由若干位组成的，比如字符串由若干字符组成，整数由若干位0~9数字组成。基数排序按照从右往左的顺序，依次将每一位都当做一次关键字，然后按照该关键字对数组的元素入桶，每一轮入桶都基于上轮入桶的结果；完成所有位的入桶后，整个数组就达到有序状态。比如对于数字2985，从右往左就是先以个位为关键字进行入桶，然后是十位、百位、千位，总共需要四轮。基数排序也是一种无需比较的排序算法。
基数是什么意思？对于十进制整数，每一位都只可能是0~9中的某一个，总共10种可能。那10就是它的基，同理二进制数字的基为2；对于字符串，如果它使用的是8位的扩展ASCII字符集，那么它的基就是256。
核心算法：
package com.lcyy.day_07; import java.util.ArrayList; /** * @author: dlwlrma * @data 2024年07月22日 20:54 * @Description: TODO:手撕十大排序算法----基数排序 */ public class RadixSort { public int[] sortArray(int[] nums) { if (nums == null || nums.length < 2) return nums; /*找出最大数*/ int max = nums[0]; for (int i = 1; i < nums.length; i++) { max = Math.max(max, nums[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) { System.out.println("----第"+i+"轮排序-----"); /*遍历原始数组，投入桶中*/ for (int j = 0; j < nums.length; j++) { int num = (nums[j] % mod) / div; bucketList.get(num).add(nums[j]); } /*看看桶中数据的分布*/ for (int b = 0; b < bucketList.size(); b++) { System.out.print("第"+b+"个桶包含数据："); PrintArray.printObject(bucketList.get(b)); } /*桶中的数据写回原始数组，清除桶，准备下一轮的排序*/ int index = 0; for (int j = 0; j < bucketList.size(); j++) { for (int k = 0; k < bucketList.get(j).size(); k++) nums[index++] = bucketList.get(j).get(k); bucketList.get(j).clear(); } } return nums; } public static void main(String[] args) { PrintArray.print(PrintArray.SRC); System.out.println("============================================"); int[] dest = new RadixSort().sortArray(PrintArray.SRC); PrintArray.print(dest); } }
八：归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
若将两个有序表合并成一个有序表，称为2-路归并，与之对应的还有多路归并。
对于给定的一组数据，利用递归与分治技术将数据序列划分成为越来越小的半子表，在对半子表排序后，再用递归方法将排好序的半子表合并成为越来越大的有序序列。
为了提升性能，有时我们在半子表的个数小于某个数（比如15）的情况下，对半子表的排序采用其他排序算法，比如插入排序。
核心算法：
package com.lcyy.day_07; import java.util.Arrays; /** * @author: dlwlrma * @data 2024年07月22日 20:22 * @Description: TODO:手撕十大排序算法----归并排序 * */ public class MergeSort { public int[] sortArray(int[] nums){ if(nums.length <2){ return nums; } //切分数组 int mid = nums.length/2; int[] left = Arrays.copyOfRange(nums,0,mid); int[] right = Arrays.copyOfRange(nums,mid,nums.length); return merge(sortArray(left),sortArray(right)); } 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.println("左子树组："); PrintArray.print(left); System.out.println("右子树组："); PrintArray.print(right); System.out.println("合并后数组："); PrintArray.print(result); System.out.println("---------------------------------------"); return result; } public static void main(String[] args) { PrintArray.print(PrintArray.SRC); System.out.println("============================================"); int[] dest = new MergeSort().sortArray(PrintArray.SRC); PrintArray.print(dest); } }
九：堆排序
许多应用程序都需要处理有序的元素，但不一定要求他们全部有序，或者不一定要一次就将他们排序，很多时候，我们每次只需要操作数据中的最大元素（最小元素），那么有一种基于二叉堆的数据结构可以提供支持。
所谓二叉堆，是一个完全二叉树的结构，同时满足堆的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。在一个二叉堆中，根节点总是最大（或者最小）节点。
核心算法：
package com.lcyy.day_07; /** * @author: dlwlrma * @data 2024年07月22日 20:46 * @Description: TODO:手撕十大排序算法----堆排序 */ public class HeapSort { //声明全局变量，用于记录数组array的长度； private static int len; /* 交换数组内两个元素*/ public static void swap(int[] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } public int[] sortArray(int[] nums) { len = nums.length; if (len < 1) return nums; /*1.构建一个最大堆*/ buildMaxHeap(nums); /*2.循环将堆首位（最大值）与未排序数据末位交换，然后重新调整为最大堆*/ while (len > 0) { swap(nums, 0, len - 1); len--; adjustHeap(nums, 0); PrintArray.print(nums); System.out.println("--------------------"); } return nums; } /** * 建立最大堆 */ 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("============================================"); } /** * 调整使之成为最大堆 */ 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]&&array[right]>array[left]) maxIndex = right; /*如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。*/ if (maxIndex != i) { swap(array, maxIndex, i); PrintArray.print(array); adjustHeap(array, maxIndex); } } public static void main(String[] args) { PrintArray.print(PrintArray.SRC); System.out.println("============================================"); int[] dest = new HeapSort().sortArray(PrintArray.SRC); PrintArray.print(dest); } }
十：快速排序
快速排序（Quicksort）是对冒泡排序的一种改进，也是采用分治法的一个典型的应用。
首先任意选取一个数据（比如数组的第一个数）作为关键数据，我们称为基准数，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序，也称为分区（partition）操作。在实际实现时，一般会在原数组上直接操作。
通过一趟快速排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
核心算法：
package com.lcyy.day_07; /** * @author: dlwlrma * @data 2024年07月22日 20:49 * @Description: TODO:手撕十大排序算法----快速排序 */ public class QuickSort { public int[] sortArray(int[] nums) { return sort(nums,0,nums.length-1); } 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; } /** * 快速排序分区方法 */ public static int partition(int[] array, int start, int end) { /*只有一个元素时，无需再分区*/ if(start == end) return start; /*随机选取一个基准数*/ int pivot = (int) (start + Math.random() * (end - start + 1)); /*zoneIndex是分区指示器，初始值为分区头元素下标减一*/ int zoneIndex = start - 1; System.out.println("开始下标："+start+",结束下标:"+end+",基准数下标：" +pivot+",元素值:"+array[pivot]+"，分区指示器下标："+zoneIndex); /*将基准数和分区尾元素交换位置*/ 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+",遍历指示器:"+i); PrintArray.printIndex(array,start,end); } System.out.println("---------------"); return zoneIndex; } /** * 交换数组内两个元素 */ 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 = new QuickSort().sortArray(PrintArray.SRC); PrintArray.print(dest); } }
核心算法2：
package com.lcyy.day_07; /** * @author: dlwlrma * @data 2024年07月22日 20:51 * @Description: TODO:手撕十大排序算法----快速排序2 */ public class QuickSort2 { public int[] sortArray(int[] nums) { return sort(nums,0,nums.length-1); } public static int[] sort(int[] array, int start, int end) { if (array.length < 1 || start < 0 || end >= array.length || start > end) return null; if(end-start < 15) { insertSort(array,start,end); }else{ /*数据分割成独立的两部分时，从哪儿分区的指示器*/ 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; } /** * 快速排序分区方法 */ public static int partition(int[] array, int start, int end) { /*只有一个元素时，无需再分区*/ if(start == end) return start; /*随机选取一个基准数*/ int pivot = (int) (start + Math.random() * (end - start + 1)); /*zoneIndex是分区指示器，初始值为分区头元素下标减一*/ int zoneIndex = start - 1; System.out.println("开始下标："+start+",结束下标:"+end+",基准数下标：" +pivot+",元素值:"+array[pivot]+"，分区指示器下标："+zoneIndex); /*将基准数和分区尾元素交换位置*/ 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+",遍历指示器:"+i); PrintArray.printIndex(array,start,end); } System.out.println("---------------"); return zoneIndex; } private static void insertSort(int[] nums, int start, int end){ int currentValue;/*当前待排序数据，该元素之前的元素均已被排序过*/ for (int i = start; i <= end-1; i++) { int preIndex = i;/*已被排序数据的索引*/ currentValue = nums[preIndex + 1]; System.out.println("待排序元素索引:" + (i + 1) + "，值为：" + currentValue + ",已被排序数据的索引:" + preIndex); /*在已被排序过数据中倒序寻找合适的位置，如果当前待排序数据比比较的元素要小， 将比较的元素元素后移一位*/ while (preIndex >= 0 && currentValue < nums[preIndex]) { //将当前元素后移一位 nums[preIndex + 1] = nums[preIndex]; preIndex--; PrintArray.print(nums); } /*while循环结束时，说明已经找到了当前待排序数据的合适位置，插入*/ nums[preIndex + 1] = currentValue; } } /** * 交换数组内两个元素 */ 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 = new QuickSort2().sortArray(PrintArray.SRC); PrintArray.print(dest); } }
快速排序种的基准数：
基准的选取：最优的情况是基准值刚好取在无序区的中间，这样能够最大效率地让两边排序，同时最大地减少递归划分的次数，但是一般很难做到最优。基准的选取一般有三种方式，选取数组的第一个元素，选取数组的最后一个元素，以及选取第一个、最后一个以及中间的元素的中位数（如4 5 6 7, 第一个4, 最后一个7, 中间的为5, 这三个数的中位数为５, 所以选择5作为基准）。
Dual-Pivot快排：两个基准数的快速排序算法，其实就是用两个基准数, 把整个数组分成三份来进行快速排序，在这种新的算法下面，比经典快排从实验来看节省了10%的时间。
为了提升性能，有时我们在分割后独立的两部分的个数小于某个数（比如15）的情况下，会采用其他排序算法，比如插入排序。
十大排序算法的总结
基数排序VS基数排序VS桶排序对比
基数排序有两种方法：
- MSD 从高位开始进行排序
- LSD 从低位开始进行排序
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
- 基数排序：根据键值的每位数字来分配桶
- 计数排序：每个桶只存储单一键值
- 桶排序：每个桶存储一定范围的数值
排序算法时间复杂度记忆技巧
冒泡、选择、插入排序需要两个for循环，每次只关注一个元素，平均时间复杂度为O(n²）（外循环找元素O(n)，内循环找位置O(n)）
快速、归并、希尔、堆基于分治思想，log以2为底，平均时间复杂度往往和O(nlogn)（外循环找元素O(n)，内循环找位置O(logn)）相关
