logo
搜索
我的图书馆

发文章

发文工具

其他工具

留言交流
搜索
分享

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

 好汉勃士 2020-01-18

十大经典排序算法

部分内容引用自：https://www.cnblogs.com/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 代码实现

  1. package cn.fuqiang.arithmetic;
  3. import java.util.Comparator;
  4. /**
  5. * 冒泡排序
  6. * @author 王福强
  7. * @Title: BubbleSort.java
  8. * @Package cn.fuqiang.arithmetic
  9. * @Description 冒泡排序 实现
  10. * @date 2018年6月8日 下午4:18:37
  11. */
  12. public class BubbleSort<T> {
  13. public static void main(String[] args) {
  14. int[] arr = {4,1,5,3,8,10,28,2};
  15. sort(arr);
  16. so(arr);
  19. Integer[] arr2 = {4,1,5,3,8,10,28,2};
  20. sort(arr2,(a,b)-> b.compareTo(a));
  21. so(arr2);
  22. }
  23. /**
  24. * 冒泡排序 (特点：从后往前)
  25. * 原理：前后元素两两之间进行比较 把大的往后扔
  26. * 升序 (从后往前，从大到小)
  27. * 外层循环是控制内层循环的次数，也就是说外层循环每循环一遍，让内层循环每次循环的次数减一次
  28. * 这样就保证内层循环每次循环结束后最后面一个都是最大
  29. * 例如 ： 3 6 4 1
  30. * 外循环第一次 结束后，内循环 会把6放到最后面 3 4 1 6
  31. * 外循环第二次开始时，内循环的循环次数会减一 也就是说 6 不会在参与比较
  32. * 外循环第二次结束时， 内循环 会把4放到最后面 3 1 4
  33. * 以此类推。。。。
  34. * 外循环第三次结束时 内循环 1 3 4
  35. * .。。。。 1 3
  36. * .。。。。 1
  37. * 最终结果 1 3 4 6
  38. * @param t
  39. */
  40. public static void sort(int[] t) {
  41. for(int i=0;i<t.length;i++) {
  42. int temp;
  43. for(int j = 0;j<t.length-1-i;j++) {
  44. if(t[j]>t[j+1]) {
  45. temp = t[j];
  46. t[j]=t[j+1];
  47. t[j+1]=temp;
  48. }
  49. }
  50. }
  52. }
  54. /**
  55. * 冒泡排序 对象类型排序
  56. * 对象必须实现Comparator接口
  57. * @param t 要遍历的数组
  58. * @param comparator 定制的遍历规则
  59. */
  60. public static <T>void sort(T[] t,Comparator<? super T> comparator) {
  61. for(int i = 0;i<t.length-1;i++) {
  62. T temp;
  63. for(int j = 1;j<t.length-i;j++) {
  64. if(comparator.compare(t[j-1], t[j])<0) {
  65. temp = t[j-1];
  66. t[j-1]=t[j];
  67. t[j]=temp;
  68. }
  69. }
  70. }
  71. }
  73. /**
  74. * 传入任意数组或对象 输出到控制台
  75. * @author 王福强
  76. * @Description 前提是传入的对象必须重写 toString()方法
  77. * @date 2018年6月8日 下午4:26:06
  78. * @param obj
  79. */
  80. public static void so(Object obj) {
  81. String str = '';
  82. if(obj instanceof int[]) {
  83. int[] arr = (int[])obj;
  84. StringBuilder sb = new StringBuilder();
  85. sb.append('[');
  86. for (int i : arr) {
  87. sb.append(i+',');
  88. }
  89. str = sb.substring(0,sb.lastIndexOf(','))+']' ;
  91. }else if(obj instanceof long[]) {
  92. long[] arr = (long[])obj;
  93. StringBuilder sb = new StringBuilder();
  94. sb.append('[');
  95. for (long i : arr) {
  96. sb.append(i+',');
  97. }
  98. str = sb.substring(0,sb.lastIndexOf(','))+']' ;
  99. }else if(obj instanceof char[]) {
  100. char[] arr = (char[])obj;
  101. StringBuilder sb = new StringBuilder();
  102. sb.append('[');
  103. for (char i : arr) {
  104. sb.append(i+',');
  105. }
  106. str = sb.substring(0,sb.lastIndexOf(','))+']' ;
  107. }else if(obj instanceof short[]) {
  108. short[] arr = (short[])obj;
  109. StringBuilder sb = new StringBuilder();
  110. sb.append('[');
  111. for (short i : arr) {
  112. sb.append(i+',');
  113. }
  114. str = sb.substring(0,sb.lastIndexOf(','))+']' ;
  115. }else if(obj instanceof double[]) {
  116. double[] arr = (double[])obj;
  117. StringBuilder sb = new StringBuilder();
  118. sb.append('[');
  119. for (double i : arr) {
  120. sb.append(i+',');
  121. }
  122. str = sb.substring(0,sb.lastIndexOf(','))+']' ;
  123. }else if(obj instanceof float[]) {
  124. float[] arr = (float[])obj;
  125. StringBuilder sb = new StringBuilder();
  126. sb.append('[');
  127. for (float i : arr) {
  128. sb.append(i+',');
  129. }
  130. str = sb.substring(0,sb.lastIndexOf(','))+']' ;
  131. }else if(obj instanceof Object[]) {
  132. Object[] arr = (Object[])obj;
  133. StringBuilder sb = new StringBuilder();
  134. sb.append('[');
  135. for (Object i : arr) {
  136. sb.append(i.toString()+',');
  137. }
  138. str = sb.substring(0,sb.lastIndexOf(','))+']' ;
  139. }else {
  140. str=obj.toString();
  141. }
  142. System.out.println(str);;
  143. }
  145. }

