冒泡排序的基本思路_冒泡排序法的基本思路

冒泡排序

基本冒泡排序：
就是将数组中的元素两两进行对比，比出大小，按顺序进行交换，没有比出则不进行任何操作。这个算法是比较简单暴力的，但是不推荐使用，因为这种算法是时间消耗最多，同时也做了很多无用功。

void BubbleSort_first(SqList* L) 
{
    for (int i = 1; i <= L->length; i++) 
    {     //Array[0]用作存储数组长度，所以从i = 1开始
        for (int j = 1; j <= L->length; j++) 
        {
            if (L->Array[i] > L->Array[j]) 
            {
                swap(L, i, j);	//交换L->Array[i]>L->Array[j]的位置
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

对于代码的解释好比下图：


是不是每层遍历都要把所有元素再次进行遍历，已经排好的位置的元素在接下来的几层遍历中又进行了无用的比较，所以说它的效率太低了，我们可以对它进行优化一下。

void BubbleSort_second(SqList* L) 
{
    for (int i = 1; i <= L->length; i++) 
    {   //Array[0]用作存储数组长度，所以从i = 1开始
        for (int j = L->length - 1; j >= i; j--) 
        {
            if (L->Array[j] > L->Array[j + 1]) 
            {
                swap(L, j, j+1);	//交换L->Array[i]>L->Array[j]的位置
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

可能有人对for(int j = L->length-1;j >= i;j++)产生疑问(指代的是小白，大佬请忽略