浅谈冒泡排序的小优化

冒泡排序作为初学者最常用的排序算法之一，大家应该闭着眼都能敲出来，但是如果在数据较大的情况下，冒泡排序的效率并不高，因为它的时间复杂度是O(n^2)，但是在我们又不会其它排序算法的前提下，怎么尽量给它优化一下呢，这就是今天要讲的内容。

首先先看普通代码

// 冒泡排序
void bubbleSort(int arr[], int n)
{
  for (int i = 0; i < n - 1; i++)
  {
    for (int j = 0; j < n - 1 - i; j++)
    {
      if (arr[j] > arr[j + 1])
      {
        int t = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = t;
      }
    }
  }
}
// 冒泡排序
void bubbleSort(int arr[], int n)
{
  for (int i = 0; i < n - 1; i++)
  {

    for (int j = 0; j < n - 1 - i; j++)
    {
      if (arr[j] > arr[j + 1])
      {

        int t = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = t;
      }
    }
  }
}
// 冒泡排序
void bubbleSort(int arr[], int n)
{
	for (int i = 0; i < n - 1; i++)
	{

		for (int j = 0; j < n - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{

				int t = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = t;
			}
		}
	}
}

它要一个个比较大小，然后从后面排到第一个，但是如果有几个数组是这样子的：

arr[10]={1,2,3,4,5,6,7,8,10,9};
brr[10]={1,2,3,4,5,6,8,7,10,9};
arr[10]={1,2,3,4,5,6,7,8,10,9};
brr[10]={1,2,3,4,5,6,8,7,10,9};
arr[10]={1,2,3,4,5,6,7,8,10,9};
brr[10]={1,2,3,4,5,6,8,7,10,9};

那是不是除了后面的那几个，其他的都排序好了呀，但是普通的冒泡排序还会继续比较前面的然后排序，这是不是使程序的效率更不高了，那有没有什么可以优化的地方呢，让我们排完后面的就结束排序呢？当然有的，请看代码：

// 冒泡排序
void bubbleSort(int arr[], int n)
{
  for (int i = 0; i < n - 1; i++)
  {
    int flag = 1;  //定义一个标志
    for (int j = 0; j < n - 1 - i; j++)
    {
      if (arr[j] > arr[j + 1])
      {
        flag = 0;  //如果发生则更改标志
        int t = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = t;
      }
    }
    if (flag == 1)    //如果没有发生排序则结束排序
      break;
  }
}
// 冒泡排序
void bubbleSort(int arr[], int n)
{
  for (int i = 0; i < n - 1; i++)
  {
    int flag = 1;  //定义一个标志
    for (int j = 0; j < n - 1 - i; j++)
    {
      if (arr[j] > arr[j + 1])
      {
        flag = 0;  //如果发生则更改标志
        int t = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = t;
      }
    }
    if (flag == 1)    //如果没有发生排序则结束排序
      break;
  }
}
// 冒泡排序
void bubbleSort(int arr[], int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int flag = 1;  //定义一个标志
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				flag = 0;  //如果发生则更改标志
				int t = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = t;
			}
		}
		if (flag == 1)    //如果没有发生排序则结束排序
			break;
	}
}

相比于普通的冒泡多了一个标志判断，如果前面的已经排好了，并且后面的也排好了，那么整个数组是不是就不会发生交换了呀，所以我们在这个时候就可以轻松愉快结束排序啦~