Data Structure--排序--插入排序----希尔排序--选择排序--堆排序

灰太狼 2022-10-31 13:51 157阅读 0赞

### 排序 ###

*  基本概念及分类
 *   *  插入排序
     *  希尔排序
     *  选择排序
     *  堆排序

# 基本概念及分类 #

**排序**:排序就是将有记录的东西,按照某个关键字进行递增的或递减的排序下来

**稳定性**:举例说明,这里有一串数组:1 9 7 4 5 5 6,其中有两个5,在进行排序  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]  
**内部排序**：元素全部放在内存中的排序。

**外部排序**：元素太多，内存中放不下,排序过程的要求不能在内外存之间移动数据的排序。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 1]

## 插入排序 ##

直接将一个数插入到有序的数组中,**直接**形成新的有序数组,相当于我们玩扑克牌,从小到大整理扑克牌,进行插入.

void insertSort(int* arr, int n){ 
    	
    	//假设第一个数据是有序的
    	//未插入数据[1,n)
    	for (int i = 0; i < n; ++i){ 
    		
    		//从有序的最后一个位置进行遍历
    		int end = i - 1;
    		int data = arr[i];
    		while (end >= 0 && arr[end] >= data){ 	//满足条件时
    			
    			//较大的数据向后移动
    			arr[end + 1] = arr[end];		//数据后移
    			--end;		//循环
    		}
    		arr[end + 1] = data;	//直接插入
    	}
    }

这个题目,相当于顺序表的头插,大体一致,大家可以具体了解了解 [点击此处][Link 1]

## 希尔排序 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 2]

void shellSort(int* arr, int n){ 
    	
    	int gap = n;		//创建gap值
    	//一趟哈希排序
    	while (gap > 1){ 
    
    		gap = gap / 3 + 1;	//让其等于一个值进行交换
    		for (int i = gap; i < n; ++i){ 	//循环内部
    
    			//同组数据,最后一个有序数组的位置
    			int end = i - gap;
    			//待插入的数据
    			int data = arr[i];
    			while (end >= 0 && arr[end]>data){ 
    
    				arr[end + gap] = arr[end];	
    				end -= gap;		//gap逐渐减到1
    			}
    			arr[end + gap] = data;		//交换
    		}
    	}
    }

## 选择排序 ##

插入理解动图[点击此处跳转看图][Link 2]  
在一组元素中,找到最小的放在最前面,然后剩下的进行二次寻找,直到排序完成!

void selectSort(int* arr, int n){ 
    	
    	int start = 0;
    	int end = n - 1;		//定义尾部节点
    	while (start < end){ 		//循环开始
    		
    		//首先找到最小值的位置
    		int minIdx = start;		
    		int i;
    		for (i = start + 1; i <= end; ++i){ 		//进行遍历
    			
    			if (arr[i] < arr[minIdx])		//如果存在最小的
    				minIdx=i;	//让它等于i
    		}
    		//将最小值存在起始位置
    		Swap(arr, start, minIdx);		//这里调用了一个最最最简单的交换元素,我就不具体写了,相信大家也会.
    		//循环
    		++start;
    	}
    }

这一个代码,我们是在每一次遍历寻找的时候,同时找到一个最大的和最小的,这样的话,需要遍历的次数就缩减了一半,提高了我们的效率!

void selectSortPlus(int* arr, int n){ 
    	
    	int start = 0;
    	int end = n - 1;
    	//我们运用同样的方法,只不过在每次遍历的时候
    	//寻找一个最大的和一个最小的,这样遍历就能减少一半
    	while (start < end){ 
    		
    		int minIdx = start;		//定义最小
    		int maxIdx = start;		//定义最大
    		for (int j = start + 1; j <= end; ++j){ 		//开始遍历
    			
    			if (arr[j] < arr[minIdx])		//找到最小的
    				minIdx = j;		//赋值
    			if (arr[j]>arr[maxIdx])			//找到最大的
    				maxIdx = j;		//赋值
    		}
    		//最小值放在头部
    		Swap(arr, start, minIdx);		//交换
    		//判断最大值位置是否在起始位置
    		if (maxIdx == start)		//如果最大值在起始位置,就说明只存在一个元素,最大最小相等!
    			maxIdx = minIdx;
    		//最大值放在尾部
    		Swap(arr, end, maxIdx);
    
    		++start;		//循环继续
    		--end;
    	}
    }

