「数据结构与算法分析」数据结构与算法分析-C++描述第7章插入排序（insertionSort）

数据结构与算法分析

插入排序（insertionSort）：

插入排序是最简单的排序算法之一。插入排序由 (N-1) 趟排序组成，对于 p = 1 到 p = N - 1 ，插入排序保证从位置0到上的元素已经为有序状态。

行为描述：

算法描述：

在第趟时，将位置上的元素向左移动至前 p+1 个元素中适当的位置<整体前移再插入从而无需反复交换元素>

插入排序的性质：

插入排序的界： $\sum_{i=2}^{N} i = O(N^2)$

一些简单排序算法（冒泡排序、选择排序）的下界：

以数为成员的数组的逆序（inversion）是指具有 i < j 但 a[i]>a[j] 的序偶 (i,j) 。显然，一次交换两个不按顺序排列的相邻元素消除一个逆序，而一个排过序的数组没有逆序。因此插入排序的运行时间为 O(N+I) ，其中为原始数组中的逆序数。于是，若逆序数是 O(N) ，则插入排序以线性时间运行。

定理：个互异元素的数组的平均逆序数为 N(N-1)/4 【设正序和逆序的数量各占一半】

定理：通过交换相邻元素进行排序的任何算法平均需要 $\Omega (N^2)$ 时间

插入排序实例：

//insertionSort.cpp
#include<iOStream>
#include<vector>
#include<algorithm>

using namespace std;

template<class Compareable>
void inserationSort(vector<Compareable> &v){
	int j;
	//traverse the vector
	for(int p  = 1; p < v.size(); p++){
		Compareable temp = v[p];
		//find the proper location
		for(j = p; j > 0 && temp < v[j - 1]; j--){
			v[j] = v[j - 1];
		}
		//insert into proper location
		v[j] = temp;
	}
}

int main(){
	int arr[] = {81, 94, 11, 96, 12, 35, 17, 95, 28, 58, 41, 75, 15};
	int len = sizeof(arr) / sizeof(arr[0]);
	vector<int> v;
	for(int i = 0 ; i < len; i++){
		v.push_back(arr[i]);
	}
	
	cout << "******* the original data ***********" << endl;
	for(typename vector<int>::iterator itr = v.begin(); itr != v.end(); ++itr){
		cout << *itr << " ";
	}
	cout << endl;
	
	cout << "******* the sorted data ***********" << endl;
	inserationSort(v);
	for(typename vector<int>::iterator itr = v.begin(); itr != v.end(); ++itr){
		cout << *itr << " ";
	}
	cout << endl;
	
	cout << " done ." << endl;
	return 0;
}

practice makes perfect ！

文章最后发布于: 2019-04-13 16:10:54

数据结构与算法分析-C++描述第7章插入排序（insertionSort）