插入排序的另一种写法

一般的插入排序方法想必大家都写过，基础好的几分钟就可以写出来了，基础差一点的调一调也就出来了。

下面是一般通用的插入排序算法：

#include<iostream>
using namespace std;
const int SIZE = 10;

int arrs[SIZE];

//打印排序后的数组
void printArr(){
	for(int i = 0; i < SIZE; i ++){
		cout<<arrs[i]<<(i==SIZE-1?"":" ");
	}
	cout<<endl;
}

//初始化数组
void initArr(){
	for(int i = 0; i < SIZE; i++){
		arrs[i] = rand()%50; //产生随机数
	}
	printArr();
}

//排序函数
void insertSort(){
	int temp,i,j;
	for(i = 1; i < SIZE; i ++){
		temp = arrs[i];
		j = i - 1;
		if(temp < arrs[j]){
			for(; temp < arrs[j]; j --){
				arrs[j+1] = arrs[j];
			}
			arrs[j+1] = temp;
		}
	}
}


int main()
{
	initArr();
	insertSort();
	printArr();
	return 0;
}

 

其实插入排序还有其它几种算法：二分插入排序 、双路径插入排序。虽然写法不同，但时间复杂度是一样的。

下面就讲 二分插入排序。思想很简单，就是在插入排序时应用二分法来把当前元素和已经排好序的比较。

#include<iostream>
using namespace std;

const int SIZE = 10;
int arr2[SIZE];

//初始化数组，数字随机产生
void initArr(){
	for(int i = 1; i <= SIZE; i ++){
		arr2[i] = rand()%50;
	}
}

//打印数组
void printArr(){
	for(int i = 1; i <= SIZE; i ++){
		cout<<arr2[i]<<(i == SIZE?"":" ");
	}
	cout<<endl;
}

//二分插入法
void bInsert(){
	int i,j,high,low,mid,temp;
	for(i = 2; i <= SIZE; i ++){
		temp = arr2[i];
		low = 1;
		high = i - 1;
		while(low <= high){
			mid = (low + high) / 2;
			if(temp > arr2[mid])
				low = mid + 1;
			else
				high = mid - 1;
		}//while

		for(j = i - 1; j >= high+1; --j)
			arr2[j+1] = arr2[j];
		arr2[j+1] = temp;
	} //for
}

int main()
{
	initArr();
	printArr();

	bInsert();
	printArr();
	return 0;
}