今天刷OJ又一次遇到了排序问题,于是把冒泡排序再回顾一遍。

原题如下:

原题

void swap(int *a, int *b);

int main()
{
  int n; //表示n个数
  while(scanf("%d", &n) && n) //输入n,并且n为0时停止
  {
    int num[2000] = { 0 };   //题目要求
    for (int i = 0; i < n; ++i)
    {
      scanf("%d", &num[i]);        //输入n个数到num数组去
    }
    for (int i = 0; i < n - 1; ++i)    //冒泡排序 
    {
      for (int j = 0; j < n - 1- i; ++j)
      {
        if (num[j] > num[j + 1])
        {
          swap(&num[j], &num[j + 1]);
        }
      }

    }
    for (int i = 0; i < n-1; i++)
    {
      printf("%d\n", num[i]);
    }
    printf("%d\n\n", num[n - 1]);

  }

  return 0;
}

void swap(int *a, int *b)  //此函数用于交换两个值
{
  int t;
  t = *a;
  *a = *b;
  *b = t;
}

稍微分析下为什么是n-1?

假如有5个数,分别为 5 6 4 2 1,冒泡排序的比较方式:

第一步:5与6比较大小,5小于6,不交换,此时仍为5 6 4 2 1

第二步:6与4比较大小,6大于4,交换,此时为5 4 6 2 1

第三步:6与2比较大小,6大于4,交换,此时为5 4 2 6 1

第四步:6与1比较大小,6大于1,交换,此时为5 4 2 1 6

通过这四部,我们找到了最大的一项,并且把它放在了数组的最后。

并且我们也知道了n个数第次需要比较n-1次找到最大的数,那么第二次循环找到第二个数就需要比较n-2次(最大的不要比较了,因为已经找出了)……

最后再输出即可。

最后修改:2019 年 02 月 26 日 07 : 14 PM
如果觉得我的文章对你有用,请随意赞赏