-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathindex.html
1393 lines (887 loc) · 62.5 KB
/
index.html
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!doctype html>
<html class="theme-next use-motion theme-next-mist">
<head>
<meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>
<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />
<link rel="stylesheet" type="text/css" href="/vendors/fancybox/source/jquery.fancybox.css?v=2.1.5"/>
<link rel="stylesheet" type="text/css" href="/css/main.css?v=0.4.4"/>
<meta name="description" content="Android | Java" />
<meta name="keywords" content="技术博客,tosslife,android,java," />
<link rel="alternate" href="/atom.xml" title="Tosslife" type="application/atom+xml" />
<link rel="shorticon icon" type="image/x-icon" href="/favicon.ico?v=0.4.4" />
<meta name="description" content="Android | Java">
<meta property="og:type" content="website">
<meta property="og:title" content="Tosslife">
<meta property="og:url" content="http://tosslife.github.io/index.html">
<meta property="og:site_name" content="Tosslife">
<meta property="og:description" content="Android | Java">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="Tosslife">
<meta name="twitter:description" content="Android | Java">
<script type="text/javascript" id="hexo.configuration">
var CONFIG = {
scheme: 'Mist',
sidebar: 'post'
};
</script>
<title> Tosslife </title>
</head>
<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">
<!--[if lte IE 8]>
<div style=' clear: both; height: 59px; padding:0 0 0 15px; position: relative;margin:0 auto;'>
<a href="http://windows.microsoft.com/en-US/internet-explorer/products/ie/home?ocid=ie6_countdown_bannercode">
<img src="http://7u2nvr.com1.z0.glb.clouddn.com/picouterie.jpg" border="0" height="42" width="820"
alt="You are using an outdated browser. For a faster, safer browsing experience, upgrade for free today or use other browser ,like chrome firefox safari."
style='margin-left:auto;margin-right:auto;display: block;'/>
</a>
</div>
<![endif]-->
<script type="text/javascript">
var _hmt = _hmt || [];
(function() {
var hm = document.createElement("script");
hm.src = "//hm.baidu.com/hm.js?edd2646a68ccf93c1438bd7e826fc4da";
var s = document.getElementsByTagName("script")[0];
s.parentNode.insertBefore(hm, s);
})();
</script>
<div class="container one-column
page-home
">
<div class="headband"></div>
<header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
<div class="header-inner"><h1 class="site-meta">
<span class="logo-line-before"><i></i></span>
<a href="/" class="brand" rel="start">
<span class="logo">
<i class="icon-logo"></i>
</span>
<span class="site-title">Tosslife</span>
</a>
<span class="logo-line-after"><i></i></span>
</h1>
<div class="site-nav-toggle">
<button>
<span class="btn-bar"></span>
<span class="btn-bar"></span>
<span class="btn-bar"></span>
</button>
</div>
<nav class="site-nav">
<ul id="menu" class="menu ">
<li class="menu-item menu-item-home">
<a href="/" rel="section">
<i class="menu-item-icon icon-home"></i> <br />
首页
</a>
</li>
<li class="menu-item menu-item-archives">
<a href="/archives" rel="section">
<i class="menu-item-icon icon-archives"></i> <br />
归档
</a>
</li>
<li class="menu-item menu-item-about">
<a href="/about" rel="section">
<i class="menu-item-icon icon-about"></i> <br />
关于
</a>
</li>
</ul>
</nav>
</div>
</header>
<main id="main" class="main">
<div class="main-inner">
<div id="content" class="content">
<section id="posts" class="posts-expand">
<article class="post post-type-normal " itemscope itemtype="http://schema.org/Article">
<header class="post-header">
<h1 class="post-title" itemprop="name headline">
<a class="post-title-link" href="/2016/02/23/Android面试宝典/" itemprop="url">
Android面试宝典
</a>
</h1>
<div class="post-meta">
<span class="post-time">
发表于
<time itemprop="dateCreated" datetime="2016-02-23T08:45:50+08:00" content="2016-02-23">
2016-02-23
</time>
</span>
<span class="post-comments-count">
|
<a href="/2016/02/23/Android面试宝典/#comments" itemprop="discussionUrl">
<span class="post-comments-count ds-thread-count" data-thread-key="2016/02/23/Android面试宝典/" itemprop="commentsCount"></span>
</a>
</span>
</div>
</header>
<div class="post-body">
<span itemprop="articleBody"><h3 id="Java部分">Java部分</h3><ol>
<li><p><strong>equals与==的区别</strong></p>
<p> ==是判断两个变量或实例是不是指向同一个内存空间<br> equals是判断两个变量或实例所指向的内存空间的值是不是相同 </p>
</li>
<li><p><strong>String、StringBuffer和StringBuilder的区别</strong></p>
<p> String 不可变 每次对其操作都会在数据池产生一个新的对象，不适合使用在对字符串进行频繁修改的场景<br> StringBuffer和StringBuilder可变，对其修改不会产生新的对象 其两者区别在于StringBuffer线程安全而StringBuilder线程不安全</p>
</li>
<li><p><strong>Override和Overload的含义去区别</strong></p>
<p> override是重写（覆盖）方法名相同，实现不同。<br> overload是重载，方法名相同，参数形式不同。</p>
</li>
<li><p><strong>抽象类和接口的区别</strong> </p>
<p> ①抽象类可以有构造方法，接口中不能有构造方法。<br> ②抽象类中可以有普通成员变量，接口中没有普通成员变量<br> ③抽象类中可以包含非抽象的普通方法，接口中的所有方法必须都是抽象的，不能有非抽象的普通方法。<br> ④抽象类中的抽象方法的访问类型可以是public，protected和（默认类型,虽然eclipse下不报错，但应该也不行），但接口中的抽象方法只能是public类型的，并且默认即为public abstract类型。<br> ⑤抽象类中可以包含静态方法，接口中不能包含静态方法<br> ⑥抽象类和接口中都可以包含静态成员变量，抽象类中的静态成员变量的访问类型可以任意，但接口中定义的变量只能是public static final类型，并且默认即为public static final类型。<br> ⑦一个类可以实现多个接口，但只能继承一个抽象类。</p>
</li>
</ol>
<ol>
<li><p><strong>sleep()和wait()的区别</strong></p>
<p> 对于sleep()方法，我们首先要知道该方法是属于Thread类中的。而wait()方法，则是属于Object类中的。<br> sleep()方法导致了程序暂停执行指定的时间，让出cpu该其他线程，但是他的监控状态依然保持者，当指定的时间到了又会自动恢复运行状态。<br> 在调用sleep()方法的过程中，线程不会释放对象锁。<br> 而当调用wait()方法的时候，线程会放弃对象锁，进入等待此对象的等待锁定池，只有针对此对象调用notify()方法后本线程才进入对象锁定池准备，获取对象锁进入运行状态。</p>
</li>
<li><p><strong>HashMap Hashtable区别</strong></p>
<p> ① Hashtable是Dictionary的子类，HashMap是Map接口的一个实现类；<br> ② HashTable不允许null值(key和value都不可以) ,HashMap允许null值(key和value都可以)。<br> ③ Hashtable中的方法是同步的（），而HashMap中的方法在默认情况下不是同步的。即是说，在多线程应用程序中，不用专门的操作就安全地可以使用Hashtable了；而对于HashMap，则需要额外的同步机制。但HashMap的同步问题可通过Collections的一个静态方法得到解决。</p>
</li>
<li><p><strong>final、finally、finalize的区别</strong></p>
<p> ①final用于声明属性，方法和类，分别表示属性不可交变，方法不可覆盖，类不可继承。<br> ②finally是异常处理语句结构的一部分，表示总是执行。<br> ③finalize是Object类的一个方法，在垃圾收集器执行的时候会调用被回收对象的此方法，供垃圾收集时的其他资源回收，例如关闭文件等</p>
</li>
<li><p><strong>Comparable和Comparator区别</strong></p>
<p> Comparable和Comparator都是用来实现集合中元素的比较、排序的。<br> Comparable是在集合内部定义的方法实现的排序，位于java.util下。<br> Comparator是在集合外部实现的排序，位于java.lang下。<br> Comparable是自已完成比较，Comparator是外部程序实现比较。</p>
</li>
<li><p>&&和&以及||和|的区别</p>
<p> &&和&都是表示与，区别是&&只要满足第一个条件，后面条件就不再判断。而&要对所有的条件都进行判断。<br> ||（短路或）和|（或）都是表示“或”，区别是||只要满足第一个条件，后面的条件就不再判断，而|要对所有的条件进行判断。</p>
</li>
<li><p><strong>说出ArrayList,Vector,LinkedList的存储性能和特性</strong></p>
<p> ArrayList和Vector都是使用数组方式存储数据，此数组元素数大于实际存储的数据以便增加和插入元素，它们都允许直接按序号索引元素，但是插入元素要涉及数组元素移动等内存操作，所以索引数据快而插入数据慢，Vector由于使用了synchronized方法（线程安全），通常性能上较ArrayList差，而LinkedList使用双向链表实现存 储，按序号索引数据需要进行前向或后向遍历，但是插入数据时只需要记录本项的前后项即可，所以插入速度较快。<br> 一.同步性:Vector是线程安全的，也就是说是同步的，而ArrayList是线程序不安全的，不是同步的<br> 二.数据增长:当需要增长时,Vector 默认增长为原来一培，而ArrayList却是原来的一半</p>
</li>
<li><p><strong>HashMap的底层源码实现</strong></p>
<p>当我们往HashMap中put元素的时候，先根据key的hashCode重新计算hash值，根据hash值得到这个元素在数组中的位置（即下标），如果数组该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。如果数组该位置上没有元素，就直接将该元素放到此数组中的该位置上。</p>
</li>
<li><p><strong>多态的实现机制</strong></p>
</li>
</ol>
<pre><code>靠的是父类或接口定义的引用变量可以指向子类或具体实现类的实例对象，而程序调用的方法在运行期才动态绑定，就是引用变量所指向的具体实例对象的方法，也就是内存里正在运行的那个对象的方法，而不是引用变量的类型中定义的方法
</code></pre><ol>
<li><p><strong>Switch能否用string做参数</strong></p>
<p>在 Java 7 之前, switch 只能支持byte,short,char,int 或者其对应的封装类以及 Enum 类型。在JAVA 7中,String 支持被加上了。</p>
</li>
<li><p><strong>Collection 和 Collections的区别</strong></p>
<p>①Collection是集合类的上级接口，继承与他的接口主要有Set 和List.</p>
<p>②Collections是针对集合类的一个帮助类，他提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。</p>
</li>
<li><p><strong>同步和异步有何异同，在什么情况下分别使用他们？举例说明。</strong></p>
<p>如果数据将在线程间共享。例如正在写的数据以后可能被另一个线程读到，或者正在读的数据可能已经被另一个线程写过了，那么这些数据就是共享数据，必须进行同步存取。</p>
<p>当应用程序在对象上调用了一个需要花费很长时间来执行的方法，并且不希望让程序等待方法的返回时，就应该使用异步编程，在很多情况下采用异步途径往往更有效率。</p>
</li>
</ol>
</span>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article class="post post-type-normal " itemscope itemtype="http://schema.org/Article">
<header class="post-header">
<h1 class="post-title" itemprop="name headline">
<a class="post-title-link" href="/2015/11/12/Android-积累的小技巧汇总/" itemprop="url">
Android 积累的小技巧汇总
</a>
</h1>
<div class="post-meta">
<span class="post-time">
发表于
<time itemprop="dateCreated" datetime="2015-11-12T18:08:58+08:00" content="2015-11-12">
2015-11-12
</time>
</span>
<span class="post-comments-count">
|
<a href="/2015/11/12/Android-积累的小技巧汇总/#comments" itemprop="discussionUrl">
<span class="post-comments-count ds-thread-count" data-thread-key="2015/11/12/Android-积累的小技巧汇总/" itemprop="commentsCount"></span>
</a>
</span>
</div>
</header>
<div class="post-body">
<span itemprop="articleBody"><h3 id="开篇导读">开篇导读</h3><p><strong>接触Android开发已经有些时日了，也算总结积累了一些小技巧，如今汇总分享给大家</strong></p>
<h6 id="include标签(避免重复渲染)和_ViewStub类(延迟加载)">include标签(避免重复渲染)和 ViewStub类(延迟加载)</h6><ol>
<li><p>当我们的页面变得复杂，XML文件内容过多时，<include>标签可以有效地帮助我们整理文件内容，同时提高了XML文件的可读性。同时，它的用法也与Fragment类似。</include></p>
</li>
<li><p>ViewStub是一个极佳的延迟加载视图资源的方式。只要你设计的视图是依赖于上下文来改变其可见性的，就利用ViewStub类吧。也许当你只将其应用在一个简单的页面当中时，并不会感觉到在性能上有任何提升，但是在复杂页面中，它的效果是极佳的。</p>
</li>
</ol>
</span>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article class="post post-type-normal " itemscope itemtype="http://schema.org/Article">
<header class="post-header">
<h1 class="post-title" itemprop="name headline">
<a class="post-title-link" href="/2015/07/31/Android中Java与Js交互及Js注入取Html标签值详解/" itemprop="url">
Android中Java与Js交互及Js注入取Html标签值详解
</a>
</h1>
<div class="post-meta">
<span class="post-time">
发表于
<time itemprop="dateCreated" datetime="2015-07-31T14:41:05+08:00" content="2015-07-31">
2015-07-31
</time>
</span>
<span class="post-comments-count">
|
<a href="/2015/07/31/Android中Java与Js交互及Js注入取Html标签值详解/#comments" itemprop="discussionUrl">
<span class="post-comments-count ds-thread-count" data-thread-key="2015/07/31/Android中Java与Js交互及Js注入取Html标签值详解/" itemprop="commentsCount"></span>
</a>
</span>
</div>
</header>
<div class="post-body">
<span itemprop="articleBody"><h3 id="开篇导读">开篇导读</h3><p><strong>Android提供了WebView控件用来处理Web网页，而在网页中，JavaScript一个很举足轻重的脚本。</strong><br><strong>本文将介绍如何通过JavaScript代码注入实现获取Html中标签值继而实现Java代码和Javascript代码的相互调用</strong></p>
<hr>
<h3 id="操作步骤">操作步骤</h3><ol>
<li><p>WebView开启Js调用：</p>
<pre><code>mWebView.getSettings<span class="params">()</span>.setJavaScriptEnabled<span class="params">(<span class="literal">true</span>)</span>;
</code></pre></li>
<li><p>定义JavaScript调用的交互接口及方法：</p>
<pre><code><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">JavaScriptInterface</span> </span>{
<span class="annotation">@JavascriptInterface</span>
<span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">getTagVal</span><span class="params">(<span class="keyword">final</span> String val)</span> </span>{
<span class="keyword">if</span> (!TextUtils.isEmpty(shareUrl)) {
Log.e(<span class="string">"log tag"</span>, <span class="string">"received from js. val = "</span> + val);
}
}
}
</code></pre></li>
<li><p>WebView设置供JavaScript调用的交互接口。</p>
<pre><code><span class="comment">//后面 “android” 相当于一个标志符</span>
mWebView.addJavascriptInterface<span class="params">(new JavaScriptInterface<span class="params">()</span>, <span class="string">"android"</span>)</span>;
</code></pre></li>
<li><p>在WebView加载完毕时注入JavaScript代码</p>
<p> 先看网页代码</p>
<pre><code>//这里是Html中我要通过注入取得的标签代码
<meta <span class="variable">name=</span><span class="string">"tag"</span> <span class="variable">content=</span><span class="string">"恭喜你注入成功，得到了返回值"</span> />
</code></pre><p> 再来实现我们的java代码</p>
<pre><code>mWebView.setWebViewClient(<span class="keyword">new</span> WebViewClient() {
<span class="keyword">public</span> <span class="function"><span class="keyword">boolean</span> <span class="title">shouldOverrideUrlLoading</span><span class="params">(WebView view, String url)</span> </span>{
view.loadUrl(url);
<span class="comment">//返回值为true的时候控制去WebView打开，为false调用系统浏览器或第三方浏览器</span>
<span class="keyword">return</span> <span class="keyword">true</span>;
}
<span class="annotation">@Override</span>
<span class="keyword">public</span> <span class="function"><span class="keyword">void</span> <span class="title">onPageFinished</span><span class="params">(WebView webView, String url)</span> </span>{
<span class="comment">//此处windows.android.getTagVal中android是第3步中设置的标记，getTagVal是第2步中的接口中的方法名</span>
<span class="comment">//回调的参数中传的就是js代码，自行根据实际html标签脑补或百度</span>
String js = <span class="string">"window.android.getTagVal(document.getElementsByName('tag')[0].content))"</span>;
webView.loadUrl(<span class="string">"javascript:"</span> + js);
}
});
</code></pre></li>
</ol>
<p><strong>OK！完美收官</strong></p>
</span>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article class="post post-type-normal " itemscope itemtype="http://schema.org/Article">
<header class="post-header">
<h1 class="post-title" itemprop="name headline">
<a class="post-title-link" href="/2012/08/06/算法简析之归并排序/" itemprop="url">
算法简析之归并排序
</a>
</h1>
<div class="post-meta">
<span class="post-time">
发表于
<time itemprop="dateCreated" datetime="2012-08-06T16:22:59+08:00" content="2012-08-06">
2012-08-06
</time>
</span>
<span class="post-comments-count">
|
<a href="/2012/08/06/算法简析之归并排序/#comments" itemprop="discussionUrl">
<span class="post-comments-count ds-thread-count" data-thread-key="2012/08/06/算法简析之归并排序/" itemprop="commentsCount"></span>
</a>
</span>
</div>
</header>
<div class="post-body">
<span itemprop="articleBody"><h3 id="简析">简析</h3><hr>
<h4 id="概念">概念</h4><p><strong>归并排序</strong> 归并排序是利用递归和分而治之的技术将数据序列划分成为越来越小的半子表，再对半子表排序，最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列，归并排序包括两个步骤，分别为：</p>
<h4 id="原理">原理</h4><ol>
<li><p><strong>拆分</strong>：假设有N个元素的列表，首先把它拆分成2个或2个以上的元素组成的新的列表，分别对对它们进行排序。</p>
</li>
<li><p><strong>归并</strong>：把所有的排好序的子类表两两归并，如此重复，直到归并成一个含N个元素的有序列表为止 </p>
</li>
</ol>
<hr>
<h3 id="范例（java）">范例（java）</h3><h4 id="概念代码">概念代码</h4><pre><code><span class="keyword">public</span> <span class="keyword">static</span> <span class="built_in">int</span>[] <span class="built_in">sort</span>(<span class="built_in">int</span>[] nums, <span class="built_in">int</span> low, <span class="built_in">int</span> high) {
<span class="built_in">int</span> mid = (low + high) / <span class="number">2</span>;
<span class="keyword">if</span> (low < high) {
<span class="comment">// 左边 </span>
<span class="built_in">sort</span>(nums, low, mid);
<span class="comment">// 右边 </span>
<span class="built_in">sort</span>(nums, mid + <span class="number">1</span>, high);
<span class="comment">// 左右归并 </span>
merge(nums, low, mid, high);
}
<span class="keyword">return</span> nums;
}
<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> merge(<span class="built_in">int</span>[] nums, <span class="built_in">int</span> low, <span class="built_in">int</span> mid, <span class="built_in">int</span> high) {
<span class="built_in">int</span>[] temp = <span class="keyword">new</span> <span class="built_in">int</span>[high - low + <span class="number">1</span>];
<span class="built_in">int</span> i = low;<span class="comment">// 左指针 </span>
<span class="built_in">int</span> j = mid + <span class="number">1</span>;<span class="comment">// 右指针 </span>
<span class="built_in">int</span> k = <span class="number">0</span>;
<span class="comment">// 把较小的数先移到新数组中 </span>
<span class="keyword">while</span> (i <= mid && j <= high) {
<span class="keyword">if</span> (nums[i] < nums[j]) {
temp[k++] = nums[i++];
} <span class="keyword">else</span> {
temp[k++] = nums[j++];
}
}
<span class="comment">// 把左边剩余的数移入数组 </span>
<span class="keyword">while</span> (i <= mid) {
temp[k++] = nums[i++];
}
<span class="comment">// 把右边边剩余的数移入数组 </span>
<span class="keyword">while</span> (j <= high) {
temp[k++] = nums[j++];
}
<span class="comment">// 把新数组中的数覆盖nums数组 </span>
<span class="keyword">for</span> (<span class="built_in">int</span> k2 = <span class="number">0</span>; k2 < temp.length; k2++) {
nums[k2 + low] = temp[k2];
}
}
<span class="comment">// 归并排序的实现 </span>
<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> main(<span class="keyword">String</span>[] args) {
<span class="built_in">int</span>[] nums = { <span class="number">2</span>, <span class="number">7</span>, <span class="number">8</span>, <span class="number">3</span>, <span class="number">1</span>, <span class="number">6</span>, <span class="number">9</span>, <span class="number">0</span>, <span class="number">5</span>, <span class="number">4</span> };
MergeSort.<span class="built_in">sort</span>(nums, <span class="number">0</span>, nums.length-<span class="number">1</span>);
System.out.<span class="built_in">println</span>(Arrays.toString(nums));
}
</code></pre><hr>
</span>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article class="post post-type-normal " itemscope itemtype="http://schema.org/Article">
<header class="post-header">
<h1 class="post-title" itemprop="name headline">
<a class="post-title-link" href="/2012/07/31/算法简析之希尔排序/" itemprop="url">
算法简析之希尔排序
</a>
</h1>
<div class="post-meta">
<span class="post-time">
发表于
<time itemprop="dateCreated" datetime="2012-07-31T17:29:39+08:00" content="2012-07-31">
2012-07-31
</time>
</span>
<span class="post-comments-count">
|
<a href="/2012/07/31/算法简析之希尔排序/#comments" itemprop="discussionUrl">
<span class="post-comments-count ds-thread-count" data-thread-key="2012/07/31/算法简析之希尔排序/" itemprop="commentsCount"></span>
</a>
</span>
</div>
</header>
<div class="post-body">
<span itemprop="articleBody"><h3 id="简析">简析</h3><hr>
<h4 id="概念">概念</h4><p><strong>希尔排序（Shell Sort）</strong> 希尔排序的实质就是分组插入排序，该方法又称缩小增量排序。</p>
<h4 id="原理">原理</h4><ol>
<li><p>先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序</p>
</li>
<li><p>依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。</p>
</li>
<li><p>当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。</p>
</li>
</ol>
<hr>
<h3 id="范例（java）">范例（java）</h3><p>初始时，有一个大小为 10 的无序序列{9,1,2,5,7,4,8,6,5,3}。</p>
<p>在第一趟排序中，我们不妨设 gap1 = N / 2 = 5，即相隔距离为 5 的元素组成一组，可以分为 5 组</p>
<p>{9,4}，{1,8}，{2,6}，{5,5}，{7,3}</p>
<p>接下来，按照直接插入排序的方法对每个组进行排序</p>
<p>{4,9}，{1,8}，{2,6}，{5,5}，{3,7}</p>
<p>排序后位置交换原数组 {4,1,2,5,3,9,8,6,5,7} </p>
<p>在第二趟排序中，我们把上次的 gap 缩小一半，即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组，可以分为 2 组。</p>
<p>{4,2,3,8,5},{1,5,9,6,7}</p>
<p>按照直接插入排序的方法对每个组进行排序。</p>
<p>{2,3,4,5,8},{1,5,6,7,9}</p>
<p>排序后位置交换原数组 {2,1,3,5,4,6,5,7,8,9} </p>
<p>在第三趟排序中，再次把 gap 缩小一半，即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组，即只有一组。</p>
<p>{2,1,3,5,4,6,5,7,8,9} </p>
<p>按照直接插入排序的方法对每个组进行排序。此时，排序已经结束。</p>
<p>{1,2,3,4,5,5,6,7,8,9} </p>
<p><strong>需要注意一下的是，图中有两个相等数值的元素 5 和 5 。我们可以清楚的看到，在排序过程中，两个元素位置交换了。<br>所以，希尔排序是不稳定的算法</strong></p>
<hr>
<h4 id="概念代码">概念代码</h4><pre><code><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> main(String[] args) {
<span class="keyword">int</span>[] arr = {<span class="number">9</span>, <span class="number">1</span>, <span class="number">2</span>, <span class="number">5</span>, <span class="number">7</span>, <span class="number">4</span>, <span class="number">8</span>, <span class="number">6</span>, <span class="number">5</span>, <span class="number">3</span>};
<span class="keyword">int</span> i, j, gap;
<span class="keyword">int</span> m = <span class="number">1</span>;<span class="comment">//输出gap步数</span>
<span class="keyword">int</span> <span class="keyword">count</span> = arr.length;
<span class="keyword">for</span> (gap = <span class="keyword">count</span> <span class="regexp">/ 2; gap > 0; gap /</span>= <span class="number">2</span>) { <span class="comment">//步长</span>
<span class="keyword">for</span> (i = <span class="number">0</span>; i < gap; i++) {<span class="comment">//直接插入排序</span>
<span class="keyword">for</span> (j = i + gap; j < <span class="keyword">count</span>; j += gap)
<span class="keyword">if</span> (arr[j] < arr[j - gap]) {
<span class="keyword">int</span> temp = arr[j];
<span class="keyword">int</span> k = j - gap;
<span class="keyword">while</span> (k >= <span class="number">0</span> && arr[k] > temp) {
arr[k + gap] = arr[k];
k -= gap;
}
arr[k + gap] = temp;
}
}
System.out.<span class="keyword">print</span>(<span class="string">"第"</span> + m + <span class="string">"次排序结果："</span>);
<span class="keyword">for</span> (<span class="keyword">int</span> anArr : arr) {
System.out.<span class="keyword">print</span>(anArr + <span class="string">"\t"</span>);
}
System.out.<span class="keyword">println</span>(<span class="string">""</span>);
m++;
}
System.out.<span class="keyword">print</span>(<span class="string">"最终排序结果："</span>);
<span class="keyword">for</span> (<span class="keyword">int</span> anArr : arr) {
System.out.<span class="keyword">print</span>(anArr + <span class="string">"\t"</span>);
}
}
</code></pre><figure class="highlight dns"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">第1次排序结果：<span class="number">4 1 2 5</span> <span class="number">3 9 8 6</span> 5 7 </span><br><span class="line">第2次排序结果：<span class="number">2 1 3 5</span> <span class="number">4 6 5 7</span> 8 9 </span><br><span class="line">第3次排序结果：<span class="number">1 2 3 4</span> <span class="number">5 5 6 7</span> 8 9 </span><br><span class="line">最终排序结果：<span class="number">1 2 3 4</span> <span class="number">5 5 6 7</span> 8 9</span><br></pre></td></tr></table></figure>
</span>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article class="post post-type-normal " itemscope itemtype="http://schema.org/Article">
<header class="post-header">
<h1 class="post-title" itemprop="name headline">
<a class="post-title-link" href="/2012/07/30/算法简析之直接选择排序/" itemprop="url">
算法简析之直接选择排序
</a>
</h1>
<div class="post-meta">
<span class="post-time">
发表于
<time itemprop="dateCreated" datetime="2012-07-30T18:59:49+08:00" content="2012-07-30">
2012-07-30
</time>
</span>
<span class="post-comments-count">
|
<a href="/2012/07/30/算法简析之直接选择排序/#comments" itemprop="discussionUrl">
<span class="post-comments-count ds-thread-count" data-thread-key="2012/07/30/算法简析之直接选择排序/" itemprop="commentsCount"></span>
</a>
</span>
</div>
</header>
<div class="post-body">
<span itemprop="articleBody"><h3 id="简析">简析</h3><hr>
<h4 id="概念">概念</h4><p><strong>直接选择排序（Select sort）</strong> 每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。</p>
<h4 id="原理">原理</h4><ol>
<li><p>初始时，数组全为无序区为a[0..n-1]。令i=0</p>
</li>
<li><p>在无序区a[i…n-1]中选取一个最小的元素，将其与a[i]交换。交换之后a[0…i]就形成了一个有序区。</p>
</li>
<li><p>i++并重复第二步直到i==n-1。排序完成。</p>
</li>
</ol>
<hr>
<h3 id="范例（java）">范例（java）</h3><hr>
<h4 id="概念代码">概念代码</h4><pre><code> <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> main(<span class="keyword">String</span>[] args) {
<span class="built_in">int</span> arr[] = {<span class="number">23</span>, <span class="number">44</span>, <span class="number">56</span>, <span class="number">21</span>, <span class="number">32</span>, <span class="number">55</span>, <span class="number">74</span>, <span class="number">13</span>};
<span class="built_in">int</span> count = arr.length;
<span class="built_in">int</span> i, j, <span class="built_in">min</span>;
<span class="keyword">for</span> (i = <span class="number">0</span>; i < count; i++) {
<span class="built_in">min</span> = i;
<span class="keyword">for</span> (j = i + <span class="number">1</span>; j < count; j++) {
<span class="keyword">if</span> (arr[j] < arr[<span class="built_in">min</span>]) {<span class="comment">//找最小元素的位置</span>
<span class="built_in">min</span> = j;
}
}
<span class="built_in">int</span> temp = arr[i];
arr[i] = arr[<span class="built_in">min</span>];
arr[<span class="built_in">min</span>] = temp;
System.out.<span class="built_in">print</span>(<span class="string">"第"</span> + (i + <span class="number">1</span>) + <span class="string">"次排序结果："</span>);
<span class="keyword">for</span> (<span class="built_in">int</span> anArr : arr) {
System.out.<span class="built_in">print</span>(anArr + <span class="string">"\t"</span>);
}
System.out.<span class="built_in">println</span>(<span class="string">""</span>);
}
System.out.<span class="built_in">print</span>(<span class="string">"最终排序结果："</span>);
<span class="keyword">for</span> (<span class="built_in">int</span> anArr : arr) {
System.out.<span class="built_in">print</span>(anArr + <span class="string">"\t"</span>);
}
}
</code></pre><figure class="highlight dns"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line">第1次排序结果：<span class="number">13 44 56 21</span> <span class="number">32 55 74 23</span> </span><br><span class="line">第2次排序结果：<span class="number">13 21 56 44</span> <span class="number">32 55 74 23</span> </span><br><span class="line">第3次排序结果：<span class="number">13 21 23 44</span> <span class="number">32 55 74 56</span> </span><br><span class="line">第4次排序结果：<span class="number">13 21 23 32</span> <span class="number">44 55 74 56</span> </span><br><span class="line">第5次排序结果：<span class="number">13 21 23 32</span> <span class="number">44 55 74 56</span> </span><br><span class="line">第6次排序结果：<span class="number">13 21 23 32</span> <span class="number">44 55 74 56</span> </span><br><span class="line">第7次排序结果：<span class="number">13 21 23 32</span> <span class="number">44 55 56 74</span> </span><br><span class="line">第8次排序结果：<span class="number">13 21 23 32</span> <span class="number">44 55 56 74</span> </span><br><span class="line">最终排序结果：<span class="number">13 21 23 32</span> <span class="number">44 55 56 74</span></span><br></pre></td></tr></table></figure>
</span>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article class="post post-type-normal " itemscope itemtype="http://schema.org/Article">
<header class="post-header">
<h1 class="post-title" itemprop="name headline">
<a class="post-title-link" href="/2012/07/30/算法简析之插入排序/" itemprop="url">
算法简析之插入排序
</a>
</h1>
<div class="post-meta">
<span class="post-time">
发表于
<time itemprop="dateCreated" datetime="2012-07-30T11:51:30+08:00" content="2012-07-30">
2012-07-30
</time>
</span>
<span class="post-comments-count">
|
<a href="/2012/07/30/算法简析之插入排序/#comments" itemprop="discussionUrl">
<span class="post-comments-count ds-thread-count" data-thread-key="2012/07/30/算法简析之插入排序/" itemprop="commentsCount"></span>
</a>
</span>
</div>
</header>
<div class="post-body">
<span itemprop="articleBody"><h3 id="简析">简析</h3><hr>
<h4 id="概念">概念</h4><p><strong>插入排序（Insertion sort）</strong> 插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。 插入排序方法分直接插入排序和折半插入排序两种。</p>
<p><strong>直接插入排序</strong> 把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。</p>
<p><strong>折半插入排序（binary insertion sort）</strong> 是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。</p>
<h4 id="直接插入排序原理">直接插入排序原理</h4><p>假设待排序的记录存放在数组a[0…n-1]。</p>
<ol>
<li><p>初始时，a[0]自成1个有序区，无序区为a[1..n-1]。令i=1</p>
</li>
<li><p>将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。</p>
</li>
<li><p>i++并重复第二步直到i==n-1。排序完成。</p>
</li>
</ol>
<h4 id="折半插入排序原理">折半插入排序原理</h4><ol>
<li><p>将待插入区域的首元素设置为a[low],末元素设置为a[high]，则轮比较时将待插入元素与a[m]</p>
</li>
<li><p>其中m=(low+high)/2相比较,如果比参考元素小，则选择a[low]到a[m-1]为新的插入区域(即high=m-1)，否则选择a[m+1]到a[high]为新的插入区域（即low=m+1）</p>
</li>
<li><p>如此直至low<=high不成立，即将此位置之后所有元素后移一位，并将新元素插入a[high+1]。</p>
</li>
</ol>
<hr>
<h3 id="范例（java）">范例（java）</h3><hr>
<h4 id="概念代码">概念代码</h4><pre><code> <span class="comment">//直接插入排序</span>
<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> main(String[] args) {
<span class="keyword">int</span> arr[] = {<span class="number">23</span>, <span class="number">44</span>, <span class="number">56</span>, <span class="number">21</span>, <span class="number">32</span>, <span class="number">55</span>, <span class="number">74</span>, <span class="number">13</span>};
<span class="keyword">int</span> <span class="keyword">count</span> = arr.length;
<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i < <span class="keyword">count</span>; i++) {
<span class="keyword">int</span> temp = arr[i];
<span class="keyword">int</span> position = i;
<span class="keyword">for</span> (<span class="keyword">int</span> j = i - <span class="number">1</span>; j >= <span class="number">0</span>; j--) {
<span class="keyword">if</span> (arr[j] > temp) {
arr[j + <span class="number">1</span>] = arr[j];
position -= <span class="number">1</span>;
} <span class="keyword">else</span> {
<span class="keyword">break</span>;
}
}
arr[position] = temp;
System.out.<span class="keyword">print</span>(<span class="string">"第"</span> + i + <span class="string">"次排序结果："</span>);
<span class="keyword">for</span> (<span class="keyword">int</span> anArr : arr) {
System.out.<span class="keyword">print</span>(anArr + <span class="string">"\t"</span>);
}
System.out.<span class="keyword">println</span>(<span class="string">""</span>);
}
System.out.<span class="keyword">print</span>(<span class="string">"最终排序结果："</span>);
<span class="keyword">for</span> (<span class="keyword">int</span> anArr : arr) {
System.out.<span class="keyword">print</span>(anArr + <span class="string">"\t"</span>);
}
}
</code></pre><figure class="highlight dns"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">第1次排序结果：<span class="number">23 44 56 21</span> <span class="number">32 55 74 13</span> </span><br><span class="line">第2次排序结果：<span class="number">23 44 56 21</span> <span class="number">32 55 74 13</span> </span><br><span class="line">第3次排序结果：<span class="number">21 23 44 56</span> <span class="number">32 55 74 13</span> </span><br><span class="line">第4次排序结果：<span class="number">21 23 32 44</span> <span class="number">56 55 74 13</span> </span><br><span class="line">第5次排序结果：<span class="number">21 23 32 44</span> <span class="number">55 56 74 13</span> </span><br><span class="line">第6次排序结果：<span class="number">21 23 32 44</span> <span class="number">55 56 74 13</span> </span><br><span class="line">第7次排序结果：<span class="number">13 21 23 32</span> <span class="number">44 55 56 74</span> </span><br><span class="line">最终排序结果：<span class="number">13 21 23 32</span> <span class="number">44 55 56 74</span></span><br></pre></td></tr></table></figure>
<pre><code> <span class="comment">//折半插入排序</span>
<span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span>(<span class="params">String[] args</span>) </span>{
<span class="keyword">int</span> arr[] = {<span class="number">23</span>, <span class="number">44</span>, <span class="number">56</span>, <span class="number">21</span>, <span class="number">32</span>, <span class="number">55</span>, <span class="number">74</span>, <span class="number">13</span>};
<span class="keyword">int</span> count = arr.length;
<span class="keyword">int</span> middle = <span class="number">0</span>;
<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i < count; i++) {
<span class="keyword">int</span> low = <span class="number">0</span>;
<span class="keyword">int</span> high = i - <span class="number">1</span>;
<span class="keyword">int</span> temp = arr[i];
<span class="keyword">while</span> (low <= high) {
middle = (low + high) / <span class="number">2</span>;
<span class="keyword">if</span> (temp < arr[middle]) {
high = middle - <span class="number">1</span>;
} <span class="keyword">else</span> {
low = middle + <span class="number">1</span>;
}
}
<span class="keyword">int</span> k = i;
<span class="keyword">while</span> (k > middle) {
arr[k] = arr[k - <span class="number">1</span>];
k--;
}
arr[high + <span class="number">1</span>] = temp; <span class="comment">//此处用 arr[low] = temp ;也可</span>
System.<span class="keyword">out</span>.print(<span class="string">"第"</span> + i + <span class="string">"次排序结果："</span>);
<span class="keyword">for</span> (<span class="keyword">int</span> anArr : arr) {
System.<span class="keyword">out</span>.print(anArr + <span class="string">"\t"</span>);
}
System.<span class="keyword">out</span>.println(<span class="string">""</span>);
}
System.<span class="keyword">out</span>.print(<span class="string">"最终排序结果："</span>);
<span class="keyword">for</span> (<span class="keyword">int</span> anArr : arr) {
System.<span class="keyword">out</span>.print(anArr + <span class="string">"\t"</span>);
}
}
</code></pre><figure class="highlight dns"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">第1次排序结果：<span class="number">23 44 56 21</span> <span class="number">32 55 74 13</span> </span><br><span class="line">第2次排序结果：<span class="number">23 44 56 21</span> <span class="number">32 55 74 13</span> </span><br><span class="line">第3次排序结果：<span class="number">21 23 44 56</span> <span class="number">32 55 74 13</span> </span><br><span class="line">第4次排序结果：<span class="number">21 23 32 44</span> <span class="number">56 55 74 13</span> </span><br><span class="line">第5次排序结果：<span class="number">21 23 32 44</span> <span class="number">55 56 74 13</span> </span><br><span class="line">第6次排序结果：<span class="number">21 23 32 44</span> <span class="number">55 56 74 13</span> </span><br><span class="line">第7次排序结果：<span class="number">13 21 23 32</span> <span class="number">44 55 56 74</span> </span><br><span class="line">最终排序结果：<span class="number">13 21 23 32</span> <span class="number">44 55 56 74</span></span><br></pre></td></tr></table></figure>
<hr>
</span>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>