最佳情况：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 代码实现

  1. package cn.fuqiang.arithmetic;
  3. import java.util.Comparator;
  5. /**
  6. * 选择排序  的两种实现方式
  7. * (在这里要注意，因为最后一个位置的数绝对是最后循环后最大的值，
  8. * 所以外层循环的循环次数 最好是arr.length-1).
  9. * @author 王福强
  10. * @Title: SelectionSort.java
  11. * @Package cn.fuqiang.arithmetic
  12. * @Description
  13. * @date 2018年6月8日 下午5:30:59
  14. */
  15. public class SelectionSort {
  16. 	public static void main(String[] args) {
  17. 		int[] arr = {4,1,5,3,8,10,28,2};
  18. 		sort(arr);
  19. 		so(arr);
  22. 		Integer[] arr2 = {4,1,5,3,8,10,28,2};
  23. 		sort(arr2,(a,b)-> b.compareTo(a));
  24. 		so(arr2);
  25. 	}
  28. 	/**
  29. 	* 选择排序   第一种实现方式  (赋值)    升序   （特点 ：从小到大）
  30. 	* 原理: 每次把最小的都放在前面，
  31. 	* 外层循环控制每次遍历的次数，内层循环替换每次找出来的最小值，放在  arr[i]的位置
  32. 	* 这样当内层比较和替换的时候，就保证每次最小的都在最前面
  33. 	* 例如：3 2 6 1
  34. 	* 第一次外层循环为  i 为  0    第一个就是最小的值放最小的值
  35. 	* 内层循换会把每次找出的最小值放在arr[0] 的位置
  36. 	* 第二次外层循环为 i 为 1
  37. 	* 内层循环会把每次找出最小的值放在 arr[1] 的位置
  38. 	*
  39. 	* 外循环    第一次   i=0
  40. 	* 内部循环
  41. 	* 第一次  2 3 6 1
  42. 	* 第二次  2 3 6 1
  43. 	* 第三次  1 3  6 2
  44. 	*
  45. 	* 外循环    第二次   i=1
  46.  	* 内部循环
  47.  	* 第一次  3 6 1
  48. 	* 第二次  1 6 3
  49. 	*
  50. 	* 外循环    第三次   i=2
  51.  	* 内部循环
  52.  	* 第一次  3  6
  53. 	*
  54. 	*
  55. 	* @author 王福强
  56. 	* @Description
  57. 	* @date 2018年6月8日 下午6:36:42
  58. 	* @param arr int类型数组
  59. 	*/
  60. 	public static void sort(int[] arr) {
  61. 		for(int i = 0;i<arr.length-1;i++) {
  62. 			int temp;
  63. 			for(int j = i+1 ; j <arr.length ; j++) {
  64. 				if(arr[i]>arr[j]) {
  65. 					temp = arr[i];
  66. 					arr[i] = arr[j];
  67. 					arr[j] = temp;
  68. 				}
  69. 			}
  70. 		}
  71. 	}
  75. 	/**
  76. 	* 选择排序  第二种实现(记录下标)  升序   （特点 ：从小到大）
  77. 	* 每次循环记录最小的下标 min 最后跟 arr[i] 位置的下标交换位置
  78. 	* 这样当外层循环每次循环一次 会先记下  arr[i] 的下标，
  79. 	* 然后让内层循环从 i+1 开始比较去比较  arr[min] 与 arr[j]
  80. 	* 如果 min下表对应的值 比  j下标对应的值大， 则记录 j的下标    min  = j
  81. 	* 然后拿新的 min下标去跟后面比较，依此类推。
  82. 	* 当内层循环循环结束后记录的下标是剩余数中最小的呢个值的下标
  83. 	* 然后用一个零时变量将他们的值交换过来，就算本身是最小的，也是替换自己
  84. 	* 例如  1 3 6 2
  85. 	*
  86. 	* 第一次外层循环结束后
  87. 	*  1 3 6 2
  88. 	* 第二次外循开始时，会记录i的下标
  89. 	* 然后开始内层循环，会记录2的下标
  90. 	* 内层循环结束后，会把  3 与 2的位置调换
  91. 	* 2 6 3
  92. 	* 。。。。。
  93. 	* 。。。。
  94. 	* 3 6
  95. 	*
  96. 	* @author 王福强
  97. 	* @Description
  98. 	* @date 2018年6月9日 下午2:13:42
  99. 	* @param arr
  100. 	* @param comparator
  101. 	*/
  102. 	public static <T>void sort(T[] arr,Comparator<T> comparator) {
  103. 		for(int i = 0;i<arr.length-1;i++) {
  104. 			int min=i;
  105. 			T temp=null;
  106. 			for(int j = i+1 ; j <arr.length ; j++) {
  107. 				if(comparator.compare(arr[min], arr[j])<0) {
  108. 					min = j;
  109. 				}
  110. 			}
  111. 			temp = arr[i];
  112. 			arr[i] = arr[min];
  113. 			arr[min] = temp;
  114. 		}
  115. 	}
  117. 	/**
  118. 	* 传入任意数组或对象   输出到控制台
  119. 	* @author 王福强
  120. 	* @Description  前提是传入的对象必须重写 toString()方法
  121. 	* @date 2018年6月8日 下午4:26:06
  122. 	* @param obj
  123. 	*/
  124. 	public static void so(Object obj) {
  125. 		String str = '';
  126. 		if(obj instanceof int[]) {
  127. 			int[] arr = (int[])obj;
  128. 			StringBuilder sb = new StringBuilder();
  129. 			sb.append('[');
  130. 			for (int i : arr) {
  131. 				sb.append(i+',');
  132. 			}
  133. 			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
  135. 		}else if(obj instanceof long[]) {
  136. 			long[] arr = (long[])obj;
  137. 			StringBuilder sb = new StringBuilder();
  138. 			sb.append('[');
  139. 			for (long i : arr) {
  140. 				sb.append(i+',');
  141. 			}
  142. 			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
  143. 		}else if(obj instanceof char[]) {
  144. 			char[] arr = (char[])obj;
  145. 			StringBuilder sb = new StringBuilder();
  146. 			sb.append('[');
  147. 			for (char i : arr) {
  148. 				sb.append(i+',');
  149. 			}
  150. 			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
  151. 		}else if(obj instanceof short[]) {
  152. 			short[] arr = (short[])obj;
  153. 			StringBuilder sb = new StringBuilder();
  154. 			sb.append('[');
  155. 			for (short i : arr) {
  156. 				sb.append(i+',');
  157. 			}
  158. 			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
  159. 		}else if(obj instanceof double[]) {
  160. 			double[] arr = (double[])obj;
  161. 			StringBuilder sb = new StringBuilder();
  162. 			sb.append('[');
  163. 			for (double i : arr) {
  164. 				sb.append(i+',');
  165. 			}
  166. 			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
  167. 		}else if(obj instanceof float[]) {
  168. 			float[] arr = (float[])obj;
  169. 			StringBuilder sb = new StringBuilder();
  170. 			sb.append('[');
  171. 			for (float i : arr) {
  172. 				sb.append(i+',');
  173. 			}
  174. 			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
  175. 		}else if(obj instanceof Object[]) {
  176. 			Object[] arr = (Object[])obj;
  177. 			StringBuilder sb = new StringBuilder();
  178. 			sb.append('[');
  179. 			for (Object i : arr) {
  180. 				sb.append(i.toString()+',');
  181. 			}
  182. 			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
  183. 		}else {
  184. 			str=obj.toString();
  185. 		}
  186. 		System.out.println(str);;
  187. 	}
  189. }

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 代码实现

  1. package cn.fuqiang.arithmetic;
  3. import java.util.Comparator;
  5. /**
  6. * 插入排序
  7. * @author 王福强
  8. * @Title: InsertionSort.java
  9. * @Package cn.fuqiang.arithmetic
  10. * @Description
  11. * @date 2018年6月11日 下午2:19:55
  12. */
  13. public class InsertionSort {
  14. public static void main(String[] args) {
  15. int[] arr = {4,1,5,3,8,10,28,2};
  16. sort(arr);
  17. so(arr);
  20. Integer[] arr2 = {4,1,5,3,8,10,28,2};
  21. sort(arr2,(a,b)-> b.compareTo(a));
  22. so(arr2);
  23. }
  24. /**
  25. * 插入排序 升序(特点:拿当前下标值与前面的值比较，将小的值排在对应的位置，把大的往后移)
  26. * 循环从 i=1 开始 用temp记录当前位置的值arr[i]，
  27. * 然后设置内部循环控制下标，通过循环将下标每次减一。
  28. * 然后判断temp与arr[index]的大小， 如果temp小于arr[index]则将arr[index-1]值移动到下一个位置，
  29. * 然后将下标往前挪一位 也就是 index-1 (因为第一次比较时记录了 temp = arr[i] 所以不用担心会将值覆盖)
  30. * 如果不进入内循环则说明，下标已经移动到最前面了没有比该值更小的了，
  31. * 这时候就把记录的 temp 赋值给 index+1 的位置上(因为index已经减到前一个了)
  32. * 比较第一个位置 和第二个位置的
  33. * 例如 3 1 6 2
  34. * 外循环第一次 i=1
  35. * 外层循环直接从 下标为一的开始
  36. * 比较1 与3的大小，然后把3的位置移动到后面一位，
  37. * 应为内层循环index--后小于0了，所以不在循环，
  38. * 然后因为把3移动到后面一位的时候前面空了一个位置，所以就把1插入
  39. * 1 3 6 2
  40. * 。。。。
  41. * 外循环第三次 i=3
  42. * 比较 2 与 6 然后把6往后移
  43. * 比较 2与3把三往后移
  44. * 然后比较2与1 把 2 插入到空缺位置
  45. *
  46. * @author 王福强
  47. * @Description
  48. * @date 2018年6月11日 下午4:22:41
  49. * @param arr
  50. */
  51. public static void sort(int[] arr) {
  52. for(int i = 1 ; i < arr.length ; i ++) {
  53. int index = i-1;
  54. int temp = arr[i];
  55. while(index>=0 && arr[index]>temp) {
  56. arr[index+1] = arr[index--];
  57. }
  58. arr[index+1] = temp;
  59. }
  60. }
  62. /**
  63. * 对任意对象排序
  64. * @author 王福强
  65. * @Description
  66. * @date 2018年6月13日 上午10:52:31
  67. * @param arr
  68. * @param comparator
  69. */
  70. public static <T>void sort(T[] arr,Comparator<T> comparator) {
  71. for(int i = 1;i<arr.length;i++) {
  72. T temp=arr[i];
  73. int index;
  74. for(index = i-1;index>=0 && comparator.compare(arr[index], temp)<0;index--) {
  75. arr[index+1]=arr[index];
  76. }
  77. arr[index+1] =temp;
  78. }
  79. }
  82. /**
  83. * 传入任意数组或对象 输出到控制台
  84. * @author 王福强
  85. * @Description 前提是传入的对象必须重写 toString()方法
  86. * @date 2018年6月8日 下午4:26:06
  87. * @param obj
  88. */
  89. public static void so(Object obj) {
  90. String str = obj.toString();
  91. if(obj instanceof int[]) {
  92. int[] arr = (int[])obj;
  93. StringBuilder sb = new StringBuilder();
  94. sb.append('[');
  95. for (int i : arr) {
  96. sb.append(i+',');
  97. }
  98. str = sb.substring(0,sb.lastIndexOf(','))+']' ;
  100. }else if(obj instanceof long[]) {
  101. long[] arr = (long[])obj;
  102. StringBuilder sb = new StringBuilder();
  103. sb.append('[');
  104. for (long i : arr) {
  105. sb.append(i+',');
  106. }
  107. str = sb.substring(0,sb.lastIndexOf(','))+']' ;
  108. }else if(obj instanceof char[]) {
  109. char[] arr = (char[])obj;
  110. StringBuilder sb = new StringBuilder();
  111. sb.append('[');
  112. for (char i : arr) {
  113. sb.append(i+',');
  114. }
  115. str = sb.substring(0,sb.lastIndexOf(','))+']' ;
  116. }else if(obj instanceof short[]) {
  117. short[] arr = (short[])obj;
  118. StringBuilder sb = new StringBuilder();
  119. sb.append('[');
  120. for (short i : arr) {
  121. sb.append(i+',');
  122. }
  123. str = sb.substring(0,sb.lastIndexOf(','))+']' ;
  124. }else if(obj instanceof double[]) {
  125. double[] arr = (double[])obj;
  126. StringBuilder sb = new StringBuilder();
  127. sb.append('[');
  128. for (double i : arr) {
  129. sb.append(i+',');
  130. }
  131. str = sb.substring(0,sb.lastIndexOf(','))+']' ;
  132. }else if(obj instanceof float[]) {
  133. float[] arr = (float[])obj;
  134. StringBuilder sb = new StringBuilder();
  135. sb.append('[');
  136. for (float i : arr) {
  137. sb.append(i+',');
  138. }
  139. str = sb.substring(0,sb.lastIndexOf(','))+']' ;
  140. }else if(obj instanceof Object[]) {
  141. Object[] arr = (Object[])obj;
  142. StringBuilder sb = new StringBuilder();
  143. sb.append('[');
  144. for (Object i : arr) {
  145. sb.append(i.toString()+',');
  146. }
  147. str = sb.substring(0,sb.lastIndexOf(','))+']' ;
  148. }else {
  149. str=obj.toString();
  150. }
  151. System.out.println(str);;
  152. }
  154. }

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 代码实现

  1. package cn.fuqiang.arithmetic;
  3. import java.util.Comparator;
  5. /**
  6. * 希尔排序
  7. * (建议：研究希尔排序前先理解插入排序)
  8. * @author 王福强
  9. * @Title: ShellSort.java
  10. * @Package cn.fuqiang.arithmetic
  11. * @Description
  12. * @date 2018年6月11日 下午7:23:24
  13. */
  14. public class ShellSort {
  15. 	public static void main(String[] args) {
  16. 		int[] arr = {4,1,5,3,8,10,28,2};
  17. 	sort(arr);
  18. 		so(arr);
  19. 		Integer[] arr2 = {4,1,5,3,8,10,28,2};
  20. 		sort(arr2,(a,b)-> a.compareTo(b));
  21. 		so(arr2);
  23. 	}
  24. 	/**
  25. 	* 希尔排序      升序(特点：缩小增量排序  ，是插入排序的改进版)
  26. 	* increment是用来记录增量的
  27. 	*讲解：
  28. 	* while(increment > 1)
  29. 	* 最外层的  while循环是用来控制增量的。增量要从大到小
  30. 	* increment =increment/3+1;
  31. 	* 当每次循环后都吧增量除以一个数(改数不能是2和1 否则会死循环)加一
  32. 	* 保证最后除尽后不能小于一，应为最后增量缩小为一后需要两两之间进行比较(此处也就是缩小增量)
  33. 	*
  34. 	* for (int i = increment; i < arr.length; i++) {
  35. 	* 中间for循环，控制每次要取出的比较的元素，从增量开始，每次加一
  36. 	* int temp = arr[i];
  37. 	* 用一个零是变量接受要比较的值
  38. 	* arr[j+increment] = temp;
  39. 	* 因为在内层循环中已将前面的值移动到后面了，在最后一次 循环结束后 j -= increment 已经少了一个增量
  40. 	* 所以j+increment 正好是移动后最后空出来的一个 所以把temp替换给该值，完成交换
  41. 	* 就算没有进入内层循环，呢j=i-incement后再+incement就还是 i本身temp也就是arr[i]本身
  42. 	*
  43. 	* for (j = i-increment; j >= 0 && arr[j]> temp ; j-=increment) {
  44. 	* 最内层的for循环是用来控制temp 与每个j-increment个值比较，从 j=i-increment开始 也就是中层循中  i减去一个增量后的下标(与插入排序相同，只不过是每次跟前increment个值比较)
  45. 	* j >= 0 && arr[j]> temp
  46. 	* 该判断是防止j减到负下标并且每次替换的实话 只有temp小于arr[j]才可以进入
  47. 	* arr[j+increment] = arr[j];
  48. 	* 如果arr[j]> temp  呢么与将 arr[j]的值移动道后面
  49. 	*
  50. 	* 例如
  51. 	* 4,1,5,3,8,10,28,2   长度为 8
  52. 	* while循环第一次
  53. 	*  	 increment = 3
  54. 	*   中层for循环 i从 3开始
  55. 	*        temp = arr[3]
  56. 	* 		    内层for循环从j=i-increment  也就是从前increment个值开始
  57. 	* 		    就会拿出arr[3-3]>temp 比较
  58. 	* 		    如果temp小则 把 arr[3-3] 的值与 的值赋给arr[0+3]  也就是 arr[j+increment] = arr[j]
  59. 	* 		    因为arr[3]已经记录，所以当 j-=increment时 j=-3此时已经不满足 j >= 0 所以内层循环结束
  60. 	* 		    内层循环结束后  arr的值就从4,1,5,3,8,10,28,2  变为了    4,1,5,4,8,10,28,2
  61. 	* 		    因为在内层循环中只是把   0下标的值赋给了3下标 所以说 0位置的值还是4
  62. 	*     此时中层循环中的 arr[j+increment] = temp; 就是把原来记录的 arr[3]----3  赋给0下标，
  63. 	*     因为j已经被减了increment 变成了-3所以此时加上increment正好等于0下标
  64. 	*     所以arr就变成了  3,1,5,4,8,10,28,2
  65. 	*
  66. 	*   中层for循环 i变为了4
  67. 	*      temp = arr[4]
  68. 	* 		内层for循环从j=i-increment  也就是从前increment个值开始
  69. 	* 		就会拿出arr[4-3]>temp 比较
  70. 	* 		因为arr[1]小于temp所以 而且j也已经=-1所以循环结束
  71. 	* 	。。。。。。。。。 以此类推
  72. 	*	
  73. 	*
  74. 	* @author 王福强
  75. 	* @Description
  76. 	* @date 2018年6月14日 下午5:33:04
  77. 	* @param arr
  78. 	*/
  79. 	public static void sort(int[] arr) {
  80. 		int  increment = arr.length;
  81. 	while(increment > 1) {    //动态定义间隔序列
  82. 	    	increment =increment/3+1;
  83.  	    	for (int i = increment; i < arr.length; i++) {
  84.  	int temp = arr[i];
  85.  	int j ;
  86. 	for (j = i-increment; j >= 0 && arr[j]> temp ; j-=increment) {
  87. 	            	arr[j+increment] = arr[j];
  88. 	}
  89. 	arr[j+increment] = temp;
  90.  	}
  91. 	}
  92. 	}
  94. 	/**
  95. 	* 任意对象排序，将上面排序中 内部的循环替换为了while循环
  96. 	* @author 王福强
  97. 	* @Description
  98. 	* @date 2018年6月15日 下午3:45:06
  99. 	* @param arr
  100. 	* @param comparator
  101. 	*/
  102. 	public static <T>void sort(T[] arr,Comparator<T> comparator){
  103. 		int  increment = arr.length;
  104. 	while(increment > 1) {    //动态定义间隔序列
  105. 	    	increment =increment/3+1;
  106.  	    	for (int i = increment; i < arr.length; i++) {
  107.  	T temp = arr[i];
  108.  	int j = i-increment;
  109. 	while ( j >= 0 && comparator.compare(arr[j], temp)>0  ) {
  110. 	            	arr[j+increment] = arr[j];
  111. 	            	j-=increment;
  112. 	}
  113. 	arr[j+increment] = temp;
  114.  	}
  115. 	}
  116. 	}
  117. 	/**
  118. 	* 传入任意数组或对象   输出到控制台
  119. 	* @author 王福强
  120. 	* @Description  前提是传入的对象必须重写 toString()方法
  121. 	* @date 2018年6月8日 下午4:26:06
  122. 	* @param obj
  123. 	*/
  124. 	public static void so(Object obj) {
  125. 		String str = obj.toString();
  126. 		if(obj instanceof int[]) {
  127. 			int[] arr = (int[])obj;
  128. 			StringBuilder sb = new StringBuilder();
  129. 			sb.append('[');
  130. 			for (int i : arr) {
  131. 				sb.append(i+',');
  132. 			}
  133. 			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
  135. 		}else if(obj instanceof long[]) {
  136. 			long[] arr = (long[])obj;
  137. 			StringBuilder sb = new StringBuilder();
  138. 			sb.append('[');
  139. 			for (long i : arr) {
  140. 				sb.append(i+',');
  141. 			}
  142. 			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
  143. 		}else if(obj instanceof char[]) {
  144. 			char[] arr = (char[])obj;
  145. 			StringBuilder sb = new StringBuilder();
  146. 			sb.append('[');
  147. 			for (char i : arr) {
  148. 				sb.append(i+',');
  149. 			}
  150. 			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
  151. 		}else if(obj instanceof short[]) {
  152. 			short[] arr = (short[])obj;
  153. 			StringBuilder sb = new StringBuilder();
  154. 			sb.append('[');
  155. 			for (short i : arr) {
  156. 				sb.append(i+',');
  157. 			}
  158. 			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
  159. 		}else if(obj instanceof double[]) {
  160. 			double[] arr = (double[])obj;
  161. 			StringBuilder sb = new StringBuilder();
  162. 			sb.append('[');
  163. 			for (double i : arr) {
  164. 				sb.append(i+',');
  165. 			}
  166. 			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
  167. 		}else if(obj instanceof float[]) {
  168. 			float[] arr = (float[])obj;
  169. 			StringBuilder sb = new StringBuilder();
  170. 			sb.append('[');
  171. 			for (float i : arr) {
  172. 				sb.append(i+',');
  173. 			}
  174. 			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
  175. 		}else if(obj instanceof Object[]) {
  176. 			Object[] arr = (Object[])obj;
  177. 			StringBuilder sb = new StringBuilder();
  178. 			sb.append('[');
  179. 			for (Object i : arr) {
  180. 				sb.append(i.toString()+',');
  181. 			}
  182. 			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
  183. 		}else {
  184. 			str=obj.toString();
  185. 		}
  186. 		System.out.println(str);
  187. 	}
  189. }

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 代码实现

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

