【排序算法】冒泡、选择、插入排序算法比较

冒泡排序

思路：
1. 有序比较两个元素，将较大的元素放到数组末尾。
2. 循环比较到最后一个元素，此时，这一轮比较出来最大的数就在数组末尾。
3. 重复上述步骤，直到没有需要比较的元素。

代码：

public int[] BubbleSort(int[] array)
    {
        for (int i = 1; i < array.Length; i++)
        {
            bool _change = false;
            for (int j = 0; j < array.Length - i; j++)
            {
                if (array[j] > array[j + 1])
                {
                    int _num = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = _num;
                    _change = true;
                }
            }
            if (!_change)
            {
                break;
            }
        }
        return array;
    }

性能分析：
时间复杂度是 O(N²)，假设数据是随机的，平均交换次数为 N²/4。如果初始数据是逆序的，那么每次比较都要交换位置，交换次数为 N²。

选择排序

思路：
1. 从所有元素中选出最小的元素，将最小的元素放在数组第一位。
2. 从余下的元素中找出最小元素，放在数组第二位。
3. 循环选择到排序结束。

代码：

public int[] ChoiceSort(int[] array)
    {
        for (int i = 0; i < array.Length - 1; i++)
        {
            int _min = i;
            for (int j = i + 1; j < array.Length; j++)
            {
                if (array[j] < array[_min])//查找最小值的index
                {
                    _min = j;
                }
            }
            if (i != _min)//替换最小值
            {
                int _temp = array[i];
                array[i] = array[_min];
                array[_min] = _temp;
            }
        }
        return array;
    }

性能分析：
时间复杂度是 O(N²)，至多进行了N次交换。

插入排序

思路：
1. 将数组分成已排序和未排序两份。
2. 循环待排序部分，将取出的元素插入到前面已经排好的部分中去。

代码：

 public int[] InsertSort(int[] array)
    {
        int j;
        for (int i = 1; i < array.Length; i++)
        {
            int _temp = array[i];
            j = i;
            while (j > 0 && _temp < array[j - 1])
            {
                array[j] = array[j - 1];
                j--;
            }
            array[j] = _temp;
        }
        return array;
    }

性能分析：
时间复杂度是 O(N²)，赋值的次数大致等于比较的次数，但是一次赋值与一次交换的时间耗时不同，所以相对于随机数据，插入排序比冒泡快一倍，比选择排序略快。

总结：

- 冒泡、选择、插入时间复杂度都是 O(N²)。一般不会选择冒泡排序，虽然冒泡排序书写是最简单的，但是平均性能是没有选择排序和插入排序好的。
- 选择排序把交换次数降低到最低，但是比较次数还是挺大的。当数据量小，并且交换数据相对于比较数据更加耗时的情况下，可以应用选择排序。
- 在大多数情况下，假设数据量比较小或基本有序时，插入排序是三种算法中最好的选择。