c#冒泡排序、插入排序、选择排序

1、冒泡排序

只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。

        /// <summary>
        /// 冒泡排序
        /// </summary>
        /// <param name="a"></param>
        public static void BubbleSort(int[] a)
        {
            int n = a.Length;
            for (int i = 0; i < n; i++)
            {
                bool flag = false;//提前退出冒泡循环的标志位
                for (int j = 0; j < n - i - 1; j++)
                {
                    if (a[j] > a[j + 1])
                    {
                        int temp = a[j];
                        a[j] = a[j + 1];
                        a[j + 1] = temp;
                        flag = true;//表示有数据交换
                    }
                }
                if (!flag)
                {
                    break;//没有数据交换，提前退出
                }
            }
        }

image image

2、插入排序

首先，我们将数组中的数据分为两个区间， 已排序区间和 未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

public static void InsertionSort2(int[] arr)
        {
            for (int i = 1; i < arr.Length; i++)
            {
                int insertVal = arr[i];//要插入的值
                int insertIndex = i - 1;
                //查找插入的位置
                while (insertIndex >= 0 && insertVal < arr[insertIndex])
                {
                    arr[insertIndex + 1] = arr[insertIndex];
                    insertIndex--;
                }
                //插入数据
                arr[insertIndex + 1] = insertVal;
            }
        }

image

3、选择排序

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

public static void SelectSort(int[] arr)
        { for (int i = 0; i < arr.Length - 1; i++)
            { int minVal = arr[i];  //先假设最小值
                int minIndex = i;     //先假设最小值的下标 //找出这一趟最小的数值并记录下它的下标
                for (int j = i + 1; j < arr.Length; j++)
                { if (minVal > arr[j])
                    {
                        minVal = arr[j];
                        minIndex = j;
                    }
                } //最后把最小的数与已排序的末尾交换
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }

image

总结

冒泡排序、插入排序、选择排序这三种排序算法，它们的时间复杂度都是 O(n 2 ) ，比较高，适合小规模数据的排序。从代码实现上来看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要 3 个赋值操作，而插入排序只需要 1 个，插入排序比冒泡排序更受欢迎。

image