首页 > > 网络编程 > 其它 >

算法_冒泡程序

2018-06-18 01:05:40来源：未知阅读 ()

这里的第一个算法，没什么可以说的，一定是从最经典的冒泡算法开始，会列出python版和c版

冒泡算法很简单，就是像冒泡一样，把小的，也可以理解成轻的，从下面浮出来

比如有个list = [3,2,5,4,1]，先用3和2比，2轻，2浮上去，3沉下去，3再和5比，3比较轻，位置不变，5和4比，4浮上来，5和1比，1浮上来

第一次比完，得到[2,3,4,1,5]，再进行第二次，第三次，直到把没有可以浮的了，就结束，通常这个算法的版本是嵌套循环，就是for for，好像掉进这个圈出不来了，其实不用全部比一遍，如果list初始就是[2,1,3,4,5]，其实只要第一次就可以得到结果了，后面不是无用功么

好了，闲话不多，上代码，边嗑瓜子，边喝茶，边看代码，人生一大幸事啊

伪代码

序列 = [3,2,5,4,1]
循环序列
  标记初始化，直到标记没有变化，就结束循环
  如果第一个>第二个
    第二个和第一个换位置
    标记值变化，记录有变化了
  回到头，重新循环

python版

#!/usr/bin/python
# coding: UTF-8

def bubble_sort(num_list):
  num_len = len(num_list)
  while True:
    n = 0
    '''range这里-1是因为下面的+1,如果不-1,下面+1后会报out of range错误,而且从算法来说最多查找len(list) - 1次,因此这个是没问题的'''
    for i in range(num_len-1):
      if num_list[i] > num_list[i+1]:
        num_list[i],num_list[i+1] = num_list[i+1],num_list[i] #交换位置
        n += 1
    if n == 0:
      break
  return num_list

if __name__ == '__main__':
  num_list = [3,2,5,4,1]
  print num_list
  num_list = bubble_sort(num_list)
  print num_list

c版

#include <stdio.h>

int main()
{
  int num[] = {3,2,5,4,1};
  int i,num_len1;
  num_len1 = sizeof(num)/4; //这个sizeof的结果是20，我也不知道咋算的，不是说一个数字占1bit$
  bubble_sort(num,num_len1);
  for(i=0; i<num_len1; i++)
  {
    printf("%d \n", num[i]);
  }
  return 0;
}

int bubble_sort(int num_list[],int num_len)
{
  int i;
  while(1)
  {
    int n = 0;
    for(i=0;i<(num_len-1);i++)
    {
      if(num_list[i] > num_list[i+1])
      {
        int temp = num_list[i];
        num_list[i] = num_list[i+1];
        num_list[i+1] = temp;
        n++;
      }
    }
    if(n == 0)
    {
      break;
    }
  }
  return 0;
}