针对堆排序的概念自己百度去,今天没事了用php实现堆排序的算法
<span> 1</span> <span>abstract</span> <span>class</span><span> Heap { </span><span> 2</span> <span>protected</span> <span>$elements</span> = <span>array</span><span>(); </span><span> 3</span> <span>protected</span> <span>$n</span> = 0<span>; </span><span> 4</span> <span> 5</span> <span>public</span> <span>abstract</span> <span>function</span> insert(<span>$element</span><span>); </span><span> 6</span> <span> 7</span> <span>public</span> <span>function</span><span> isEmpty() { </span><span> 8</span> <span>return</span> <span>$this</span>->n==0<span>; </span><span> 9</span> <span> } </span><span>10</span> <span>11</span> <span>public</span> <span>function</span><span> all(){ </span><span>12</span> <span>return</span> <span>$this</span>-><span>elements; </span><span>13</span> <span> } </span><span>14</span> <span>15</span> <span>/*</span><span>* </span><span>16</span> <span> * Extract the top value of the heap </span><span>17</span> <span> * </span><span>18</span> <span>*/</span> <span>19</span> <span>public</span> <span>function</span> <span>extract</span><span>() { </span><span>20</span> <span>$element</span> = <span>$this</span>->elements[1<span>]; </span><span>21</span> <span>$this</span>->elements[1] = <span>array_pop</span>(<span>$this</span>-><span>elements); </span><span>22</span> <span>$this</span>->n--<span>; </span><span>23</span> <span>$this</span>-><span>siftDown(); </span><span>24</span> <span>return</span> <span>$element</span><span>; </span><span>25</span> <span> } </span><span>26</span> <span>27</span> <span>/*</span><span>* </span><span>28</span> <span> * Rearranges the heap after an extraction to keep the heap property </span><span>29</span> <span>*/</span> <span>30</span> <span>protected</span> <span>abstract</span> <span>function</span><span> siftDown(); </span><span>31</span> <span>32</span> <span>/*</span><span>* </span><span>33</span> <span> * Swap two elements on the elements array </span><span>34</span> <span> * </span><span>35</span> <span>*/</span> <span>36</span> <span>protected</span> <span>function</span> swap(<span>$x</span>,<span>$y</span><span>) { </span><span>37</span> <span>$tmp</span> = <span>$this</span>->elements[<span>$x</span><span>]; </span><span>38</span> <span>$this</span>->elements[<span>$x</span>] = <span>$this</span>->elements[<span>$y</span><span>]; </span><span>39</span> <span>$this</span>->elements[<span>$y</span>] = <span>$tmp</span><span>; </span><span>40</span> <span> } </span><span>41</span> <span>} </span><span>42</span> <span>class</span> MinHeap <span>extends</span><span> Heap { </span><span>43</span> <span>44</span> <span>public</span> <span>function</span> insert(<span>$element</span><span>) { </span><span>45</span> <span>$this</span>->elements[++<span>$this</span>->n] = <span>$element</span><span>; </span><span>46</span> <span>for</span> (<span>$i</span> = <span>$this</span>->n; <span>$i</span> > 1 && <span>$this</span>->elements[<span>$i</span> >> 1] > <span>$this</span>->elements[<span>$i</span>]; <span>$i</span> = <span>$i</span> >> 1<span>) </span><span>47</span> <span>$this</span>->swap(<span>$i</span> >> 1,<span>$i</span><span>); </span><span>48</span> <span> } </span><span>49</span> <span>protected</span> <span>function</span><span> siftDown() { </span><span>50</span> <span>for</span> (<span>$i</span> = 1; (<span>$c</span> = <span>$i</span> * 2) <= <span>$this</span>->n; <span>$i</span> = <span>$c</span><span>) { </span><span>51</span> <span>//</span><span>Checks which of the smaller child to compare with the parent</span> <span>52</span> <span>if</span> (<span>$c</span>+1 <= <span>$this</span>->n && <span>$this</span>->elements[<span>$c</span>+1] < <span>$this</span>->elements[<span>$c</span><span>]) </span><span>53</span> <span>$c</span>++<span>; </span><span>54</span> <span>if</span> (<span>$this</span>->elements[<span>$i</span>] < <span>$this</span>->elements[<span>$c</span><span>]) </span><span>55</span> <span>break</span><span>; </span><span>56</span> <span>$this</span>->swap(<span>$c</span>, <span>$i</span><span>); </span><span>57</span> <span> } </span><span>58</span> <span> } </span><span>59</span> <span>60</span> <span>} </span><span>61</span> <span>62</span> <span>function</span> heapSort(<span>$array</span><span>){ </span><span>63</span> <span>$heap</span>=<span>new</span><span> MinHeap(); </span><span>64</span> <span>foreach</span>(<span>$array</span> <span>as</span> <span>$val</span><span>){ </span><span>65</span> <span>$heap</span>->insert(<span>$val</span><span>); </span><span>66</span> <span>67</span> <span> } </span><span>68</span> <span>$arr</span>=<span>array</span><span>(); </span><span>69</span> <span>while</span>(!<span>$heap</span>-><span>isEmpty()){ </span><span>70</span> <span>$arr</span>[]=<span>$heap</span>-><span>extract</span><span>(); </span><span>71</span> <span> } </span><span>72</span> <span>return</span> <span>$arr</span><span>; </span><span>73</span> <span>} </span><span>74</span> <span>$array</span>=<span>array</span>(1,13,8,4,5<span>); </span><span>75</span> <span>$arr</span>=heapSort(<span>$array</span><span>); </span><span>76</span> <span>print_r</span>(<span>$arr</span>);