function mergeSort(arr) { //采用自上而下的递归方法

    var len = arr.length;

    if(len < 2) {

        return arr;

    }

    var middle = Math.floor(len / 2),

        left = arr.slice(0, middle),

        right = arr.slice(middle);

    return merge(mergeSort(left), mergeSort(right));

}

function merge(left, right)

{

    var result = [];

    while (left.length>0 && right.length>0) {

        if (left[0] <= right[0]) {

            result.push(left.shift());

        }else {

            result.push(right.shift());

        }

    }

    while (left.length)

        result.push(left.shift());

    while (right.length)

        result.push(right.shift());

    return result;

}

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 代码实现

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

function quickSort(arr, left, right) {

    var len = arr.length,

        partitionIndex,

        left =typeof left !='number' ? 0 : left,

        right =typeof right !='number' ? len - 1 : right;

    if (left < right) {

        partitionIndex = partition(arr, left, right);

        quickSort(arr, left, partitionIndex-1);

        quickSort(arr, partitionIndex+1, right);

    }

    return arr;

}

function partition(arr, left ,right) {    //分区操作

    var pivot = left,                     //设定基准值（pivot）

        index = pivot + 1;

    for (var i = index; i <= right; i++) {

        if (arr[i] < arr[pivot]) {

            swap(arr, i, index);

            index++;

        }       

    }

    swap(arr, pivot, index - 1);

    return index-1;

}

