插入、冒泡、选择三种排序算法比较

先说结论：

• 插入排序和冒泡排序比较，就时间复杂度而言：最好、最坏以及平均时间复杂度一样，但是插入排序的数据移动相对于冒泡排序的数据交换，赋值语句更少，所以优先选择插入排序；
• 选择排序最坏的时间复杂度是O(n^2)，相对于插入排序或冒泡排序的O(n)已经低人一等；而且选择排序是非稳定排序，效果不理想；

---

三种算法代码实现

插入排序算法代码：(1-i模式)

//实现一
void insert_sort(int arr[], int size) {
    int i, j, tmp;
    for(i=1; i<size; i++) {
        tmp = arr[i];
        for(j=i; j>0 && arr[j-1]>tmp; j--) {
            arr[j] = arr[j-1]; //数据移动，一行代码
        }
        arr[j] = tmp; //找到j的位置，插入进去      
    }
}

//实现二
void insert_sort(int arr[], int size) {
    int i, j, tmp;
    for(i=1; i<size; i++) {
        tmp = arr[i];
        for(j=i; j>0; j--) {
            if(arr[j-1]>tmp) {
                arr[j] = arr[j-1]; //数据移动，一行代码
            } else {
                break;
            }
        }
        arr[j] = tmp; //找到j的位置，插入进去      
    }
}

冒泡排序算法代码：(0-0模式)

//实现一
void bubble_sort(int arr[], int size) {
    int i, j, tmp;
    for(i=0; i<size-1; i++) {
        for(j=0; j<size-1-i; j++) {  //数据交换三行代码比较多，耗时长
              if(arr[j] > arr[j+1]) {
                    tmp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = tmp;
              }  
        }
}
//实现二：加flag 优化
void bubble_sort(int arr[], int size) {
    int i, j, tmp;
    
    for(i=0; i<size-1; i++) {
        int exchangeFlag = 0;
        for(j=0; j<size-1-i; j++) {
              if(arr[j] > arr[j+1]) {  // 数据交换三行代码比较多，耗时长
                    tmp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = tmp;
                    exchangeFlag = 1; // 表示有数据交换
              }  
        }
        if (0 == exchangeFlag) break; // 没有数据交换，已经排好序了，提前退出
    }
}

选择排序代码：(0-i+1模式)

void select_sort(int arr[], int size) {
      int i, j, min;
      for(i=0; i<size-1; i++) {
          min = arr[i];
          for(j=i+1; j<size; j++) {
              if(arr[j] < min) {
                  min = arr[j];
                  arr[j] = arr[i];
                  arr[i] = min;
              }
          }
      }
}

---

其他补充

算法评价标准

• 排序算法的执行效率

时间复杂度：最好情况、最坏情况、平均情况时间复杂度；
时间复杂度的系数、常数 、低阶：实际情况小规模数据，不涉及到无穷大情况；
比较次数和交换（或移动）次数；

• 排序算法的内存消耗

空间复杂度；
原地排序（Sorted in place）。原地排序算法，就是特指空间复杂度是 O(1) 的排序算法； 是否是原地排序

• 排序算法的稳定性

如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

---

引用：

11 | 排序（上）：为什么插入排序比冒泡排序更受欢迎？