1+ //插入和归并排序算法
2+ function ArrayList ( ) {
3+ //存储数据数组
4+ var array = [ ] ;
5+ //定义插入方法
6+ this . insert = function ( item ) {
7+ array . push ( item ) ;
8+ } ;
9+
10+ //输出数组内容
11+ this . print = function ( ) {
12+ return array . join ( "," ) ;
13+ } ;
14+
15+ //快速排序
16+ this . quickSort = function ( ) {
17+ quick ( array , 0 , array . length - 1 ) ;
18+ } ;
19+
20+ //私有排序实现方法：拆分数组
21+ var quick = function ( array , left , right ) {
22+ var index ;
23+ if ( array . length > 1 ) {
24+ index = partition ( array , left , right ) ;
25+ if ( left < right ) {
26+ quick ( array , left , index - 1 ) ;
27+ }
28+ if ( right > index ) {
29+ quick ( array , index , right ) ;
30+ }
31+ }
32+ } ;
33+
34+ //划分过程
35+ var partition = function ( array , left , right ) {
36+ var pivot = array [ Math . floor ( ( right + left ) / 2 ) ] ,
37+ i = left ,
38+ j = right ;
39+ while ( i <= j ) {
40+ while ( array [ i ] < pivot ) {
41+ i ++ ;
42+ }
43+ while ( array [ j ] > pivot ) {
44+ j -- ;
45+ }
46+ if ( i <= j ) {
47+ swap ( array , i , j ) ;
48+ i ++ ;
49+ j -- ;
50+ }
51+ }
52+ return i ;
53+ } ;
54+
55+ //交换两个数位置
56+ var swap = function ( arry , index1 , index2 ) {
57+ //方法一
58+ // var temAux = array[index1];
59+ // array[index1] = array[index2];
60+ // array[index2] = temAux;
61+
62+ //方法二 ES6语法
63+ [ array [ index1 ] , array [ index2 ] ] = [ array [ index2 ] , array [ index1 ] ] ;
64+ } ;
65+
66+ //堆排序
67+
68+ var buildHeap = function ( array ) {
69+ var heapSize = array . length ;
70+ for ( var i = Math . floor ( array . length / 2 ) ; i >= 0 ; i -- ) {
71+ heapify ( array , heapSize , i ) ;
72+ }
73+ } ;
74+
75+ var heapify = function ( array , heapSize , i ) {
76+ var left = i * 2 + 1 ;
77+ var right = i * 2 + 2 ;
78+ var largest = i ;
79+ if ( left < heapSize ] && array [ left ] > array [ largest ] ) {
80+ largest = left ;
81+ }
82+ if ( right < heapSize && array [ right ] > array [ largest ] ) {
83+ largest = right ;
84+ }
85+ if ( right != i ) {
86+ swap ( array , i , largest ) ;
87+ heapify ( array , heapSize , largest ) ;
88+ }
89+ } ;
90+
91+ }
92+
93+ //初始化数组
94+ function createNodeSort ( size ) {
95+ var array = new ArrayList ( ) ;
96+ //随机生成10个0到10的数
97+ for ( var i = 0 ; i < 10 ; i ++ ) {
98+ array . insert ( Math . floor ( Math . random ( ) * 10 + i ) ) ;
99+ }
100+ return array ;
101+ }
0 commit comments