function swap(arr, i, j) {

    var temp = arr[i];

    arr[i] = arr[j];

    arr[j] = temp;

}

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 代码实现

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

var len;   //因为声明的多个函数都需要数据长度，所以把len设置成为全局变量

function buildMaxHeap(arr) {  //建立大顶堆

    len = arr.length;

    for (var i = Math.floor(len/2); i >= 0; i--) {

        heapify(arr, i);

    }

}

function heapify(arr, i) {    //堆调整

    var left = 2 * i + 1,

        right = 2 * i + 2,

        largest = i;

    if (left < len && arr[left] > arr[largest]) {

        largest = left;

    }

    if (right < len && arr[right] > arr[largest]) {

        largest = right;

    }

    if (largest != i) {

        swap(arr, i, largest);

        heapify(arr, largest);

    }

}

function swap(arr, i, j) {

    var temp = arr[i];

    arr[i] = arr[j];

    arr[j] = temp;

}

function heapSort(arr) {

    buildMaxHeap(arr);

    for (var i = arr.length-1; i > 0; i--) {

        swap(arr, 0, i);

        len--;

        heapify(arr, 0);

    }

    return arr;

}

7.4 算法分析

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

8、计数排序（Counting Sort）

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。

8.1 算法描述

  • 找出待排序的数组中最大和最小的元素；

  • 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；

  • 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；

  • 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

