学习视频推荐
工具网站
代码设计原则
模板方法
public abstract class BaseSort { public abstract <E extends Comparable<E>> void sort(E[] a); public static <E> void swap(E[] a, int min, int i) { E temp = a[min]; a[min] = a[i]; a[i] = temp; } }
生成随机数组
public class ArrayGenerator { private ArrayGenerator() { } /** * 生成顺序数组 * * @param n:数组规模 * @return java.lang.Integer[] * @author wangjie * @date 2023/3/8 19:27 * @since 1.0.0 */ public static Integer[] generateOrderedArray(int n) { Integer[] arr = new Integer[n]; for (int i = 0; i < n; i++) { arr[i] = i; } return arr; } /** * 生成随机数组 * * @param n:数组规模 * @param bound：随机数字的范围 0 <= nextInt结果 < bound。 * @return java.lang.Integer[] * @author wangjie * @date 2023/3/8 19:27 * @since 1.0.0 */ public static Integer[] generateRandomArray(int n, int bound) { Integer[] arr = new Integer[n]; Random rnd = new Random(); for (int i = 0; i < n; i++) { arr[i] = rnd.nextInt(bound); } return arr; } }
package com.onethink.util; import com.onethink.sort.BaseSort; public class SortHelper { private SortHelper() { } /** * 判断是否顺序排序完成 * * @return boolean * @author wangjie * @date 2023/3/8 18:57 * @since 1.0.0 */ public static <E extends Comparable<E>> boolean isSorted(E[] arr) { boolean forwardFlag = true; for (int i = 0; i < arr.length - 1; i++) { if (arr[i].compareTo(arr[i + 1]) > 0) { forwardFlag = false; } } boolean reverseFlag = true; for (int i = arr.length - 1; i > 0; i--) { if (arr[i - 1].compareTo(arr[i]) < 0) { reverseFlag = false; } } return forwardFlag || reverseFlag; } /** * 判断是否顺序排序完成 * * @return boolean * @author wangjie * @date 2023/3/8 18:57 * @since 1.0.0 */ public static <E extends Comparable<E>> void sortTest(String sortName, E[] arr) { long startTime = System.nanoTime(); Object o = null; try { Class<?> clazz = Class.forName(sortName); BaseSort sortClas = (BaseSort) clazz.newInstance(); sortClas.sort(arr); } catch (Exception e) { throw new RuntimeException(e); } long endTime = System.nanoTime(); double time = (endTime - startTime) / 1000000000.0; if (!SortHelper.isSorted(arr)) { throw new RuntimeException(sortName + " failed"); } System.out.println(String.format("%s算法，数据规模n = %d , 耗时%f s", sortName, arr.length, time)); } }
冒泡排序
冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
排序前 :
{21 ,4, 5, 6, 15, 3, 2, 1}排序后 :
{1, 2, 3, 4, 5, 6, 15, 21}排序原理
- 比较相邻的元素。如果前一个元素比后一个元素大，就交换这两个元素的位置。
- 对每一对相邻元素做同样的工作，从开始第一对元素到结尾的最后一对元素。最终最后位置的元素就是最大值。
核心思路
假设数组长度为N
最细粒度的两两比较即为内层循环代码体.比较轮数为外层循环
总轮数=N-1,每轮参加比较的元素下标 0到 N-1 -轮数
API设计
public class Bubble { /* 对数组a中的元素进行升序排序 */ public static void sort(Comparable[] a){ for(int i=a.length-1;i>0;i--){ for(int j=0;j<i;j++){ //比较索引j和索引j+1处的值 if (greater(a[j],a[j+1])){ exch(a,j,j+1); } } } } /* 比较v元素是否大于w元素 */ private static boolean greater(Comparable v,Comparable w){ return v.compareTo(w)>0; } /* 数组元素i和j交换位置 */ private static void exch(Comparable[] a,int i,int j){ Comparable temp; temp = a[i]; a[i]=a[j]; a[j]=temp; } }
public class BubbleTest { public static void main(String[] args) { Integer[] arr = {21,4,5,6,15,3,2,1}; Bubble.sort(arr); System.out.println(Arrays.toString(arr));//[1, 2, 3, 4, 5, 6, 15, 21] } }
复杂度分析
冒泡排序使用了双层for循环，其中内层循环的循环体是真正完成排序的代码，所以，我们分析冒泡排序的时间复杂度，主要分析一下内层循环体的执行次数即可。
在最坏情况下，也就是假如要排序的元素为逆序，那么：元素比较的次数为：
元素交换的次数为：
总执行次数为：
按照大O推导法则，保留函数中的最高阶项那么最终冒泡排序的时间复杂度为O().
冒泡排序优化-鸡尾酒
- 当某一轮冒泡，不需要交换元素，说明数组此时已经有序，停止下轮比较
- 当数组部分有序时，单一方向冒泡，会导致更多轮排序
比如从左往右冒泡的时候，最小元素1靠右，需要排5轮
排序轮次 | 结果 |
1 | 234516 |
2 | 234156 |
3 | 231456 |
4 | 213456 |
5 | 123456 |
第一轮从左往右，第二轮从右往左，只需要三轮（第三轮发现不需要交换，数组已经有序，停止排序）
public static void optimizeSort(Comparable[] a) { //第一轮冒泡,最后一个元素为最大元素， for (int i = a.length - 1; i > 0; i--) { //比较0到倒数第二个元素 boolean leftSorted = true; for (int j = 0; j < i; j++) { if (greater(a[j], a[j + 1])) { exchange(a, j, j + 1); leftSorted = false; } } if (leftSorted){ break; } //反向冒泡 boolean rightSorted = true; for (int j = i; j > a.length - 1 - i; j--) { if (greater(a[j - 1], a[j])) { exchange(a, j - 1, j); rightSorted = false; } } if (rightSorted){ break; } } }
选择排序
选择排序
Selection-sort是一种简单直观的排序算法排序原理
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
需求：
排序前：
{4,6,8,7,9,2,10,1}
排序后：{1,2,4,5,7,8,9,10}算法描述
- 每一次遍历的过程中，都假定第一个索引处的元素是最小值，和其他索引处的值依次进行比较，如果当前索引处的值大于其他某个索引处的值，则假定其他某个索引出的值为最小值，最后可以找到最小值所在的索引。
- 交换第一个索引处和最小值所在的索引处的值。
API设计
public class SelectSort extends BaseSort { public static void main(String[] args) { int[] dataSize = {10000, 100000}; for (int n : dataSize) { Integer[] arr = ArrayGenerator.generateRandomArray(n, n); SortHelper.sortTest("com.onethink.sort.SelectSort", arr); } } @Override public <E extends Comparable<E>> void sort(E[] a) { for (int i = 0; i < a.length; i++) { int min = i; for (int j = i; j < a.length; j++) { if (a[min].compareTo(a[j]) > 0) { min = j; } } swap(a, min, i); } } }
时间复杂度分析
选择排序使用了双层for循环，其中外层循环完成了数据交换，内层循环完成了数据比较，所以我们分别统计数据交换次数和数据比较次数：数据比较次数：
数据交换次数：N-1
时间复杂度：
根据大O推导法则，保留最高阶项，去除常数因子，时间复杂度为O();
表现最稳定的排序算法之一，因为无论什么数据进去都是O()的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。
插入排序
插入排序（Insertion sort）是一种简单直观且稳定的排序算法。
插入排序的工作方式非常像人们排序一手扑克牌一样。开始时，我们的左手为空并且桌子上的牌面朝下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较。
需求：排序前：
{4,3,2,10,12,1,5,6} 排序后：{1,2,3,4,5,6,10,12}排序原理
- 把所有的元素分为两组，已经排序的和未排序的；
- 找到未排序的组中的第一个元素，向已经排序的组中进行插入；
- 倒叙遍历已经排序的元素，依次和待插入的元素进行比较，直到找到一个元素小于等于待插入元素，那么就把待插入元素放到这个位置，其他的元素向后移动一位
API设计
public class InsertSort extends BaseSort { @Override public <E extends Comparable<E>> void sort(E[] a) { //默认0为已经排序的，外层循环从1开始，代表未排序的 for (int i = 1; i < a.length; i++) { //倒序遍历已经排序的数组 for (int j = i; j > 0; j--) { //如果已经排序的数组元素大于未排序元素，则交换 if ((a[j - 1].compareTo(a[j])) > 0) { swap(a, j - 1, j); } else { //找到已经排序的数组元素小于等于未排序，则找到了待排序元素位置，停止遍历已经排序的数组 break; } } } } public static void main(String[] args) { int[] dataSize = {10000, 100000}; for (int n : dataSize) { Integer[] arr = ArrayGenerator.generateRandomArray(n, n); SortHelper.sortTest("com.onethink.sort.InsertSort", arr); } //com.onethink.sort.InsertSort算法，数据规模n = 10000 , 耗时0.095334 s //com.onethink.sort.InsertSort算法，数据规模n = 100000 , 耗时8.954800 s //根据结果 O(n) int[] dataSize2 = {10000, 100000}; for (int n : dataSize2) { Integer[] arr = ArrayGenerator.generateRandomArray(n, n); SortHelper.sortTest("com.onethink.sort.InsertSort2", arr); } // com.onethink.sort.InsertSort2算法，数据规模n = 10000 , 耗时0.087319 s // com.onethink.sort.InsertSort2算法，数据规模n = 100000 , 耗时7.186170 s }
插入排序使用了双层for循环，其中内层循环的循环体是真正完成排序的代码，所以，我们分析插入排序的时间复杂度，主要分析一下内层循环体的执行次数即可。
最坏情况，也就是待排序的数组元素为{12,10,6,5,4,3,2,1}，那么：比较的次数为：
交换的次数为：
总执行次数为：
按照大O推导法则，保留函数中的最高阶项那么最终插入排序的时间复杂度为O().
小优化
public class InsertSort2 extends BaseSort { /** * 对插入排序的优化 优化swap操作，原有的swap需要操作三次 * 优化： 对于a[i] 元素 插入到[0,i-1]时候，如果a[i]小于已经排序的元素j， * 将[j-1,i-1]的元素移动一位，a[j]= a[i] * * @param a: * @return void * @author wangjie * @date 2023/3/8 22:12 * @since 1.0.0 */ @Override public <E extends Comparable<E>> void sort(E[] a) { //默认0为已经排序的，外层循环从1开始，代表未排序的 for (int i = 1; i < a.length; i++) { //倒序遍历已经排序的数组 E temp = a[i]; int j = i; for (; j > 0; j--) { //如果已经排序的数组元素大于未排序元素，则交换 if ((a[j - 1].compareTo(temp)) > 0) { a[j] = a[j - 1]; } else { //找到已经排序的数组元素小于等于未排序，则找到了待排序元素位置，停止遍历已经排序的数组 break; } // } a[j] = temp; } } }
最好时间复杂度
当数组本身有序的时候，插入排序的时间复杂度为O(n)
希尔排序
希尔排序是插入排序的一种，又称“缩小增量排序”，是插入排序算法的一种更高效的改进版本。它与插入排序的不同之处在于，它会优先比较距离较远的元素。
需求：
排序前：
{9,1,2,5,7,4,8,6,3,5}
排序后：{1,2,3,4,5,5,6,7,8,9}排序原理
1.选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组；
2.对分好组的每一组数据完成插入排序；
3.减小增长量，最小减为1，重复第二步操作。
public class Shell { /* 对数组a中的元素进行排序 */ public static void sort(Comparable[] a){ //1.根据数组a的长度，确定增长量h的初始值； int h = 1; while(h<a.length/2){ h=2*h+1; } //2.希尔排序 while(h>=1){ //排序 //2.1.找到待插入的元素 for (int i=h;i<a.length;i++){ //2.2把待插入的元素插入到有序数列中 for (int j=i;j>=h;j-=h){ //待插入的元素是a[j],比较a[j]和a[j-h] if (greater(a[j-h],a[j])){ //交换元素 exch(a,j-h,j); }else{ //待插入元素已经找到了合适的位置，结束循环； break; } } } //减小h的值 h= h/2; } } /* 比较v元素是否大于w元素 */ private static boolean greater(Comparable v,Comparable w){ return v.compareTo(w)>0; } /* 数组元素i和j交换位置 */ private static void exch(Comparable[] a,int i,int j){ Comparable temp; temp = a[i]; a[i]=a[j]; a[j]=temp; } }
二路归并排序
归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
需求：
排序前：{8,4,5,7,1,3,6,2}
排序后：{1,2,3,4,5,6,7,8}
排序原理
1.尽可能的一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数是1为止。
2.将相邻的两个子组进行合并成一个有序的大组；
3.不断的重复步骤2，直到最终只有一个组为止
最核心的merge代码,合并两个有序数组
从数列的角度来理解
API设计
public class Merge { //归并所需要的辅助数组 private static Comparable[] assist; /* 比较v元素是否小于w元素 */ private static boolean less(Comparable v, Comparable w) { return v.compareTo(w)<0; } /* 数组元素i和j交换位置 */ private static void exch(Comparable[] a, int i, int j) { Comparable t = a[i]; a[i] = a[j]; a[j] = t; } /* 对数组a中的元素进行排序 */ public static void sort(Comparable[] a) { //1.初始化辅助数组assist； assist = new Comparable[a.length]; //2.定义一个lo变量，和hi变量，分别记录数组中最小的索引和最大的索引； int lo=0; int hi=a.length-1; //3.调用sort重载方法完成数组a中，从索引lo到索引hi的元素的排序 sort(a,lo,hi); } /* 对数组a中从lo到hi的元素进行排序 */ private static void sort(Comparable[] a, int lo, int hi) { //做安全性校验； if (hi<=lo){ return; } //对lo到hi之间的数据进行分为两个组 int mid = lo+(hi-lo)/2;// 5,9 mid=7 //分别对每一组数据进行排序 sort(a,lo,mid); sort(a,mid+1,hi); //再把两个组中的数据进行归并 merge(a,lo,mid,hi); } /* 对数组中，从lo到mid为一组，从mid+1到hi为一组，对这两组数据进行归并 */ private static void merge(Comparable[] a, int lo, int mid, int hi) { //定义三个指针 int i=lo; int p1=lo; int p2=mid+1; //遍历，移动p1指针和p2指针，比较对应索引处的值，找出小的那个，放到辅助数组的对应索引处 while(p1<=mid && p2<=hi){ //比较对应索引处的值 if (less(a[p1],a[p2])){ assist[i++] = a[p1++]; }else{ assist[i++]=a[p2++]; } } //遍历，如果p1的指针没有走完，那么顺序移动p1指针，把对应的元素放到辅助数组的对应索引处 while(p1<=mid){ assist[i++]=a[p1++]; } //遍历，如果p2的指针没有走完，那么顺序移动p2指针，把对应的元素放到辅助数组的对应索引处 while(p2<=hi){ assist[i++]=a[p2++]; } //把辅助数组中的元素拷贝到原数组中 for(int index=lo;index<=hi;index++){ a[index]=assist[index]; } } }
归并排序时间复杂度分析：
归并排序是分治思想的最典型的例子，上面的算法中，对a[lo...hi]进行排序，先将它分为a[lo...mid]和a[mid+1...hi]两部分，分别通过递归调用将他们单独排序，最后将有序的子数组归并为最终的排序结果。该递归的出口在于如果一个数组不能再被分为两个子数组，那么就会执行merge进行归并，在归并的时候判断元素的大小进行排序。
用树状图来描述归并，如果一个数组有8个元素，那么它将每次除以2找最小的子数组，共拆log8次，值为3，所以树共有3层,
那么自顶向下第k层有个子数组，每个数组的长度为，归并最多需要次比较。因此每层的比较次数为 ,那么3层总共为。
假设元素的个数为n，那么使用归并排序拆分的次数为log2(n),所以共log2(n)层，那么使用log2(n)替换上面中的3这个层数，最终得出的归并排序的时间复杂度为：
,根据大O推导法则，忽略底数，最终归并排序的时间复杂度为O(nlogn);
归并排序的缺点：
需要申请额外的数组空间，导致空间复杂度提升，是典型的以空间换时间的操作。
插入排序、希尔排序、归并排序性能比较:
测试数据文件夹下有一个reverse_arr.txt文件，里面存放的是从1000000到1的逆向数据，我们可以根据这个批量数据完成测试。测试的思想：在执行排序前前记录一个时间，在排序完成后记录一个时间，两个时间的时间差就是排序的耗时。
public class SortCompare { //调用不同的测试方法，完成测试 public static void main(String[] args) throws Exception{ //1.创建一个ArrayList集合，保存读取出来的整数 ArrayList<Integer> list = new ArrayList<>(); //2.创建缓存读取流BufferedReader，读取数据，并存储到ArrayList中； BufferedReader reader = new BufferedReader(new InputStreamReader(SortCompare.class.getClassLoader().getResourceAsStream("reverse_arr.txt"))); String line=null; while((line=reader.readLine())!=null){ //line是字符串，把line转换成Integer，存储到集合中 int i = Integer.parseInt(line); list.add(i); } reader.close(); //3.把ArrayList集合转换成数组 Integer[] a = new Integer[list.size()]; list.toArray(a); //4.调用测试代码完成测试 // testInsertion(a);//37184毫秒 testShell(a);//32毫秒 // testMerge(a);//31毫秒 } //测试希尔排序 public static void testShell(Integer[] a){ //1.获取执行之前的时间 long start = System.currentTimeMillis(); //2.执行算法代码 Shell.sort(a); //3.获取执行之后的时间 long end = System.currentTimeMillis(); //4.算出程序执行的时间并输出 System.out.println("希尔排序执行的时间为："+(end-start)+"毫秒"); } //测试插入排序 public static void testInsertion(Integer[] a){ //1.获取执行之前的时间 long start = System.currentTimeMillis(); //2.执行算法代码 Insertion.sort(a); //3.获取执行之后的时间 long end = System.currentTimeMillis(); //4.算出程序执行的时间并输出 System.out.println("插入排序执行的时间为："+(end-start)+"毫秒"); } //测试归并排序 public static void testMerge(Integer[] a){ //1.获取执行之前的时间 long start = System.currentTimeMillis(); //2.执行算法代码 Merge.sort(a); //3.获取执行之后的时间 long end = System.currentTimeMillis(); //4.算出程序执行的时间并输出 System.out.println("归并排序执行的时间为："+(end-start)+"毫秒"); } }
多路归并排序
待续
快排
快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
需求：
排序前:{6, 1, 2, 7, 9, 3, 4, 5, 8}
排序后:{1, 2, 3, 4, 5, 6, 7, 8, 9}
排序原理
1.首先设定一个分界值，通过该分界值将数组分成左右两部分；
2.将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值；
3.然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
4.重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了。
分组找中间值
API设计
public class Quick { /* 比较v元素是否小于w元素 */ private static boolean less(Comparable v, Comparable w) { return v.compareTo(w) < 0; } /* 数组元素i和j交换位置 */ private static void exch(Comparable[] a, int i, int j) { Comparable t = a[i]; a[i] = a[j]; a[j] = t; } //对数组内的元素进行排序 public static void sort(Comparable[] a) { int lo = 0; int hi = a.length-1; sort(a,lo,hi); } //对数组a中从索引lo到索引hi之间的元素进行排序 private static void sort(Comparable[] a, int lo, int hi) { //安全性校验 if (hi<=lo){ return; } //需要对数组中lo索引到hi索引处的元素进行分组（左子组和右子组）； int partition = partition(a, lo, hi);//返回的是分组的分界值所在的索引，分界值位置变换后的索引 //让左子组有序 sort(a,lo,partition-1); //让右子组有序 sort(a,partition+1,hi); } //对数组a中，从索引 lo到索引 hi之间的元素进行分组，并返回分组界限对应的索引 public static int partition(Comparable[] a, int lo, int hi) { //确定分界值 Comparable key = a[lo]; //定义两个指针，分别指向待切分元素的最小索引处和最大索引处的下一个位置 int left=lo; int right=hi+1; //切分 while(true){ //先从右往左扫描，移动right指针，找到一个比分界值小的元素，停止 while(less(key,a[--right])){ if (right==lo){ break; } } //再从左往右扫描，移动left指针，找到一个比分界值大的元素，停止 while(less(a[++left],key)){ if (left==hi){ break; } } //判断 left>=right,如果是，则证明元素扫描完毕，结束循环，如果不是，则交换元素即可 if (left>=right){ break; }else{ exch(a,left,right); } } //交换分界值 exch(a,lo,right); return right; } }
快速排序时间复杂度分析：
快速排序的一次切分从两头开始交替搜索，直到left和right重合，因此，一次切分算法的时间复杂度为O(n),但整个快速排序的时间复杂度和切分的次数相关。
最优情况：每一次切分选择的基准数字刚好将当前序列等分。
如果我们把数组的切分看做是一个树，那么上图就是它的最优情况的图示，共切分了logn次，所以，最优情况下快速排序的时间复杂度为O(nlogn);
最坏情况：每一次切分选择的基准数字是当前序列中最大数或者最小数，这使得每次切分都会有一个子组，那么总共就得切分n次，所以，最坏情况下，快速排序的时间复杂度为O();
快速排序和归并排序的区别
快速排序是另外一种分治的排序算法，它将一个数组分成两个子数组，将两部分独立的排序。快速排序和归并排序是互补的：
归并排序将数组分成两个子数组分别排序，并将有序的子数组归并从而将整个数组排序，而快速排序的方式则是当两个数组都有序时，整个数组自然就有序了。在归并排序中，一个数组被等分为两半，归并调用发生在处理整个数组之前，在快速排序中，切分数组的位置取决于数组的内容，递归调用发生在处理整个数组之后。
快速排序优化
基准值取两端的话,在特殊情况一下,会导致更容易StackOverFlow
比如数组是逆序的,需要顺序排列,此时0号为基准值,则每次的分区后基准值都是数组的索引降序,如果数组的长度超过编程语言的栈深度,则会报错
/** * 1。 left指针从左到右，找到比基准值大的则停止 * 2。 right指针从右到左，找到比基准值小的则停止 * 3。 交换left，right的值， * 4。 重复上述步骤，直到left>=right * 5。 交互right处索引和基准值 * 6。 right为新的基准索引 * * @param arr: 原数组 * @param lo: 分组的开始索引 * @param hi: 分组的结束索引 * @return int: 返回的基准值索引 * @author wangjie * @date 2022/12/28 10:06 * @since 1.0.0 */ private static int partition(Comparable[] arr, int lo, int hi) { int k = (lo + hi) / 2; int left = lo - 1; int right = hi + 1; while (true) { while (greater(arr[k], arr[++left])) { if (left == hi) { break; } } while (greater(arr[--right], arr[k])) { if (right == lo) { break; } } if (left >= right) { break; } else { exchange(arr, left, right); } } exchange(arr, k, right); return right; }
堆排序
给定一个数组：
String[] arr = {"S","O","R","T","E","X","A","M","P","L","E"}
请对数组中的字符按从小到大排序。
实现步骤：
1.构造堆；
2.得到堆顶元素，这个值就是最大值；
3.交换堆顶元素和数组中的最后一个元素，此时所有元素中的最大元素已经放到合适的位置；
4.对堆进行调整，重新让除了最后一个元素的剩余元素中的最大值放到堆顶；
5.重复2~4这个步骤，直到堆中剩一个元素为止。
堆构造过程
堆的构造，最直观的想法就是另外再创建一个和新数组数组，然后从左往右遍历原数组，每得到一个元素后，添加到新数组中，并通过上浮，对堆进行调整，最后新的数组就是一个堆。
上述的方式虽然很直观，也很简单，但是我们可以用更聪明一点的办法完成它。创建一个新数组，把原数组
0~length-1的数据拷贝到新数组的1~length处，再从新数组长度的一半处开始往1索引处扫描（从右往左），然后对扫描到的每一个元素做下沉调整即可。
堆排序过程
对构造好的堆，我们只需要做类似于堆的删除操作，就可以完成排序。
- 将堆顶元素和堆中最后一个元素交换位置；
- 通过对堆顶元素下沉调整堆，把最大的元素放到堆顶(此时最后一个元素不参与堆的调整，因为最大的数据已经到了数组的最右边)
- 重复1~2步骤，直到堆中剩最后一个元素。
public class HeapSort { //判断heap堆中索引i处的元素是否小于索引j处的元素 private static boolean less(Comparable[] heap, int i, int j) { return heap[i].compareTo(heap[j])<0; } //交换heap堆中i索引和j索引处的值 private static void exch(Comparable[] heap, int i, int j) { Comparable tmp = heap[i]; heap[i] = heap[j]; heap[j] = tmp; } //根据原数组source，构造出堆heap private static void createHeap(Comparable[] source, Comparable[] heap) { //把source中的元素拷贝到heap中，heap中的元素就形成一个无序的堆 System.arraycopy(source,0,heap,1,source.length); //对堆中的元素做下沉调整(从长度的一半处开始，往索引1处扫描) for (int i = (heap.length)/2;i>0;i--){ sink(heap,i,heap.length-1); } } //对source数组中的数据从小到大排序 public static void sort(Comparable[] source) { //构建堆 Comparable[] heap = new Comparable[source.length+1]; createHeap(source,heap); //定义一个变量，记录未排序的元素中最大的索引 int N = heap.length-1; //通过循环，交换1索引处的元素和排序的元素中最大的索引处的元素 while(N!=1){ //交换元素 exch(heap,1,N); //排序交换后最大元素所在的索引，让它不要参与堆的下沉调整 N--; //需要对索引1处的元素进行对的下沉调整 sink(heap,1, N); } //把heap中的数据复制到原数组source中 System.arraycopy(heap,1,source,0,source.length); } //在heap堆中，对target处的元素做下沉，范围是0~range private static void sink(Comparable[] heap, int target, int range){ while(2*target<=range){ //1.找出当前结点的较大的子结点 int max; if (2*target+1<=range){ if (less(heap,2*target,2*target+1)){ max = 2*target+1; }else{ max = 2*target; } }else{ max = 2*target; } //2.比较当前结点的值和较大子结点的值 if (!less(heap,target,max)){ break; } exch(heap,target,max); target = max; } } }
桶排序
排序的稳定性
稳定性的定义：
数组arr中有若干元素，其中A元素和B元素相等，并且A元素在B元素前面，如果使用某种排序算法排序后，能够保证A元素依然在B元素的前面，可以说这个该算法是稳定的。
稳定性的意义：
如果一组数据只需要一次排序，则稳定性一般是没有意义的，如果一组数据需要多次排序，稳定性是有意义的。例如要排序的内容是一组商品对象，第一次排序按照价格由低到高排序，第二次排序按照销量由高到低排序，如果第二次排序使用稳定性算法，就可以使得相同销量的对象依旧保持着价格高低的顺序展现，只有销量不同的对象才需要重新排序。这样既可以保持第一次排序的原有意义，而且可以减少系统开销。
常见排序算法的稳定性
冒泡排序：
只有当arr[i]>arr[i+1]的时候，才会交换元素的位置，而相等的时候并不交换位置，所以冒泡排序是一种稳定排序算法。
选择排序:
选择排序是给每个位置选择当前元素最小的,例如有数据{5(1)，8 ，5(2)， 2， 9 },第一遍选择到的最小元素为2，所以5(1)会和2进行交换位置，此时5(1)到了5(2)后面，破坏了稳定性，所以选择排序是一种不稳定的排序算法。
插入排序：
比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么把要插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
希尔排序：
希尔排序是按照不同步长对元素进行插入排序 ,虽然一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。
归并排序：
归并排序在归并的过程中，只有arr[i]<arr[i+1]的时候才会交换位置，如果两个元素相等则不会交换位置，所以它并不会破坏稳定性，归并排序是稳定的。
快速排序：
快速排序需要一个基准值，在基准值的右侧找一个比基准值小的元素，在基准值的左侧找一个比基准值大的元素，然后交换这两个元素，此时会破坏稳定性，所以快速排序是一种不稳定的算法
各大排序算法复杂度总览
相关概念
- 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
- 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
- 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
- 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。