胖子汪洋的博客

一只超级简单的喵星转世人

普通冒泡排序

| Comments

本文参考了的一些文章

冒泡排序
选择排序

关于冒泡

思想

  • 从数组的第一个元素开始，两两比较，大的往后放，经过n-1次比较，最大的放到了n-1位置。
  • 从数组的第一个元素开始，两两比较，大的往后放，经过n-2次比较，第二大的放在了n-2位置。
  • 以此类推

尼玛！！！这也不像冒泡啊

不知道有没有人也像我这么想过：乍一看，每一次都是将最大的放在了最后面（沉底），这怎么是冒泡！！！尼玛！！！ image

其实今天我才想明白，虽然每次都是将最大的放在最后，可是从另一方面来看，也就是说每一次都是将其余小的放在了上面，也就可以想成小的往上升，称之为冒泡排序。如果还是不行，可以看下面的流程，我们从更加形象的流程来描述冒泡排序的思想。

  • 从数组最后一个元素开始，将相邻的挨个比较，小的往前放，经过n-1次比较，最小的就放到了最前面。
  • 仍然从最后一个元素开始，经过n-2次比较，第二小的放在了第二位置。
  • 以此类推

写段python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

def bubbleSort(list):
  issorted = False
  
  for i in range(0,len(list)):
      issorted = True
      
      # 在这一趟的比较中，如果发现这一趟的数列已经成有序状态，那就不用排了，并且是整个数列也都算排完了
      for j in range(0, len(list) - i - 1):
          if list[j] > list[j+1]:
              temp = list[j]
              list[j] = list[j+1]
              list[j + 1] = temp
              issorted = False;
      print "sort ",i, " " , list
      if (issorted):
          break;
      
              
list = [7, 4, 1, 3, 9, 2, 8]
bubbleSort(list)

总结

  • 小的（轻的）逐渐上升到指定位置，从过程来看像冒泡（bubble sort）。
  • 每一次相邻比较数组都有可能会发现变化。

选择排序

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，比较时并不改变数组元素位置，至到一趟比较结束后，才将最小（最大）的元素与首元素（尾元素）交换位置

下面以排出由小到大的数组为例 以数组array[]为例，选择0位置为最小元素位置，用局部变量temp记住当前的index：0 * 用array[0]与其它位置元素比较，如果array[x]小于array[0]，temp = x，使用array[x]与剩下元素比较，如果array[y] < array[x], temp = y。直到全部比较完，此时的temp是最小元素的下村，将array[temp]与array[0]交换位置 * 用array[1]重复上面的步骤

什么是稳定的排序

通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下，如果Ai = Aj, 排序前Ai在Aj前，那么排序后Ai仍然在Aj前。 * 冒泡是稳定的 * 选择是不稳定的

Comments