【学习笔记】在C语言中对一个数组进行冒泡排序

问题描述：假如现在有一个数组arr[ ]，里面有{ 3, 2, 1, 4, 7, 6, 5,9, 8 }九个元素，现要将其按升序排列。要求用冒泡排序实现。

问题分析：

• 有10个元素，那么要进行9趟冒泡排序，每趟把一个元素排到最后；
  • 第一趟中，10个元素，那么要相互比较9对，
  • 第二趟中，9个元素，那么要相互比较8对，
    之所以元素较第一趟少了一个，是因为最大的那个元素已经去到最后边了，占了一个位置，就不用再那它去比较。
  • 第三趟中，8个元素，那么要相互比较7对，
  • ...
• 因此首先要做的是确定冒泡的趟数，然后针对某一趟内的元素进行排序。

  ---

  代码实现：（首先自定义了函数bubble_sort）

  #include 
  //冒泡排序
  
  void bubble_sort(int arr[], int sz)
  {
      int i = 0;
      int j = 0;
      for (i = 0; i < sz - 1; i++)   //决定冒泡排序的趟数
      {
          for (j = 0; j < sz - 1-i; j++)  //对每一趟进行处理（排序）
          {
              if (arr[j] > arr[j + 1])
              {
                  int tmp = arr[j];
                  arr[j] = arr[j + 1];
                  arr[j + 1] = tmp;
              }
          }
      }
  }
  
  int main()
  {
      int arr[] = { 3, 2, 1, 4, 7, 6, 5,9, 8 };
      int sz = sizeof(arr) / sizeof(arr[0]);
      bubble_sort(arr, sz); // 冒泡排序函数。arr是数组，我们对数组arr进行传参，实际上传递过去的是数组arr首元素的地址 &arr[0]。
      int c = 0;
      for (c = 0; c < sz; c++)
      {
          printf("%d ", arr[c]);
      }
      return 0;
  }
  

  ---

  代码更上层楼：（因为前述代码做了“无用功”。 其实​可以让该算法“智能”一点，即发现某一趟                            的元素已经有序的时候，就不再噗嗤噗嗤地两两比较排序了。）

  #include 
  
  //冒泡排序(优化）
  void bubble_sort(int arr[], int sz)
  {
  	int i = 0;
  	int j = 0;
  	for (i = 0; i < sz - 1; i++)   //决定冒泡排序的趟数
  	{
  		int flag = 1; // 假设这一趟要排序的数据已经有序。（所以设下flag作为一个“间谍”）
  		for (j = 0; j < sz - 1 - i; j++)  //对每一趟进行处理（排序）
  		{
  			if (arr[j] > arr[j + 1])
  			{
  				int tmp = arr[j];
  				arr[j] = arr[j + 1];
  				arr[j + 1] = tmp;
  				flag = 0;  //如果程序运行到这，说明有arr[j] > arr[j + 1]的出现，因此通过改变flag的值来传递“信号”。
  			}
  		}
  		if (flag == 1)  //点睛之笔。这样就能避免代码作“无用功。
  			break;
  	}
  }
  
  int main()
  {
  	int arr[] = {9,1,2,3,4,5,6,7,8};  //我更改了要进行排序的那个数组。目的是为了使代码的优化更直观。
  	int sz = sizeof(arr) / sizeof(arr[0]);
  	bubble_sort(arr, sz); // 冒泡排序函数。arr是数组，我们对数组arr进行传参，实际上传递过去的是数组arr首元素的地址 &arr[0]。
  	int c = 0;
  	for (c = 0; c < sz; c++)
  	{
  		printf("%d ", arr[c]);
  	}
  	return 0;
  }