## 堆排序 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 3]

void shiftDown(int* arr, int n, int parent){ 
    	
    	int child = 2 * parent + 1;		//最后一个孩子节点的位置
    	while (child < n){ 			//循环
    		
    		if (child + 1 < n&&arr[child + 1] > arr[child])	//存在则继续
    			++child;
    		if (arr[child]>arr[parent]){ 	//孩子节点大于父节点,则交换
    
    			Swap(arr, child, parent);	//交换,如同图中的橙色线
    			
    			parent = child;		//更新
    			child = 2 * parent + 1;	//更新孩子节点
    		}
    		else
    			break;		//不满足直接结束
    	}
    }
    void heapSort(int* arr, int n){ 
    	
    	for (int i = (n - 2) / 2; i >= 0; --i){ 
    		
    		shiftDown(arr, n, i);		//进行循环调用
    	}
    	int end = n - 1;		//最后的节点依次减1
    	while (end > 0){ 		//end>0继续循环
    		
    		Swap(arr, end, 0);		//交换函数
    		shiftDown(arr, end, 0);	//交换最后一个
    		--end;		//直到end=0,循环结束
    	}
    }

我在上面的图中已经表达的很清楚了,大家具体理解,多看图,就能懂!!!多敲代码!!!一起加油!!!

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]: /images/20221024/7f706ba2a4754b4783031b3da353eaf3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 1]: /images/20221024/5da72de6339d478fbe428faec27f6531.png
[Link 1]: https://blog.csdn.net/weixin_46554582/article/details/113764090
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 2]: /images/20221024/d095191d29644a11908cecc5fc0ac024.png
[Link 2]: https://image.baidu.com/search/detail?ct=503316480&z=0&ipn=d&word=%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F&step_word=&hs=0&pn=0&spn=0&di=15290&pi=0&rn=1&tn=baiduimagedetail&is=0%2C0&istype=0&ie=utf-8&oe=utf-8&in=&cl=2&lm=-1&st=undefined&cs=3093909428%2C3210278594&os=1838708298%2C2406975132&simid=4085918796%2C611327870&adpicid=0&lpn=0&ln=1173&fr=&fmq=1614019474565_R&fm=&ic=undefined&s=undefined&hd=undefined&latest=undefined&copyright=undefined&se=&sme=&tab=0&width=undefined&height=undefined&face=undefined&ist=&jit=&cg=&bdtype=0&oriquery=&objurl=https%3A%2F%2Fgimg2.baidu.com%2Fimage_search%2Fsrc%3Dhttp%3A%2F%2Fxyzip-1253271981.costj.myqcloud.com%2F%25E5%25BE%25AE%25E4%25BF%25A1%25E5%2585%25AC%25E4%25BC%2597%25E5%25B9%25B3%25E5%258F%25B0%25E5%259B%25BE%25E5%25BA%258A%2FSort%2FSimpleSelectSort.gif%26refer%3Dhttp%3A%2F%2Fxyzip-1253271981.costj.myqcloud.com%26app%3D2002%26size%3Df9999%2C10000%26q%3Da80%26n%3D0%26g%3D0n%26fmt%3Djpeg%3Fsec%3D1616611476%26t%3D3b67e210bbf65a455a18908ebdcf0e20&fromurl=ippr_z2C%24qAzdH3FAzdH3Fooo_z%26e3Bvf1g_z%26e3BgjpAzdH3F2wpij6_d0AzdH3FMpTwY2cfM3vxMDEpY4xeZoOaOaOOaOaO_z%26e3Bip4s&gsm=1&rpstart=0&rpnum=0&islist=&querylist=&force=undefined
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 3]: /images/20221024/ad341e3c5ee949e5a577adc268227326.png