一.冒泡排序

1.排序的基本概念

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

常用的排序例子：

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,4,2,6,3,9};

2.冒泡排序基本原理

两两相邻，不停比较，不停交换，比较n轮

8  7  1  5  4  2  6  3  9

8 > 7 （交换）

8 > 1（交换）

8 > 5（交换）

8 > 4（交换）

8 > 2（交换）

8 > 6（交换）

8 > 3（交换）

8 < 9（不换）

以此类推，接下来是让7和1比较

3.代码实现

（1）第一步：两两比较

int[] arr = new int[]{8,7,1,5,4,2,6,3,9};
//第一步:如何比较数组中的两两相邻的数
//第n个数和第n+1个数  比较
for(int n = 0;n < arr.Length - 1; n++)
{
    if(arr[n] > arr[n + 1])
    {
        
    }
}

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

（2）第二步：交换位置

int[] arr = new int[]{8,7,1,5,4,2,6,3,9};
//第一步:如何比较数组中的两两相邻的数
//第n个数和第n+1个数  比较
for(int n = 0;n < arr.Length - 1; n++)
{
    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.Write(arr[i]+"  ");
}

（3）第三步：交换m轮次

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

//第三步:如何换m轮
for(int m = 0;m < arr.Length; m++)
{
    //第一步:如何比较数组中的两两相邻的数
    //第n个数和第n+1个数  比较
    for(int n = 0;n < arr.Length - 1; n++)
    {
        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.Write(arr[i]+"  ");
}

（4）第四步：优化

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


//第四步:优化
//确认了位置的数字,不用参与比较了
//第三步:如何换m轮
for(int m = 0;m < arr.Length; m++)
{
    //第一步:如何比较数组中的两两相邻的数
    //第n个数和第n+1个数  比较
    for(int n = 0;n < arr.Length - 1 - m; n++)
    {
        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.Write(arr[i]+"  ");
}

（5）特殊情况优化

提前完成排序

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

//特殊情况优化(提前完成排序)
bool isSort = false;

//第四步:优化
//确认了位置的数字,不用参与比较了
//第三步:如何换m轮
for(int m = 0;m < arr.Length; m++)
{
    //第一步:如何比较数组中的两两相邻的数
    //第n个数和第n+1个数  比较
    for(int n = 0;n < arr.Length - 1 - m; n++)
    {
        if(arr[n] > arr[n + 1])
        {
            //第二步:交换位置
            int temp = arr[n];
            arr[n] = arr[n+1];
            arr[n+1] = temp;
            isSort = true;
        }
    }
    //没有进行交换,说明序列已经完整排好,直接退出循环即可
    if(!isSort)
    {
        break;
    }
}

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

二.选择排序

1.选择排序的基本原理

8  7  1  5  4  2  6  3  9

新建中间商（索引值）、依次比较、找出极值（最大或者最小）、放入目标位置、比较n轮

新建一个索引值0，对应的数值为8，依次向后比较，发现9比8大，而9对应的索引值为8，那么就让数组中索引值为8和这个最大值的索引值交换（是一样的无需交换）

同理，新建一个索引值为0，对应的值为8，依次向后比较，一直比较到索引值为7都是索引值为0的数最大，那么让索引值为7的数和索引值为0的数互换位置，（即8和3换位置）

同理，再新建一个索引值为0，对应的值为3，依次向后比较，发现索引值为1的数最大，那么就把索引值为1的数和索引值为6的数进行交换位置，（即7和6换位置）

同理，再新建一个索引值为0，对应的值为3，依次向后比较，发现索引值为1的数最大，那么就把索引值为1的数和索引值为5的数进行交换位置，（即6和2换位置）

同理，再新建一个索引值为0，对应的值为3，依次向后比较，发现索引值为3的数最大，那么就把索引值为3的数和索引值为4的数进行交换位置，（即5和4换位置）

同理，再新建一个索引值为0，对应的值为3，依次向后比较，发现索引值为3的数最大，那么就把索引值为3的数和索引值为3的数进行交换位置，（位置相同无需交换）

同理，再新建一个索引值为0，对应的值为3，依次向后比较，发现索引值为0的数最大，那么就把索引值为0的数和索引值为2的数进行交换位置，（即3和1交换）

接下来同理

2.代码实现

（1）第一步：申明一个索引值

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

//第一步  申明一个索引值
int index = 0;

//遍历
for(int i = 0;i<arr.Length;i++)
{
    Console.Write(arr[i]+"  ");
}

（2）第二步：以此比较，找到极值（最大值）

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

//第一步  申明一个索引值
int index = 0;

//第二步
for(int n = 1;n < arr.Length;n++)
{   //找到极值(最大值)
    if(arr[index] < arr[n])
    {
        index = n;
    }
}

//遍历
for(int i = 0;i<arr.Length;i++)
{
    Console.Write(arr[i]+"  ");
}

（3）第三步：放入目标位置

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

//第一步  申明一个索引值
int index = 0;

//第二步  以此比较
for(int n = 1;n < arr.Length;n++)
{   //找到极值(最大值)
    if(arr[index] < arr[n])
    {
        index = n;
    }
}
//第三步  放入目标位置
int m = 0;
//Length - 1 - m
if(index ! = arr.Length - 1 - m)
{
    int temp = arr[index];
    arr[index] = arr[arr.Length - 1 - m];
    arr[arr.Length - 1- m] = temp;
}
//遍历
for(int i = 0;i<arr.Length;i++)
{
    Console.Write(arr[i]+"  ");
}

（4）第四步：循环m轮

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

//第四步 循环m轮
for(int m = 0;m < arr.Length;m++)
{
    //第一步  申明一个索引值
    int index = 0;

    //第二步  以此比较
    for(int n = 1;n < arr.Length;n++)
    {   //找到极值(最大值)
        if(arr[index] < arr[n])
        {
            index = n;
        }
    }
    //第三步  放入目标位置
    //Length - 1 - m
    if(index != arr.Length - 1 - m)
    {
        int temp = arr[index];
        arr[index] = arr[arr.Length - 1 - m];
        arr[arr.Length - 1- m] = temp;
    }
} 

//遍历
for(int i = 0;i<arr.Length;i++)
{
    Console.Write(arr[i]+"  ");
}

（5）优化

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

//第四步 循环m轮
for(int m = 0;m < arr.Length;m++)
{
    //第一步  申明一个索引值
    int index = 0;

    //第二步  以此比较
    for(int n = 1;n < arr.Length - m;n++)
    {   //找到极值(最大值)
        if(arr[index] < arr[n])
        {
            index = n;
        }
    }
    //第三步  放入目标位置
    //Length - 1 - m
    if(index != arr.Length - 1 - m)
    {
        int temp = arr[index];
        arr[index] = arr[arr.Length - 1 - m];
        arr[arr.Length - 1- m] = temp;
    }
} 

//遍历
for(int i = 0;i<arr.Length;i++)
{
    Console.Write(arr[i]+"  ");
}