8.2 动图演示

8.3 代码实现

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

function countingSort(arr, maxValue) {

    var bucket =new Array(maxValue+1),

        sortedIndex = 0;

        arrLen = arr.length,

        bucketLen = maxValue + 1;

    for (var i = 0; i < arrLen; i++) {

        if (!bucket[arr[i]]) {

            bucket[arr[i]] = 0;

        }

        bucket[arr[i]]++;

    }

    for (var j = 0; j < bucketLen; j++) {

        while(bucket[j] > 0) {

            arr[sortedIndex++] = j;

            bucket[j]--;

        }

    }

    return arr;

}

8.4 算法分析

当输入的元素是n 个0到k之间的整数时，它的运行时间是 O(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。

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

9、桶排序（Bucket Sort）

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。

桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排

9.1 算法描述

  • 设置一个定量的数组当作空桶；

  • 遍历输入数据，并且把数据一个一个放到对应的桶里去；

  • 对每个不是空的桶进行排序；

  • 从不是空的桶里把排好序的数据拼接起来。 

9.2 图片演示

9.3 代码实现

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

function bucketSort(arr, bucketSize) {

    if (arr.length === 0) {

      return arr;

    }

    var i;

    var minValue = arr[0];

    var maxValue = arr[0];

    for (i = 1; i < arr.length; i++) {

      if (arr[i] < minValue) {

          minValue = arr[i];               //输入数据的最小值

      }else if (arr[i] > maxValue) {

          maxValue = arr[i];               //输入数据的最大值

      }

    }

    //桶的初始化

    var DEFAULT_BUCKET_SIZE = 5;           //设置桶的默认数量为5

    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;

    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;  

    var buckets =new Array(bucketCount);

    for (i = 0; i < buckets.length; i++) {

        buckets[i] = [];

    }

    //利用映射函数将数据分配到各个桶中

    for (i = 0; i < arr.length; i++) {

        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);

    }

    arr.length = 0;

    for (i = 0; i < buckets.length; i++) {

        insertionSort(buckets[i]);                     //对每个桶进行排序，这里使用了插入排序

        for (var j = 0; j < buckets[i].length; j++) {

            arr.push(buckets[i][j]);                     

        }

    }

    return arr;

}

