冒泡排序知识点

排序的基本概念

排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录调整为“有序”的记录序列。

常用的排序例子

8 7 1 5 4 2 6 3 9

把上面的这个无序序列变为有序（升序或者降序）序列的过程。

1 2 3 4 5 6 7 8 9（升序）

9 8 7 6 5 4 3 2 1（降序）

在程序中，序列一般存储在数组当中。

所以排序往往是对数组进行排序。

int[] arr = new int[] { 8, 7, 1, 5, 2, 6, 3, 9, };

把数组里面的内容变为有序的。

排序图解

代码实现

第一步，如何比较数组中两两相邻的数

8, 7, 1, 5, 4, 2, 6, 3, 9

从头开始

//第n个数和第n+1个数比较
//for (int n = 0; n < arr.Length - 1; n++)
//{
//    //如果第n个数比第n+1个数大，它们就要交换结果
//    if (arr[n] > arr[n + 1])
//    {
//        //第二步，交换位置
//        //中间商不赚差价
//        int temp = arr[n];
//        arr[n] = arr[n + 1];
//        arr[n + 1] = temp;
//    }
//}
//第三步，如何交换n轮呢？
for (int m = 0; m < arr.Length - 1; m++)
{
    //进一次循环，就需要比较一轮
    for (int n = 0; n < arr.Length - 1; n++)
    {
        //如果第n个数比第n+1个数大，它们就要交换结果
        if (arr[n] > arr[n + 1])
        {
            //第二步，交换位置
            //中间商不赚差价
            int temp = arr[n];
            arr[n] = arr[n + 1];
            arr[n + 1] = temp;
        }
    }
}

for (int i = 0; i < arr.Length; i++)
{
    Console.WriteLine(arr[i]);
}

//第四步 优化
//1.确定位置的数字，不用比较了
//确定了一轮后，极值（最大或者最小）已经放到了对应的位置（往后放）
//所以每完成n轮，后面位置的数就不用再参与比较了
for (int m = 0; m < arr.Length - 1; m++)
{
    //进一次循环，就需要比较一轮
    for (int n = 0; n < arr.Length - 1 - m; n++)
    {
        //如果第n个数比第n+1个数大，它们就要交换结果
        if (arr[n] > arr[n + 1])
        {
            //第二步，交换位置
            //中间商不赚差价
            int temp = arr[n];
            arr[n] = arr[n + 1];
            arr[n + 1] = temp;
        }
    }
}

for (int i = 0; i < arr.Length; i++)
{
    Console.WriteLine(arr[i]);
}

特殊情况的优化

//外面声明一个标识来表示，该轮是否进行了交换
bool isShort = false;
for (int m = 0; m < arr.Length - 1; m++)
{
    //每一轮开始时，默认没有进行过交换
    isShort = false;
    //进一次循环，就需要比较一轮
    for (int n = 0; n < arr.Length - 1 - m; n++)
    {
        //如果第n个数比第n+1个数大，它们就要交换结果
        if (arr[n] > arr[n + 1])
        {
            isShort = true;
            //第二步，交换位置
            //中间商不赚差价
            int temp = arr[n];
            arr[n] = arr[n + 1];
            arr[n + 1] = temp;
        }
    }
    //当一轮结束后，如果isShort这个标识还是false
    //那就意味着，已经是最终的荀烈了，不需要再判断交换了
    if (!isShort)
    {
        break;
    }
}

for (int i = 0; i < arr.Length; i++)
{
    Console.WriteLine(arr[i]);
}