600字范文 > 史上最容易理解的《十大经典算法（动态图展示）》

史上最容易理解的《十大经典算法（动态图展示）》

时间：2019-09-20 18:12:43

十大经典排序算法

部分内容引用自：/onepixel/articles/7674659.html

感谢作者贡献，如需删除请联系本人！

0、排序算法说明

0.1排序分类

非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。

线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。

0.2 术语说明

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；内排序：所有排序操作都在内存中完成；外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；时间复杂度：一个算法执行所耗费的时间。空间复杂度：运行完一个程序所需内存的大小。

0.3 算法总结

图片名词解释：

n: 数据规模k: “桶”的个数In-place: 占用常数内存，不占用额外内存Out-place: 占用额外内存

1、冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

1.1 算法描述

比较相邻的元素。如果第一个比第二个大，就交换它们两个；对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；针对所有的元素重复以上的步骤，除了最后一个；重复步骤1~3，直到排序完成。

1.2 动图演示

1.3 代码实现

package cn.fuqiang.arithmetic;import parator;/*** 冒泡排序* @author 王福强* @Title: BubbleSort.java * @Package cn.fuqiang.arithmetic* @Description 冒泡排序实现* @date 6月8日下午4:18:37*/public class BubbleSort<T> {public static void main(String[] args) {int[] arr = {4,1,5,3,8,10,28,2};sort(arr);so(arr);Integer[] arr2 = {4,1,5,3,8,10,28,2};sort(arr2,(a,b)-> pareTo(a));so(arr2);}/*** 冒泡排序 (特点：从后往前)* 原理：前后元素两两之间进行比较把大的往后扔* 升序(从后往前，从大到小) * 外层循环是控制内层循环的次数，也就是说外层循环每循环一遍，让内层循环每次循环的次数减一次* 这样就保证内层循环每次循环结束后最后面一个都是最大* 例如： 3 6 4 1 * 外循环第一次结束后，内循环会把6放到最后面 3 4 1 6* 外循环第二次开始时，内循环的循环次数会减一也就是说 6 不会在参与比较* 外循环第二次结束时，内循环会把4放到最后面 3 1 4 * 以此类推。。。。* 外循环第三次结束时内循环 1 3 4* .。。。。1 3* .。。。。 1* 最终结果 1 3 4 6* @param t*/public static void sort(int[] t) {for(int i=0;i<t.length;i++) {int temp;for(int j = 0;j<t.length-1-i;j++) {if(t[j]>t[j+1]) {temp = t[j];t[j]=t[j+1];t[j+1]=temp;}}}}/*** 冒泡排序对象类型排序 * 对象必须实现Comparator接口* @param t 要遍历的数组* @param comparator 定制的遍历规则*/public static <T>void sort(T[] t,Comparator<? super T> comparator) {for(int i = 0;i<t.length-1;i++) {T temp;for(int j = 1;j<t.length-i;j++) {if(pare(t[j-1], t[j])<0) {temp = t[j-1];t[j-1]=t[j];t[j]=temp;}}}}/*** 传入任意数组或对象输出到控制台* @author 王福强* @Description 前提是传入的对象必须重写 toString()方法* @date 6月8日下午4:26:06* @param obj*/public static void so(Object obj) {String str = "";if(obj instanceof int[]) {int[] arr = (int[])obj;StringBuilder sb = new StringBuilder();sb.append("[");for (int i : arr) {sb.append(i+",");}str = sb.substring(0,sb.lastIndexOf(","))+"]" ;}else if(obj instanceof long[]) {long[] arr = (long[])obj;StringBuilder sb = new StringBuilder();sb.append("[");for (long i : arr) {sb.append(i+",");}str = sb.substring(0,sb.lastIndexOf(","))+"]" ;}else if(obj instanceof char[]) {char[] arr = (char[])obj;StringBuilder sb = new StringBuilder();sb.append("[");for (char i : arr) {sb.append(i+",");}str = sb.substring(0,sb.lastIndexOf(","))+"]" ;}else if(obj instanceof short[]) {short[] arr = (short[])obj;StringBuilder sb = new StringBuilder();sb.append("[");for (short i : arr) {sb.append(i+",");}str = sb.substring(0,sb.lastIndexOf(","))+"]" ;}else if(obj instanceof double[]) {double[] arr = (double[])obj;StringBuilder sb = new StringBuilder();sb.append("[");for (double i : arr) {sb.append(i+",");}str = sb.substring(0,sb.lastIndexOf(","))+"]" ;}else if(obj instanceof float[]) {float[] arr = (float[])obj;StringBuilder sb = new StringBuilder();sb.append("[");for (float i : arr) {sb.append(i+",");}str = sb.substring(0,sb.lastIndexOf(","))+"]" ;}else if(obj instanceof Object[]) {Object[] arr = (Object[])obj;StringBuilder sb = new StringBuilder();sb.append("[");for (Object i : arr) {sb.append(i.toString()+",");}str = sb.substring(0,sb.lastIndexOf(","))+"]" ;}else {str=obj.toString();}System.out.println(str);;}}

