首页 > 代码库 > 《数据结构与算法分析：C语言描述》复习——第六章“排序”——插入排序

《数据结构与算法分析：C语言描述》复习——第六章“排序”——插入排序

2024-07-08 12:27:03   225人阅读

2014.06.17 01:37

简介：

　　插入排序是最常用的O(n^2)级别的交换排序算法。之所以最常用，是因为它和选择排序、冒泡排序相比，有着自己的优势。

描述：

　　如果数组的前i - 1个元素已经排好序，你要将第i个元素插入到其中，使得前i个元素变得有序。为了找到应该插入的位置，我们从后向前扫描，直到找到合适的位置为止。扫描过程中还需要把每个检查的每个元素向后移动一位，以便给新元素腾出位置。如果你观察下面的代码，不难发现在数组已经“接近有序”的时候（也就是逆序数很小的时候），需要的“移动”操作就很少了。当数组完全有序时，插入排序的复杂度就降低到了O(n)。这中worst case和best case的明显效率差异，就是插入排序比选择排序好的原因。尽管他们理论上复杂度都是O(n^2)。

实现：

 1 // My implementation for insertion sort. 2 #include <iostream> 3 #include <vector> 4 using namespace std; 5  6 void insertionSort(vector<int> &v) 7 { 8     int i, j, n; 9     int val;10     11     n = (int)v.size();12     if (n <= 1) {13         return;14     }15     16     for (i = 1; i < n; ++i) {17         val = v[i];18         for (j = i - 1; j >= 0 && v[j] > val; --j) {19             v[j + 1] = v[j];20         }21         v[j + 1] = val;22     }23 }24 25 int main()26 {27     vector<int> v;28     int n, i;29     30     while (cin >> n && n > 0) {31         v.resize(n);32         for (i = 0; i < n; ++i) {33             cin >> v[i];34         }35         insertionSort(v);36         for (i = 0; i < n; ++i) {37             cout << v[i] << ‘ ‘;38         }39         cout << endl;40     }41     42     return 0;43 }

 


联系
我们