排序引入,插入类排序笔记

红太狼 2022-12-27 07:45 65阅读 0赞

排序  
排序: 若干元素 根据其对应的关键字的值的大小, 从小到大或从大到小  
的顺序对记录序列重新排列.

排序的稳定性:若 keyi = keyj  
排序后 这两个记录是否保持原次序不变

存储结构的设计

#define MAXSIZE 20
    typedef int KeyType;
    typedef struct 
    {
        
    	KeyType key;
    	InfoType otherinfo;
    }RcdType; //记录的类型(recordtype)
    
    //顺序存储,经常排序操作, 很少增删操作
    typedef struct 
    {
        
    	//r[0]闲置, 留作他用
    	RcdType r[MAXSIZE + 1];
    	int length;
    }SqList;

内部排序方法

插入类:  
直接插入排序  
折半插入排序  
希尔排序

选择排序:  
简单选择排序  
堆排序

交换排序:  
冒泡排序  
快速排序

归并类排序:  
二路归并排序

插入类排序:(Insertion Sort)  
1 直接插入排序  
从第二个元素开始(无序序列从第二个元素开始),  
将其左侧元素从后向前之歌比较,后移并填入

void InsertionSort(SqList &L)
    {
        
    	int i, j;
    	for (i = 2; i < L.length; i++)
    	{
        
    		if (L.r[i - 1].key > L.r[i].key)
    		{
        
    			//备份
    			L.r[0] = L.r[i];
    			//将大于 L.r[0].key都后移
    			for (j = i - 1; L.r[j].key > L.r[0].key; j--)
    				L.r[j + 1] = L.r[j];
    			//退出的位置 j的右边 是应该 放L.r[0]的位置
    			L.r[j + 1] = L.r[0];
    		}
    	}
    }

2 折半插入排序  
思想:折半法定位第一个大于待插入元素的记录位置,  
在其左侧插入  
每次和中间元素比较,如果中间元素小于或等于待插入记录  
则所需找位置在右半区, low变为 mid + 1;  
如果中间元素大,则将high变为 mid - 1;

void BinInsertionSort(SqList &L)
    {
        
    	for (int i = 2; i <= L.length; i++)
    	{
        
    		int low = 1;
    		int high = i - 1;
    		//我觉得:最后的状态是 low和high在一个位置
    		//再次进入循环,此时在通过 程序 
    		//最终会让low到high的右侧(high在low的右侧)
    		//但是为什么这时的位置就是目标状态?
    		while (low <= high)
    		{
        
    			mid = (low + high) / 2;
    			if (L.r[mid].key > L.r[i].key)
    				high = mid -1;
    			else 
    				low = mid + 1;
    		}
    		L.r[0] = L.r[i];
    		//从[high + 1] 到 [i-1] 都要后移
    		for (int j = i-1; j >= high + 1; j--)
    			L.r[j + 1] = L.r[j];
    		
    		L.r[high + 1] = L.r[0];
    	}
    }

3 总结与推广