C++排序算法之插入排序

C++排序算法之插入排序 本文主要介绍了C++排序算法之插入排序的基本思想、算法实现和时间复杂度分析。插入排序是一种简单的排序算法，通过将未排序的数据元素按大小顺序插入到已排好序数据序列中实现排序。 基本思想 插入排序的基本思想是将未排序的数据元素按大小顺序插入到已排好序数据序列中，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。例如，对2, 4, 3, 1, 6, 5进行插入排序。进行排序前，默认2是有序的，为有序区，而4, 3, 1, 6, 5是无序的，为无序区。将这五个无序的数按从小到大的顺序插入到有序区。 算法实现 插入排序的算法实现可以通过以下C++代码实现： ```c #include<iostream> using namespace std; void insertion_sort(int a[], int len){ int i, j, temp; for (i = 1; i < len; i++) { temp = a[i]; for(j = i; j > 0 && temp < a[j-1]; j--) { a[j] = a[j-1]; } a[j] = temp; } } int main(){ int a[] = {2, 4, 3, 1, 6, 5}; insertion_sort(a, 6); for (int i = 0; i < 6; i++) { cout << a[i] << " "; } return 0; } ``` 时间复杂度分析 插入排序的时间复杂度分析可以分为最好情况和最坏情况讨论。 (1). 最好的情况：最好的情况就是待排序的数据已经排好序了，这时只需要进行（n-1)次比较操作。 (2). 最坏的情况：最坏的情况就是待排序的数据序列是逆序的。此时需要进行的比较次数为n(n-1)/2次，赋值操作是比较操作的次数n(n-1)/2+(n-1）次。平均来说插入排序算法的时间复杂度为O(n^2）。 插入排序是一种简单且易于实现的排序算法，但是它不适合对于数据量比较大的排序应用。