9.4 算法分析

桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。 

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

10、基数排序（Radix Sort）

基数排序也是非比较的排序算法，对每一位进行排序，从最低位开始排序，复杂度为O(kn),为数组长度，k为数组中的数的最大的位数；

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。

10.1 算法描述

  • 取得数组中的最大数，并取得位数；

  • arr为原始数组，从最低位开始取每个位组成radix数组；

  • 对radix进行计数排序（利用计数排序适用于小范围数的特点）；

10.2 动图演示

10.3 代码实现

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

//LSD Radix Sort

var counter = [];

function radixSort(arr, maxDigit) {

    var mod = 10;

    var dev = 1;

    for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {

        for(var j = 0; j < arr.length; j++) {

            var bucket = parseInt((arr[j] % mod) / dev);

            if(counter[bucket]==null) {

                counter[bucket] = [];

            }

            counter[bucket].push(arr[j]);

        }

        var pos = 0;

        for(var j = 0; j < counter.length; j++) {

            var value =null;

            if(counter[j]!=null) {

                while ((value = counter[j].shift()) !=null) {

                      arr[pos++] = value;

                }

          }

        }

    }

    return arr;

}

10.4 算法分析

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

基数排序有两种方法：

MSD 从高位开始进行排序 LSD 从低位开始进行排序 

基数排序 vs 计数排序 vs 桶排序

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

  • 基数排序：根据键值的每位数字来分配桶

  • 计数排序：每个桶只存储单一键值

  • 桶排序：每个桶存储一定范围的数值

参考资料：

http://blog.csdn.net/fengyinchao/article/details/52667625

    本站是提供个人知识管理的网络存储空间，所有内容均由用户发布，不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息，谨防诈骗。如发现有害或侵权内容，请点击一键举报。
    转藏 分享 献花（0）

    来自： 好汉勃士 > 《操作系统综述》

    举报/认领

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多