这里有新鲜出炉的 Java 并发编程示例,程序狗速度看过来!
java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的 Java 程序设计语言和 Java 平台(即 JavaEE(j2ee), JavaME(j2me), JavaSE(j2se))的总称。
这篇文章主要为大家详细介绍了 Java 经典排序算法之插入排序,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
一、算法原理
插入排序法:所谓插入排序法乃是将一个数目插入该占据的位置。
假设我们输入的是 "53,27,36,15,69, 42" 我们从第二个数字开始,这个数字是 27,我们的任务只要看看 27 有没有正确的位置,我们的做法是和这个数字左边的数字来比,因此我们比较 27 和 53,27 比 53 小,所以我们就交换 27 和 53,原来的排列就变成了 "27, 53, 36, 15, 69, 42"
接下来,我们看第 3 个数字有没有在正确的位置。这个数字是 36,它的左边数字是 53,36 比 53 小,所以我们将 36 和 53 交换,排列变成了 "27,36, 53, 15, 69, 42" 我们必须继续看 36 有没有在正确的位置,36 的左边是 27,27 比 36 小,36 就维持不动了, 这时候排序还是 "27, 36, 53, 15, 69, 42"。
再来看第四个数字,这个数字是 15,我们将 15 和它左边的数字相比,都比 15 大,所以就将 15 一路往左移动,这时候排序变成了 "15, 27, 36, 53, 69, 42"。
再来看第五个数字,这个数字是 69,我们将 69 和它左边的数字相比,都比 69 小,所以就 69 维持不动了,这时候排序变成了 "15, 27, 36, 53, 69, 42"
最后,我们检查第六个数字,这个数字是 42,42 必须往左移,一直移到 42 的左边是 36 为止,所以我们的排列就变成了 "15, 27, 36, 42 ,53, 69" 排序因此完成了。
ps: 读者也可以自己打开下面的链接,自己设定要排序的数组,进行排序演练
直接插入排序动画 演示
所谓插入排序法,就是检查第 i 个数字,如果在它的左边的数字比它大,进行交换,这个动作一直继续下去,直到这个数字的左边数字比它还要小,就可以停止了。插入排序法主要的回圈有两个变数:i 和 j,每一次执行这个回圈,就会将第 i 个数字放到左边恰当的位置去。
二、算法描述
1、从第一个元素开始,该元素可以认为已经被排序。
2、取出下一个元素,在已经排序的元素序列中从后向前扫描。
3、如果该元素(已排序)大于新元素,则将该元素移到下一位置。
4、重复步骤 3,直到找到已排序的元素小于或者大于新元素的位置。
5、将新元素插入到该位置。
6、重复步骤 2。
三、效率分析
如果目标是把 n 个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况如下。
最好情况:序列已经是升序排列了,在这种情况下,需要进行的比较操作需 (n-1) 次即可。
最坏情况:序列是降序排列,那么此时需要进行的比较共有 n(n-1)/2 次。
直接插入排序属于稳定的排序,最坏时间复杂度为 O(n^2),最好时间复杂度为 O(n),空间复杂度为 O(1)。
插入排序的赋值操作是比较操作的次数加上 (n-1) 次。
因此,插入排序不适合对于数据量比较大的排序应用。
四、代码实现
- public class InsertSortTest {
- public static void InsertSort(int[] source) {
- int i, j;
- int insertNode;// 要插入的数据
- // 从数组的第二个元素开始循环将数组中的元素插入
- for (i = 1; i < source.length; i++) {
- // 设置数组中的第2个元素为第一次循环要插入的数据
- insertNode = source[i];
- j = i - 1;
- // 如果要插入的元素小于第j个元素,就将第j个元素向后移
- while ((j >= 0) && insertNode < source[j]) {
- source[j + 1] = source[j];
- j--;
- }
- // 直到要插入的元素不小于第j个元素,将insertNote插入到数组中
- source[j + 1] = insertNode;
- System.out.print("第" + i + "趟排序:");
- printArray(source);
- }
- }
- private static void printArray(int[] source) {
- for (int i = 0; i < source.length; i++) {
- System.out.print("\t" + source[i]);
- }
- System.out.println();
- }
- public static void main(String[] args) {
- int source[] = new int[] { 53, 27, 36, 15, 69, 42 };
- System.out.print("初始关键字:");
- printArray(source);
- System.out.println("");
- InsertSort(source);
- System.out.print("\n\n排序后结果:");
- printArray(source);
- }
- }
五、运行结果
- 初始关键字: 53 27 36 15 69 42
- 第1趟排序: 27 53 36 15 69 42
- 第2趟排序: 27 36 53 15 69 42
- 第3趟排序: 15 27 36 53 69 42
- 第4趟排序: 15 27 36 53 69 42
- 第5趟排序: 15 27 36 42 53 69
- 排序后结果: 15 27 36 42 53 69
来源: http://www.phperz.com/article/17/1221/357726.html