Quick Sort In-place Implementation，quicksort

Quick Sort In-place Implementation，quicksort

在线运行PHP http://www.compileonline.com/execute_php_online.php

<span> 1</span> <?<span>php
</span><span> 2</span> <span>function</span> swap( &<span>$a</span>, &<span>$b</span><span> )
</span><span> 3</span> <span>{
</span><span> 4</span>     <span>$c</span> = <span>$a</span><span>;
</span><span> 5</span>     <span>$a</span> = <span>$b</span><span>;
</span><span> 6</span>     <span>$b</span> = <span>$c</span><span>;
</span><span> 7</span> <span>}
</span><span> 8</span> 
<span> 9</span> <span>/*</span><span>*
</span><span>10</span> <span>* quick sort
</span><span>11</span> <span>* ascend
</span><span>12</span> <span>* in-place
</span><span>13</span> <span>*/</span>
<span>14</span> <span>function</span> quick_sort( &<span>$a</span><span> )
</span><span>15</span> <span>{
</span><span>16</span>     <span>$s</span> = <span>count</span>( <span>$a</span> ); <span>//</span><span> size of a</span>
<span>17</span>     <span>if</span> ( <span>$s</span> < 2 ) <span>return</span><span>;
</span><span>18</span>     <span>$i</span> = 0; <span>//</span><span> index of pivot, for tracking pivot</span>
<span>19</span>     <span>$pivot</span> = <span>$a</span>[<span>$i</span><span>];
</span><span>20</span>     <span>$l</span> = 0; <span>//</span><span> swap listener, if listens no swap, sort fini
</span><span>21</span> 
<span>22</span> <span>    // swap those smaller than pivot to the left</span>
<span>23</span>     <span>for</span> ( <span>$m</span> = 0; <span>$m</span> < <span>$s</span>; <span>$m</span>++<span> )
</span><span>24</span> <span>    {
</span><span>25</span>         <span>if</span> ( <span>$a</span>[<span>$m</span>] < <span>$a</span>[<span>$i</span><span>] )
</span><span>26</span> <span>        {
</span><span>27</span>             swap( <span>$a</span>[<span>$m</span>], <span>$a</span>[<span>$i</span><span>] );
</span><span>28</span>             <span>$i</span> = <span>$m</span><span>;
</span><span>29</span>             <span>$l</span>++<span>;
</span><span>30</span> <span>        }
</span><span>31</span> <span>    }
</span><span>32</span> 
<span>33</span>     <span>//</span><span> swap those larger than pivot to the right</span>
<span>34</span>     <span>for</span> ( <span>$n</span> = 0; <span>$n</span> < <span>$i</span>; <span>$n</span>++<span>)
</span><span>35</span> <span>    {
</span><span>36</span>         <span>if</span> ( <span>$a</span>[<span>$n</span>] > <span>$a</span>[<span>$i</span><span>] )
</span><span>37</span> <span>        {
</span><span>38</span>             swap( <span>$a</span>[<span>$n</span>], <span>$a</span>[<span>$i</span><span>] );
</span><span>39</span>             <span>$i</span> = <span>$n</span><span>;
</span><span>40</span>             <span>$l</span>++<span>;
</span><span>41</span> <span>        }
</span><span>42</span> <span>    }
</span><span>43</span> 
<span>44</span>     <span>if</span> ( <span>$l</span> == 0 ) <span>return</span><span>;
</span><span>45</span>     <span>else</span> <span>$l</span> = 0<span>;
</span><span>46</span>     quick_sort( <span>$a</span><span> );
</span><span>47</span> <span>}
</span><span>48</span> 
<span>49</span> <span>$arr</span> = <span>range</span>( 9, 0<span> );
</span><span>50</span> quick_sort( <span>$arr</span><span> );
</span><span>51</span> <span>echo</span> <span>implode</span>( ', ', <span>$arr</span><span> );
</span><span>52</span> ?>