经典算法之折半插入排序

/************************
author's email:wardseptember@gmail.com
date:2017.12.10
折半插入排序
************************/
/*
折半插入排序与直接插入排序算法思想类似，区别是查找插入位置的方法不同，
折半插入排序是采用折半查找的方法来查找插入位置的。
*/
#include<iostream>
#define maxSize 10
using namespace std;
void BinaryInsertSort(int *a, int n);//折半插入排序
void printArray(int D[], int n);//输出数组
void main() {
	int E[maxSize] = { 12,15,48,46,16,78,57,88,65,48 };//构造一个一维数组

	BinaryInsertSort(E, maxSize);//折半插入排序
	cout << "折半插入排序后，结果为：" << endl;
	printArray(E, maxSize);
}
void BinaryInsertSort(int *a, int n)
{
	for (int i = 1; i < n; i++) {
		int temp = a[i];//将待插关键字存入temp
		int low = 0;
		int high = i - 1;

		//下面这个循环查找要插入的位置
		while (low <= high) {
			int mid = (low + high) / 2;
			if (temp > a[mid]) //待插元素比中间值大,取m+1到high区域
				low = mid + 1;
			else
				high = mid - 1;
		}

		//将temp插入a[low]位置。将比low下标大的关键字整体后移
		for (int j = i; j > low; j--) {//或者为for (int j = i; j > high+1; j--)
			a[j] = a[j - 1];
		}
		a[low] = temp;//或者为a[high+1]=temp;
	}
}
void printArray(int D[], int n) {
	for (int i = 0; i < n; ++i)  //输出排序后的关键字
		cout << D[i] << " ";
	cout << endl;
}

版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/wardseptember/article/details/78764176
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。

发表于 2020-06-27 23:20:32
阅读 ( 937 )
分类：算法

经典算法之折半插入排序

你可能感兴趣的文章

精选的优质文章

0 条评论

官方社群

GO教程

推荐文章

猜你喜欢

随便看看