精华内容
下载资源
问答
  • 21、折半插入排序 22、21、折半插入排序 22、冒泡排序 21、折半插入排序 22、冒泡排序 23、快速排序 21、折半插入排序 22、冒泡排序 23、快速排序 24、简单选择排序 21、折半插入排序 22、冒泡排序 23、快速排序 24...
  • 折半插入排序

    2020-02-22 11:02:53
    折半插入排序 -什么是折半插入排序 折半插入排序就是在直接插入排序的基础上,修改了“查找”操作的算法,使用折半查找操作,使得排序效率得到提升。 折半插入排序的算法步骤 (1)设待排序的记录放在数组r[1…n]中...

    折半插入排序

    -什么是折半插入排序
    折半插入排序就是在直接插入排序的基础上,修改了“查找”操作的算法,使用折半查找操作,使得排序效率得到提升。

    • 折半插入排序的算法步骤
      (1)设待排序的记录放在数组r[1…n]中,r[1]是一个有序序列。
      (2)循环n-1次,每次使用折半查找法,查找了r[i]在已经排好序的序列了r[1…i-1]的插入位置,然后将其插入到一个表长为i-1的有序序列,依次循环,最后得到一个表长为n的序列。
    • 代码实现
    	#include<iostream>
    	using namespace std;
    	
    	#define MAXSIZE 20
    	typedef int KeyType;
    	typedef struct
    	{
    		KeyType key;//关键字
    		int other;//其他信息
    	}RedType;
    	
    	typedef struct
    	{
    		RedType r[MAXSIZE];
    		int length;
    	}SqList;
    	
    	void CreateSqList(SqList& L)
    	{
    		cout << "输入表的长度:";
    		cin >> L.length;
    		cout << "输入表的关键字信息:";
    		for (int i = 0; i < L.length; i++)
    		{
    			cin >> L.r[i].key;
    		}
    	}
    	
    	void BIinsertSort(SqList& L)
    	{
    		for (int i = 1; i < L.length; i++)
    		{
    			int key = L.r[i].key;
    			int low = 0;
    			int high = i - 1;
    			while (low <= high)//折半查找
    			{
    				int mid = (low + high) / 2;//折半
    				if (key < L.r[mid].key) high = mid - 1;//插入点在前半子表
    				else low = mid + 1;//插入点在后半子表
    			}
    			for (int j = i - 1; j >= high + 1; j--)//记录后移
    			{
    				L.r[j + 1].key = L.r[j].key;
    			}
    			L.r[high + 1].key = key;//插入点赋值
    		}
    	}
    	
    	void Show(SqList L)
    	{
    		for (int i = 0; i < L.length; i++)
    		{
    			cout << L.r[i].key << " ";
    		}
    	}
    	
    	int main()
    	{
    		SqList L;
    		CreateSqList(L);
    		BIinsertSort(L);
    		cout << "排好序的表的关键字信息:";
    		Show(L);
    		return 0;
    	}
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,534
精华内容 1,413
关键字:

折半插入排序