排序小结 sort

排序小结

排序算法是基础之基础。在这里小结一下。方便自己查阅和学习。

1.冒泡排序(BubbleSort)

思想：比较相邻的两个元素，如果前面的元素大于后面的元素，交换之。

思路：采用双层循环。外循环控制要处理多少趟。里面循环用来做元素的交换操作。注意上下界。

稳定性：稳定

时间复杂度：O(n2)

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

<code>void</code> <code>bubbleSort(</code><code>int</code> <code>a[], </code><code>int</code> <code>size)</code>

<code>{</code>

<code>    </code><code>int</code> <code>tmp;</code>

<code>    </code><code>for</code> <code>(</code><code>int</code> <code>i = 0; i &lt; size; i++)</code>

<code>    </code><code>{   </code><code>//每一趟都会把最大的元素放入最右边的位置</code>

<code>        </code><code>//最右边的位置会一点点往左移动</code>

<code>        </code><code>for</code> <code>(</code><code>int</code> <code>j = 0; j &lt; size - i - 1; j++)</code>

<code>        </code><code>{</code>

<code>            </code><code>if</code> <code>(a[j] &gt; a[j + 1])</code>

<code>            </code><code>{</code>

<code>                </code><code>tmp = a[j];</code>

<code>                </code><code>a[j] = a[j + 1];</code>

<code>                </code><code>a[j + 1] = tmp;</code>

<code>            </code><code>}</code>

<code>        </code><code>}</code>

<code>    </code><code>}</code>

<code>}</code>

2.快速排序(quickSort)

思想：找到第一个元素的最终位置，然后对数组进行分割，对左边的进行快排，对右边的进行快排。

思路：采用递归，需要一个辅助函数findPos()来找到某一个元素的最终位置。

稳定性：不稳定

时间复杂度：有时O(nlogn),最坏情况是已经排好序，这样时间复杂度为O(n2)

伪算法

/*

 * 快速排序（伪算法） 2016-08-14 11:01:34

 * 1.先找到第一个元素的最终位置

 * 2.对第一个元素的最终位置之前的元素，进行快速排序。

 * 3.对第一个元素的最终位置之后的元素，进行快速排序。

 *

*/

18

19

20

21

22

23

24

25

26

27

<code>int</code> <code>findPos(</code><code>int</code> <code>a[],</code><code>int</code> <code>low,</code><code>int</code> <code>high)</code>

