插入排序和冒泡排序时间复杂度相同,但为什么更倾向于使用插入排序而不是冒泡排序？

排序算法有很多，主要按时间复杂度分为三大类

image

冒泡排序（Bubble Sort）

算法

  1. 比较相邻两个元素
  2. 不满足条件的，则将他们互换
  3. 一次冒泡，将第一个元素移动到应有的位置
  4. n次完成排序工作
  5. 如果一次冒泡中，没有数据变化，则说明所有数据已经有序

image

image

image

代码

void BubbleSort(int data[], int length)
{
    //BubbleSort
    for (int i = 0; i < length; i++) {
        bool ValueChanged = false;

        for (int j = 1; j < length - i; j++) {
        	//不符合条件，则互换
            if (data[j - 1] > data[j]) {
                int tmp = data[j];
                data[j] = data[j - 1];
                data[j - 1] = tmp;

                ValueChanged = true;
            }
        }

        //一次完整冒泡没有数据变化，说明已经是有序的了
        if (!ValueChanged) break;
    }
}

特性

  1. 原地排序
  2. 稳定排序
  3. 空间复杂度O(1)
  4. 时间复杂度O(n平方)
    image

插入排序（Insertion Sort）

算法

将未排序的数据插入到已经排序的区间中

代码

void InsertionSort(int data[], int length)
{
    for (int i = 1; i < length; i++) {
    	//缓存比较的数据，该位置在移动有序区间是会被覆盖
        int currentValue = data[i];
        int j = i;
        for (; j > 0; j--) {
        	//有序区间如果小于比较值，则移动
            if (currentValue < data[j - 1] ) {
                data[j] = data[j - 1];
            } else {
                break;
            }
        }
        data[j] = currentValue;
    }
}

image

image

特性

  1. 原地排序
  2. 稳定排序
  3. 空间复杂度O(1)
  4. 时间复杂度O(n平方)

选择排序（Selection Sort）

算法

从未排序的区间中选出最小的放到已排序的末尾

image

代码

void SelectSort(int data[], int length)
{
    for (int i = 0; i < length - 1; i++) {
        int MinIndex = i;
        //i之后为未排序的
        for (int j = i + 1; j < length; j++) {
            if (data[MinIndex] > data[j]) {
                MinIndex = j;
            }
        }
        //i为已排序空间末尾
        if (i != MinIndex) {
            int tmp = data[i];
            data[i] = data[MinIndex];
            data[MinIndex] = tmp;
        }
    }
}

特性

  1. 原地排序
  2. 不稳定排序
  3. 空间复杂度O(1)
  4. 时间复杂度O(n平方)

开篇解答

冒泡排序一次移动需要3次赋值，而插入排序只需要一次赋值

总结

image