11/**
2+ * Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with
3+ *
4+ * Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
5+ *
6+ * Note:
7+ * You are not suppose to use the library's sort function for this problem.
8+ *
9+ * Follow up:
10+ * A rather straight forward solution is a two-pass algorithm using counting sort.
11+ *
12+ * First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
13+ *
14+ * Could you come up with an one-pass algorithm using only constant space?
15+ *
216 * res.js
317 *@authors Joe Jiang (hijiangtao@gmail.com)
418 *@date 2017-03-02 23:33:12
519 *@version $Id$
20+ *
21+ *@param {number[] } nums
22+ *@return {void } Do not return anything, modify nums in-place instead.
623 */
24+ let sortColors = function ( nums ) {
25+ let numsize = nums . length ,
26+ begin = 0 ,
27+ end = numsize - 1 ;
28+
29+ for ( let i = 0 ; i <= end ; i ++ ) {
30+ let currentVal = nums [ i ] ;
31+ switch ( currentVal ) {
32+ case 0 :
33+ nums [ i ] = nums [ begin ] ;
34+ nums [ begin ++ ] = 0 ;
35+ break ;
36+ case 2 :
37+ nums [ i -- ] = nums [ end ] ;
38+ nums [ end -- ] = 2 ;
39+ break ;
40+ default :
41+ break ;
42+ }
43+ }
44+
45+ } ;
746
47+ // another one-pass solution
48+ let sortColors = function ( nums ) {
49+ let numsize = nums . length ,
50+ n0 = - 1 ,
51+ n1 = - 1 ,
52+ n2 = - 1 ;
53+
54+ for ( let i = 0 ; i < numsize ; ++ i ) {
55+ if ( nums [ i ] == 0 ) {
56+ nums [ ++ n2 ] = 2 ;
57+ nums [ ++ n1 ] = 1 ;
58+ nums [ ++ n0 ] = 0 ;
59+ } else if ( nums [ i ] == 1 ) {
60+ nums [ ++ n2 ] = 2 ;
61+ nums [ ++ n1 ] = 1 ;
62+ } else if ( nums [ i ] == 2 ) {
63+ nums [ ++ n2 ] = 2 ;
64+ }
65+ }
66+ } ;
67+
68+ // traditional two-pass solution
69+ let sortColors = function ( nums ) {
70+ let numsize = nums . length ,
71+ n0 = 0 ,
72+ n1 = 0 ;
73+
74+ for ( let i = 0 ; i < numsize ; i ++ ) {
75+ if ( nums [ i ] === 0 ) {
76+ nums [ n0 ++ ] = 0 ;
77+ } else if ( nums [ i ] === 1 ) {
78+ n1 += 1 ;
79+ }
80+ }
81+
82+ n1 += n0 ;
83+ for ( let i = n0 ; i < numsize ; i ++ ) {
84+ if ( i < n1 ) {
85+ nums [ i ] = 1 ;
86+ } else {
87+ nums [ i ] = 2 ;
88+ }
89+ }
90+ } ;