<code>{  </code>

<code>    </code><code>int</code> <code>val = a[low];</code>

<code>    </code><code>while</code><code>(low &lt; high)</code>

<code>    </code><code>{</code>

<code>        </code><code>//因为val取的是最前面的值，所以先从后往前遍历比较</code>

<code>        </code><code>while</code><code>(low &lt; high &amp;&amp; a[high] &gt;= val)</code>

<code>            </code><code>high--;</code>

<code>        </code><code>a[low] = a[high];</code><code>//将后面较小值赋值给前面已经做好备份的位置上</code>

<code>        </code><code>//然后从前往后遍历比较</code>

<code>        </code><code>while</code><code>(low &lt; high &amp;&amp; a[low] &lt;= val)</code>

<code>            </code><code>low++;</code>

<code>        </code><code>a[high] = a[low];</code><code>//将前面较大值赋值给后面已经做好备份的位置上</code>

<code>    </code><code>a[low] = val;</code>

<code>    </code><code>return</code> <code>low;</code>

<code>void</code> <code>quickSort(</code><code>int</code> <code>a[],</code><code>int</code> <code>low,</code><code>int</code> <code>high)</code>

<code>    </code><code>if</code><code>(low &lt; high)</code>

<code>        </code><code>int</code> <code>pos = findPos(a,low,high);</code>

<code>        </code><code>quickSort(a,low,pos-1);</code>

<code>        </code><code>quickSort(a,pos+1,high);</code>

3.直接插入排序(insertSort)也叫选择插入排序

思想：将第i个元素插入到前面i-1个已排好序的记录中。直到所有的元素都排一次。

思路：见伪算法

* 插入排序（伪算法） 2016-08-14 12:23:09

* 1. 将相邻的两个元素比较，如果前面的数大于后面的数，则交换。

*    直到找到前面的数小于后面的，就把这个值插入到这个位置。

* 2. 循环1，直到所有的元素都有序排列。

*

<code>void</code> <code>insertSort(</code><code>int</code> <code>a[], </code><code>int</code> <code>size)</code>

<code>    </code><code>int</code> <code>i, j, tmp;</code>

<code>    </code><code>for</code> <code>(i = 0; i &lt; size; i++)</code>

<code>        </code><code>tmp = a[i];</code>

<code>        </code><code>for</code> <code>(j = i - 1; j &gt;= 0 &amp;&amp; a[j] &gt; tmp; j--)</code>

<code>            </code><code>a[j+1] = a[j];</code>

<code>        </code><code>a[j + 1] = tmp;</code>

4.选择排序(selectSort)

思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在待序列的起始位置。 

* 选择排序（伪算法） 2016-08-14 13:08:50

* 1. 工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在待序列的起始位置。 

* 2. 循环1，直到全部待排序的数据元素排完。

<code>void</code> <code>selectSort(</code><code>int</code> <code>a[], </code><code>int</code> <code>size)</code>

<code>    </code><code>int</code> <code>currentSmallIndex;</code><code>//记录待排序队列中最小元素的下标</code>

<code>    </code><code>int</code> <code>tmp;</code><code>//记录最小元素的大小</code>

<code>        </code><code>currentSmallIndex = i;</code>

<code>        </code><code>for</code> <code>(</code><code>int</code> <code>j = i + 1; j &lt; size; j++)</code>

<code>            </code><code>if</code> <code>(a[j] &lt; tmp)</code>

<code>                </code><code>currentSmallIndex = j;</code>

<code>        </code><code>a[currentSmallIndex] = a[i];</code>

<code>        </code><code>a[i] = tmp;</code>

5.归并排序(mergeSort)

思想：将数组递归分成2半，知道数组的长度为1，然后将分成2半的数组合并。

思路：需要使用辅助函数merge()来合并

1.将数组分成左右两半

2.递归1，直道只剩1个元素的时候，然后合并。

 */

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

<code>void</code> <code>merge(</code><code>int</code> <code>a[], </code><code>int</code> <code>start, </code><code>int</code> <code>end)</code>

<code>    </code><code>int</code> <code>mid = (start + end) / 2;</code>

<code>    </code><code>int</code> <code>left, right;</code>

<code>    </code><code>int</code> <code>* temp = </code><code>new</code> <code>int</code><code>[end - start + 1];</code>

<code>    </code><code>int</code> <code>k = 0;</code><code>//临时数组的下标</code>

<code>    </code><code>left = start;</code>

<code>    </code><code>right = mid + 1;</code>

<code>    </code><code>while</code> <code>(left &lt;= mid &amp;&amp; right &lt;= end)</code>

<code>        </code><code>while</code> <code>((left &lt;= mid &amp;&amp; right &lt;= end) &amp;&amp; (a[left] &lt; a[right]))</code>

<code>            </code><code>temp[k++] = a[left++];</code>

<code>        </code><code>while</code> <code>((left &lt;= mid &amp;&amp; right &lt;= end) &amp;&amp; (a[right] &lt; a[left]))</code>

<code>            </code><code>temp[k++] = a[right++];</code>

<code>    </code><code>while</code> <code>(left &lt;= mid)</code>

<code>        </code><code>temp[k++] = a[left++];</code>

<code>    </code><code>while</code> <code>(right &lt;= end)</code>

<code>        </code><code>temp[k++] = a[right++];</code>

<code>    </code><code>//将临时数组中的元素，找到原数组的位置，按位赋值过去。</code>

<code>    </code><code>//这里需要注意原数组的起始位置是start，而不是0</code>

<code>    </code><code>for</code> <code>(</code><code>int</code> <code>i = start, k = 0; i &lt;= end; i++, k++)</code>

<code>        </code><code>a[i] = temp[k];</code>

<code>    </code><code>delete</code><code>[] temp;</code>

<code>void</code> <code>mergeSort(</code><code>int</code> <code>a[], </code><code>int</code> <code>start, </code><code>int</code> <code>end)</code>

<code>    </code><code>if</code> <code>(start &lt; end)</code>

<code>        </code><code>int</code> <code>mid = (start + end) / 2;</code>

<code>        </code><code>mergeSort(a, start, mid); </code><code>//左数组合并排序</code>

<code>        </code><code>mergeSort(a, mid + 1, end); </code><code>//右数组合并排序</code>

<code>        </code><code>merge(a, start, end);     </code><code>//整体排序</code>

排序总结未完待续。

本文转自313119992 51CTO博客，原文链接:http://blog.51cto.com/qiaopeng688/1837802