简单排序 插入排序 C语言入门

欢迎关注笔者，你的支持是持续更博的最大动力

问题描述

给n个数按从小到大排序 （插入排序）

思路

插入排序：把无序部分元素插入有序部分
1.用无序部分的第1个元素，和前面有序部分每一个元素比较；
2.如果比前面有序部分某元素小，则插到那个元素前面；
…
直到最后一个元素排完。


关于怎么插入：

代码

代码思路

因为位置1是第一个无序元素 (位置0不用排，有序），所以从位置1开始排序：

• 和前面有序部分每一个元素比较；
• 如果比前面有序部分位置 j 元素小，则插到那个元素前面：
  – 把这个无序元素放到临时位，空出位置
  – 把位置 j 往后的有序元素，倒着依次往后挪一位
  – 无序元素插入位置 j
  

void InsertionSort(int a[], int size){           //a[]:要排序的数组，size:数组大小，函数返回值：无，类型写void
    for (int i = 1; i < size; ++i) {             //无序部分：i~(size-1)
        for (int j = 0; j < i; ++j) {            //有序部分：0~(i-1)
            if (a[j] > a[i]){                    //如果位置j的有序元素比无序元素i大，i元素就要排到j对应的元素前面，且因为有序，i不用再和j后面的有序部分比较了，它们一定比i元素大
                int tmp = a[i];                  //先把原i位置无序元素放到临时位
                for (int k = i; k > j; --k) {   //再把从j到i-1的有序元素倒着依次往后挪一位：如起始位置i-1的元素挪到i，即a[i]=a[i-1]
                    a[k] = a[k-1];
                }
                a[j] = tmp;                      //挪完后，临时位的无序元素插入有序部分j位置
                break;                           //j后面的有序部分一定比a[i]大，就不用比较了
            }
        }
    }
}
//用选择排序函数InsertionSort给 3 2 1 5 排序， 输出： 1 2 3 5
int main(){
    int a[] = {3,2,1,5};
    InsertionSort(a, 4);
    for (int i = 0; i < 4; ++ i) {
        cout << a[i] << " ";    
    }
}

其他

日常vlog: 点这里去B站～