最佳情况：T(n) = O(n) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)

2、选择排序（Selection Sort）

表现最稳定的排序算法之一，因为无论什么数据进去都是O(n2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

2.1 算法描述

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

初始状态：无序区为R[1..n]，有序区为空；第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；n-1趟结束，数组有序化了。

2.2 动图演示

2.3 代码实现

package cn.fuqiang.arithmetic;import parator;/*** 选择排序的两种实现方式* (在这里要注意，因为最后一个位置的数绝对是最后循环后最大的值，* 所以外层循环的循环次数最好是arr.length-1).* @author 王福强* @Title: SelectionSort.java * @Package cn.fuqiang.arithmetic* @Description * @date 6月8日下午5:30:59*/public class SelectionSort {public static void main(String[] args) {int[] arr = {4,1,5,3,8,10,28,2};sort(arr);so(arr);Integer[] arr2 = {4,1,5,3,8,10,28,2};sort(arr2,(a,b)-> pareTo(a));so(arr2);}/*** 选择排序第一种实现方式 (赋值) 升序（特点：从小到大）* 原理: 每次把最小的都放在前面，* 外层循环控制每次遍历的次数，内层循环替换每次找出来的最小值，放在 arr[i]的位置* 这样当内层比较和替换的时候，就保证每次最小的都在最前面* 例如：3 2 6 1* 第一次外层循环为 i 为 0 第一个就是最小的值放最小的值* 内层循换会把每次找出的最小值放在arr[0] 的位置 * 第二次外层循环为 i 为 1 * 内层循环会把每次找出最小的值放在 arr[1] 的位置* * 外循环第一次 i=0* 内部循环 * 第一次 2 3 6 1* 第二次 2 3 6 1* 第三次 1 3 6 2* * 外循环第二次 i=1* 内部循环 * 第一次 3 6 1* 第二次 1 6 3* * 外循环第三次 i=2* 内部循环 * 第一次 3 6* * * @author 王福强* @Description * @date 6月8日下午6:36:42* @param arr int类型数组*/public static void sort(int[] arr) {for(int i = 0;i<arr.length-1;i++) {int temp;for(int j = i+1 ; j <arr.length ; j++) {if(arr[i]>arr[j]) {temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}}}/*** 选择排序第二种实现(记录下标) 升序（特点：从小到大）* 每次循环记录最小的下标 min 最后跟 arr[i] 位置的下标交换位置* 这样当外层循环每次循环一次会先记下 arr[i] 的下标，* 然后让内层循环从 i+1 开始比较去比较 arr[min] 与 arr[j]* 如果 min下表对应的值比 j下标对应的值大，则记录 j的下标 min = j* 然后拿新的 min下标去跟后面比较，依此类推。* 当内层循环循环结束后记录的下标是剩余数中最小的呢个值的下标* 然后用一个零时变量将他们的值交换过来，就算本身是最小的，也是替换自己* 例如 1 3 6 2* * 第一次外层循环结束后* 1 3 6 2* 第二次外循开始时，会记录i的下标* 然后开始内层循环，会记录2的下标* 内层循环结束后，会把 3 与 2的位置调换* 2 6 3* 。。。。。* 。。。。* 3 6* * @author 王福强* @Description * @date 6月9日下午2:13:42* @param arr* @param comparator*/public static <T>void sort(T[] arr,Comparator<T> comparator) {for(int i = 0;i<arr.length-1;i++) {int min=i;T temp=null;for(int j = i+1 ; j <arr.length ; j++) {if(pare(arr[min], arr[j])<0) {min = j;}}temp = arr[i];arr[i] = arr[min];arr[min] = temp;}}/*** 传入任意数组或对象输出到控制台* @author 王福强* @Description 前提是传入的对象必须重写 toString()方法* @date 6月8日下午4:26:06* @param obj*/public static void so(Object obj) {String str = "";if(obj instanceof int[]) {int[] arr = (int[])obj;StringBuilder sb = new StringBuilder();sb.append("[");for (int i : arr) {sb.append(i+",");}str = sb.substring(0,sb.lastIndexOf(","))+"]" ;}else if(obj instanceof long[]) {long[] arr = (long[])obj;StringBuilder sb = new StringBuilder();sb.append("[");for (long i : arr) {sb.append(i+",");}str = sb.substring(0,sb.lastIndexOf(","))+"]" ;}else if(obj instanceof char[]) {char[] arr = (char[])obj;StringBuilder sb = new StringBuilder();sb.append("[");for (char i : arr) {sb.append(i+",");}str = sb.substring(0,sb.lastIndexOf(","))+"]" ;}else if(obj instanceof short[]) {short[] arr = (short[])obj;StringBuilder sb = new StringBuilder();sb.append("[");for (short i : arr) {sb.append(i+",");}str = sb.substring(0,sb.lastIndexOf(","))+"]" ;}else if(obj instanceof double[]) {double[] arr = (double[])obj;StringBuilder sb = new StringBuilder();sb.append("[");for (double i : arr) {sb.append(i+",");}str = sb.substring(0,sb.lastIndexOf(","))+"]" ;}else if(obj instanceof float[]) {float[] arr = (float[])obj;StringBuilder sb = new StringBuilder();sb.append("[");for (float i : arr) {sb.append(i+",");}str = sb.substring(0,sb.lastIndexOf(","))+"]" ;}else if(obj instanceof Object[]) {Object[] arr = (Object[])obj;StringBuilder sb = new StringBuilder();sb.append("[");for (Object i : arr) {sb.append(i.toString()+",");}str = sb.substring(0,sb.lastIndexOf(","))+"]" ;}else {str=obj.toString();}System.out.println(str);;}}

2.4算法分析

最佳情况：T(n) = O(n2) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)

3、插入排序（Insertion Sort）

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

3.1 算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

从第一个元素开始，该元素可以认为已经被排序；取出下一个元素，在已经排序的元素序列中从后向前扫描；如果该元素（已排序）大于新元素，将该元素移到下一位置；重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；将新元素插入到该位置后；重复步骤2~5。

3.2 动图演示

3.2 代码实现

package cn.fuqiang.arithmetic;import parator;/*** 插入排序 * @author 王福强* @Title: InsertionSort.java * @Package cn.fuqiang.arithmetic* @Description * @date 6月11日下午2:19:55*/public class InsertionSort {public static void main(String[] args) {int[] arr = {4,1,5,3,8,10,28,2};sort(arr);so(arr);Integer[] arr2 = {4,1,5,3,8,10,28,2};sort(arr2,(a,b)-> pareTo(a));so(arr2);}/*** 插入排序升序(特点:拿当前下标值与前面的值比较，将小的值排在对应的位置，把大的往后移)* 循环从 i=1 开始用temp记录当前位置的值arr[i]，* 然后设置内部循环控制下标，通过循环将下标每次减一。* 然后判断temp与arr[index]的大小，如果temp小于arr[index]则将arr[index-1]值移动到下一个位置，* 然后将下标往前挪一位也就是 index-1 (因为第一次比较时记录了 temp = arr[i] 所以不用担心会将值覆盖)* 如果不进入内循环则说明，下标已经移动到最前面了没有比该值更小的了，* 这时候就把记录的 temp 赋值给 index+1 的位置上(因为index已经减到前一个了)* 比较第一个位置和第二个位置的* 例如 3 1 6 2 * 外循环第一次 i=1* 外层循环直接从下标为一的开始 * 比较1 与3的大小，然后把3的位置移动到后面一位，* 应为内层循环index--后小于0了，所以不在循环，* 然后因为把3移动到后面一位的时候前面空了一个位置，所以就把1插入* 1 3 6 2 * 。。。。* 外循环第三次 i=3* 比较 2 与 6 然后把6往后移* 比较 2与3把三往后移* 然后比较2与1 把 2 插入到空缺位置* * @author 王福强* @Description * @date 6月11日下午4:22:41* @param arr*/public static void sort(int[] arr) {for(int i = 1 ; i < arr.length ; i ++) {int index = i-1;int temp = arr[i];while(index>=0 && arr[index]>temp) {arr[index+1] = arr[index--];}arr[index+1] = temp;}}/*** 对任意对象排序* @author 王福强* @Description * @date 6月13日上午10:52:31* @param arr* @param comparator*/public static <T>void sort(T[] arr,Comparator<T> comparator) {for(int i = 1;i<arr.length;i++) {T temp=arr[i];int index;for(index = i-1;index>=0 && pare(arr[index], temp)<0;index--) {arr[index+1]=arr[index];}arr[index+1] =temp;}}/*** 传入任意数组或对象输出到控制台* @author 王福强* @Description 前提是传入的对象必须重写 toString()方法* @date 6月8日下午4:26:06* @param obj*/public static void so(Object obj) {String str = obj.toString();if(obj instanceof int[]) {int[] arr = (int[])obj;StringBuilder sb = new StringBuilder();sb.append("[");for (int i : arr) {sb.append(i+",");}str = sb.substring(0,sb.lastIndexOf(","))+"]" ;}else if(obj instanceof long[]) {long[] arr = (long[])obj;StringBuilder sb = new StringBuilder();sb.append("[");for (long i : arr) {sb.append(i+",");}str = sb.substring(0,sb.lastIndexOf(","))+"]" ;}else if(obj instanceof char[]) {char[] arr = (char[])obj;StringBuilder sb = new StringBuilder();sb.append("[");for (char i : arr) {sb.append(i+",");}str = sb.substring(0,sb.lastIndexOf(","))+"]" ;}else if(obj instanceof short[]) {short[] arr = (short[])obj;StringBuilder sb = new StringBuilder();sb.append("[");for (short i : arr) {sb.append(i+",");}str = sb.substring(0,sb.lastIndexOf(","))+"]" ;}else if(obj instanceof double[]) {double[] arr = (double[])obj;StringBuilder sb = new StringBuilder();sb.append("[");for (double i : arr) {sb.append(i+",");}str = sb.substring(0,sb.lastIndexOf(","))+"]" ;}else if(obj instanceof float[]) {float[] arr = (float[])obj;StringBuilder sb = new StringBuilder();sb.append("[");for (float i : arr) {sb.append(i+",");}str = sb.substring(0,sb.lastIndexOf(","))+"]" ;}else if(obj instanceof Object[]) {Object[] arr = (Object[])obj;StringBuilder sb = new StringBuilder();sb.append("[");for (Object i : arr) {sb.append(i.toString()+",");}str = sb.substring(0,sb.lastIndexOf(","))+"]" ;}else {str=obj.toString();}System.out.println(str);;}}

3.4算法分析

最佳情况：T(n) = O(n) 最坏情况：T(n) = O(n2) 平均情况：T(n) = O(n2)

4、希尔排序（Shell Sort）

1959年Shell发明，第一个突破O(n^2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版》的合著者Robert Sedgewick提出的。

4.1 算法描述

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；按增量序列个数k，对序列进行k 趟排序；每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

4.2 过程演示

4.3 代码实现

package cn.fuqiang.arithmetic;import parator;/*** 希尔排序* (建议：研究希尔排序前先理解插入排序)* @author 王福强* @Title: ShellSort.java * @Package cn.fuqiang.arithmetic* @Description * @date 6月11日下午7:23:24*/public class ShellSort {public static void main(String[] args) {int[] arr = {4,1,5,3,8,10,28,2};sort(arr);so(arr);Integer[] arr2 = {4,1,5,3,8,10,28,2};sort(arr2,(a,b)-> pareTo(b));so(arr2);}/*** 希尔排序升序(特点：缩小增量排序，是插入排序的改进版) * increment是用来记录增量的*讲解：* while(increment > 1)* 最外层的 while循环是用来控制增量的。增量要从大到小* increment =increment/3+1;* 当每次循环后都吧增量除以一个数(改数不能是2和1 否则会死循环)加一* 保证最后除尽后不能小于一，应为最后增量缩小为一后需要两两之间进行比较(此处也就是缩小增量)* * for (int i = increment; i < arr.length; i++) {* 中间for循环，控制每次要取出的比较的元素，从增量开始，每次加一* int temp = arr[i];* 用一个零是变量接受要比较的值* arr[j+increment] = temp;* 因为在内层循环中已将前面的值移动到后面了，在最后一次循环结束后 j -= increment 已经少了一个增量* 所以j+increment 正好是移动后最后空出来的一个所以把temp替换给该值，完成交换* 就算没有进入内层循环，呢j=i-incement后再+incement就还是 i本身temp也就是arr[i]本身* * for (j = i-increment; j >= 0 && arr[j]> temp ; j-=increment) {* 最内层的for循环是用来控制temp 与每个j-increment个值比较，从 j=i-increment开始也就是中层循中 i减去一个增量后的下标(与插入排序相同，只不过是每次跟前increment个值比较)* j >= 0 && arr[j]> temp * 该判断是防止j减到负下标并且每次替换的实话只有temp小于arr[j]才可以进入* arr[j+increment] = arr[j];* 如果arr[j]> temp 呢么与将 arr[j]的值移动道后面 * * 例如 * 4,1,5,3,8,10,28,2 长度为 8* while循环第一次 * increment = 3* 中层for循环 i从 3开始 * temp = arr[3]*内层for循环从j=i-increment 也就是从前increment个值开始*就会拿出arr[3-3]>temp 比较*如果temp小则把 arr[3-3] 的值与的值赋给arr[0+3] 也就是 arr[j+increment] = arr[j]*因为arr[3]已经记录，所以当 j-=increment时 j=-3此时已经不满足 j >= 0 所以内层循环结束*内层循环结束后 arr的值就从4,1,5,3,8,10,28,2 变为了 4,1,5,4,8,10,28,2 *因为在内层循环中只是把 0下标的值赋给了3下标所以说 0位置的值还是4*此时中层循环中的 arr[j+increment] = temp; 就是把原来记录的 arr[3]----3 赋给0下标，*因为j已经被减了increment 变成了-3所以此时加上increment正好等于0下标*所以arr就变成了 3,1,5,4,8,10,28,2* * 中层for循环 i变为了4 *temp = arr[4]* 内层for循环从j=i-increment 也就是从前increment个值开始* 就会拿出arr[4-3]>temp 比较* 因为arr[1]小于temp所以而且j也已经=-1所以循环结束* 。。。。。。。。。以此类推* * * @author 王福强* @Description * @date 6月14日下午5:33:04* @param arr*/public static void sort(int[] arr) {int increment = arr.length;while(increment > 1) { //动态定义间隔序列increment =increment/3+1;for (int i = increment; i < arr.length; i++) {int temp = arr[i];int j ;for (j = i-increment; j >= 0 && arr[j]> temp ; j-=increment) {arr[j+increment] = arr[j];}arr[j+increment] = temp;}} }/*** 任意对象排序，将上面排序中内部的循环替换为了while循环* @author 王福强* @Description * @date 6月15日下午3:45:06* @param arr* @param comparator*/public static <T>void sort(T[] arr,Comparator<T> comparator){int increment = arr.length;while(increment > 1) { //动态定义间隔序列increment =increment/3+1;for (int i = increment; i < arr.length; i++) {T temp = arr[i];int j = i-increment;while ( j >= 0 && pare(arr[j], temp)>0 ) {arr[j+increment] = arr[j];j-=increment; }arr[j+increment] = temp;}} }/*** 传入任意数组或对象输出到控制台* @author 王福强* @Description 前提是传入的对象必须重写 toString()方法* @date 6月8日下午4:26:06* @param obj*/public static void so(Object obj) {String str = obj.toString();if(obj instanceof int[]) {int[] arr = (int[])obj;StringBuilder sb = new StringBuilder();sb.append("[");for (int i : arr) {sb.append(i+",");}str = sb.substring(0,sb.lastIndexOf(","))+"]" ;}else if(obj instanceof long[]) {long[] arr = (long[])obj;StringBuilder sb = new StringBuilder();sb.append("[");for (long i : arr) {sb.append(i+",");}str = sb.substring(0,sb.lastIndexOf(","))+"]" ;}else if(obj instanceof char[]) {char[] arr = (char[])obj;StringBuilder sb = new StringBuilder();sb.append("[");for (char i : arr) {sb.append(i+",");}str = sb.substring(0,sb.lastIndexOf(","))+"]" ;}else if(obj instanceof short[]) {short[] arr = (short[])obj;StringBuilder sb = new StringBuilder();sb.append("[");for (short i : arr) {sb.append(i+",");}str = sb.substring(0,sb.lastIndexOf(","))+"]" ;}else if(obj instanceof double[]) {double[] arr = (double[])obj;StringBuilder sb = new StringBuilder();sb.append("[");for (double i : arr) {sb.append(i+",");}str = sb.substring(0,sb.lastIndexOf(","))+"]" ;}else if(obj instanceof float[]) {float[] arr = (float[])obj;StringBuilder sb = new StringBuilder();sb.append("[");for (float i : arr) {sb.append(i+",");}str = sb.substring(0,sb.lastIndexOf(","))+"]" ;}else if(obj instanceof Object[]) {Object[] arr = (Object[])obj;StringBuilder sb = new StringBuilder();sb.append("[");for (Object i : arr) {sb.append(i.toString()+",");}str = sb.substring(0,sb.lastIndexOf(","))+"]" ;}else {str=obj.toString();}System.out.println(str);}}

4.4 算法分析

最佳情况：T(n) = O(nlog2 n) 最坏情况：T(n) = O(nlog2 n) 平均情况：T(n) =O(nlog n)

5、归并排序（Merge Sort）

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

5.1 算法描述

把长度为n的输入序列分成两个长度为n/2的子序列；对这两个子序列分别采用归并排序；将两个排序好的子序列合并成一个最终的排序序列。

5.2 动图演示

5.3 代码实现

5. 4 算法分析

最佳情况：T(n) = O(n) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)

6、快速排序（Quick Sort）

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

6.1 算法描述

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

从数列中挑出一个元素，称为 “基准”（pivot）；重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

5.2 动图演示

5.3 代码实现

5.4 算法分析

最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(nlogn)

7、堆排序（Heap Sort）

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

7.1 算法描述

将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

7.2 动图演示

7.3 代码实现

7.4 算法分析

最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)