八大排序总结---- 数据结构 (图解法) 面试必会! ! !

亦凉 2022-09-01 13:47 153阅读 0赞

![请添加图片描述][56c441d56fbc41f68a274277c0630802.png]

### 八大排序总结 ###

*  目录:
 *   *  一.插入排序 (InsertSort)
     *  二.希尔排序 (ShellSort)
     *  三.选择排序 (SelectSort)
     *  四.堆排序 (HeapSort)
     *  五.冒泡排序 (BubbleSort)
     *  六.快速排序 (QuickSort)
     *   *  1.hoare法
         *  2.挖坑法
         *  3.前后指针法
     *  七.归并排序 (MergeSort)
     *   *  1.递归实现
         *  2.非递归实现
     *  八.计数排序 (CountSort)

# 目录: #

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

## 一.插入排序 (InsertSort) ##

![在这里插入图片描述][ae6b3f9dd8454f48903b44de0010b111.gif_pic_center]

>  对于插入排序的本质就是从后向前将所有的元素找到对应的位置进行插入即可.

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;	//直接插入
    	}
    }

## 二.希尔排序 (ShellSort) ##

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

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;		//交换
    		}
    	}
    }

## 三.选择排序 (SelectSort) ##

![在这里插入图片描述][222c7393e1ad48368e8bbdfb5226724f.gif_pic_center]

>  选择排序从前向后遍历,找后面小于这个数(**最小**),然后将两者进行交换,依次向后移一位.

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;
    	}
    }

## 四.堆排序 (HeapSort) ##

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

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,循环结束
    	}
    }

## 五.冒泡排序 (BubbleSort) ##

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

void bubbleSort(int* arr,int n){ 
    	
    	//相邻元素进行比较
    	//遍历范围:0-为排序的最后一位
    	int end = n;
    	while (end > 1){ 
    		
    		//第一次冒泡排序
    		for (int i = 1; i < end; ++i){ 
    			
    			if (arr[i - 1]>arr[i]){ 		//这里的i和i-1就相当于i和j
    				
    				//大的元素向后移动
    				Swap(arr, i - 1, i);		//简单交换函数,不描写接口
    			}
    		}
    		--end;		//主要进行循环
    	}
    }

## 六.快速排序 (QuickSort) ##

### 1.hoare法 ###

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

//获取基准值
    //下面输出的都会基准值
    //这段代码主要是理解,其结构不难,不进行过多的注释
    int getMid(int* arr, int begin, int end){ 
    
    	int mid = begin + (end - begin) / 2;	
    
    	if (arr[begin] > arr[mid]){ 			//==========1.开始大于中间
    
    		if (arr[mid] > arr[end])	
    			return mid;
    		else if (arr[begin] > arr[end])	
    			return end;
    		else
    			return begin;		
    	}
    	else{ 								//=========2.开始小于等于中间
    
    		if (arr[mid] < arr[end])		
    			return mid;
    		else if (arr[begin] < arr[end])
    			return end;
    		else
    			return begin;
    	}
    }
    
    //划分函数 实现数组的划分,进行分别遍历的操作
    int partion(int* arr, int begin, int end){ 
    
    	//获取基准值位置
    	int mid = getMid(arr, begin, end);
    	//把基准值放到起始位置
    	Swap(arr, begin, end);
    
    	//首先选择基准值
    	int key = arr[begin];
    	int start = begin;
    
    	while (begin < end){ 		//后置比较大的时候
    
    		//1.==============================从后向前找小于基准值的位置
    		while (begin < end&&arr[end] >= key)
    			--end;
    
    		//2.===============================从前向后找大于的位置
    		while (begin < end&&arr[begin] <= key)
    			++begin;
    		//3.===============================用函数交换
    		Swap(arr, begin, end);
    	}
    	//交换基准值与相遇位置的数据
    	Swap(arr, start, begin);
    	return begin;
    }
    
    //快速排序
    void quickSort(int* arr, int begin, int end){ 
    	
    	if (begin >= end)
    		return;
    		
    	//div:一次划分后基准值
    	int div = partion(arr, begin, end);
    	//分别进行左右两边的快排
    	//[begin,div-1]
    	//[div+1,end]
    	quickSort(arr, begin, div - 1);
    	quickSort(arr, div + 1, end);
    }

### 2.挖坑法 ###

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

//获取中间值的函数接口
    int getMid(int* arr, int begin, int end){ 
    
    	int mid = begin + (end - begin) / 2;	//获取中间值
    
    	if (arr[begin] > arr[mid]){ 		//对所处的位置进行比较,最终获取中间的值
    									//很简单的,我就不具体解释了,大家多看看就行了
    		if (arr[mid] > arr[end])
    			return mid;
    		else if (arr[begin] > arr[end])
    			return end;
    		else
    			return begin;
    	}
    	else{ 
    
    		if (arr[mid] < arr[end])
    			return mid;
    		else if (arr[begin] < arr[end])
    			return end;
    		else
    			return begin;
    	}
    }
    
    int partion2(int* arr, int begin, int end){ 
    	
    	int mid = getMid(arr, begin, end);
    	Swap(arr, begin, mid);
    	
    	//第一个基准值,也就是初始为坑的位置
    	int key = arr[begin];
    	while (begin < end){ 
    		//从后往前找到小的
    		while (begin < end&&arr[end] >= key)
    			--end;
    		//进行填坑
    		arr[begin] = arr[end];
    		//从前往后找大的
    		while (begin < end&&arr[begin] <= key)
    			++begin;
    		//填坑
    		arr[end] = arr[begin];
    	}
    	arr[begin] = key;
    	return begin;
    }
    
    
    //主要的对于下面写的划分方式的调用
    void quickSort(int* arr, int begin, int end){ 
    
    	if (begin >= end)						//如果开始的 大于结束的则为越界,直接结束
    		return;
    		
    	//div:一次划分后基准值
    	//int div = partion(arr, begin, end);
    	//int div = partion2(arr, begin, end);
    	int div = partion3(arr, begin, end);		//对下面两个种方法进行调用
    	//分别进行左右两边的快排
    	//[begin,div-1]
    	//[div+1,end]
    	quickSort(arr, begin, div - 1);			//对上面划分的左右两个区间进行循环调用
    	quickSort(arr, div + 1, end);
    }

### 3.前后指针法 ###

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

//获取中间值的函数接口
    int getMid(int* arr, int begin, int end){ 
    
    	int mid = begin + (end - begin) / 2;	//获取中间值
    
    	if (arr[begin] > arr[mid]){ 		//对所处的位置进行比较,最终获取中间的值
    									//很简单的,我就不具体解释了,大家多看看就行了
    		if (arr[mid] > arr[end])
    			return mid;
    		else if (arr[begin] > arr[end])
    			return end;
    		else
    			return begin;
    	}
    	else{ 
    
    		if (arr[mid] < arr[end])
    			return mid;
    		else if (arr[begin] < arr[end])
    			return end;
    		else
    			return begin;
    	}
    }
    
    int partion3(int* arr, int begin, int end){ 
    	
    	int mid = getMid(arr, begin, end);
    	Swap(arr, begin, mid);
    	//上一个小于基准值的位置
    	int prev = begin;
    	//下一个小于基准值的位置
    	int cur = begin + 1;
    
    	int key = arr[begin];
    	while (cur <= end){ 
    		
    		//当cur走到下一个基准值的位置的时候,判断是否连续
    		if (arr[cur]<key && ++prev != cur) { 
    			
    			//不连续,交换数据
    			Swap(arr, prev,cur);
    		}
    		++cur;		//cur继续向下走,prev不动
    	}
    	Swap(arr, begin, prev);		//与基准值进行交换,且固定
    	return prev;
    }
    
    //主要的对于下面写的划分方式的调用
    void quickSort(int* arr, int begin, int end){ 
    
    	if (begin >= end)						//如果开始的 大于结束的则为越界,直接结束
    		return;
    		
    	//div:一次划分后基准值
    	//int div = partion(arr, begin, end);
    	//int div = partion2(arr, begin, end);
    	int div = partion3(arr, begin, end);		//对下面两个种方法进行调用
    	//分别进行左右两边的快排
    	//[begin,div-1]
    	//[div+1,end]
    	quickSort(arr, begin, div - 1);			//对上面划分的左右两个区间进行循环调用
    	quickSort(arr, div + 1, end);
    }

## 七.归并排序 (MergeSort) ##

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

### 1.递归实现 ###

//归并排序
    
    void merge(int* arr, int begin, int mid, int end, int* tmp){ 
    	
    	//递增
    	int begin1 = begin;		//前半个区间
    	int end1 = mid;
    	
    	int begin2 = mid + 1;	//后半个区间
    	int end2 = end;
    
    	//辅助空间
    	int idx = begin;
    	
    	//合并有序的序列
    	//检查是否越界
    	while (begin1 <= end1&&begin2 <= end2){ 		//如果没有越界
    		
    		if (arr[begin1] <= arr[begin2])			//如果第一个元素小
    			tmp[idx++] = arr[begin1++];			//先将第一个输入
    
    		else
    			tmp[idx++] = arr[begin2++];			//否则,先将第二个输入
    	}
    	//上面的循环进行,直到结束
    	
    	//判断是否有没有合并的元素
    	if (begin1 <= end1)		//如果1中有剩余
    	
    		//直接将1中剩余的元素拷贝到序列中
    		memcpy(tmp + idx, arr + begin1, sizeof(int)*(end1 - begin1 + 1));
    	
    	if (begin2 <= end2)
    		//如果2中有剩余,直接将2中的拷贝过去
    		memcpy(tmp + idx, arr + begin2, sizeof(int)*(end2 - begin2 + 1));
    
    	//合并后的序列拷贝到原始的数据
    	memcpy(arr + begin, tmp + begin, sizeof(int)*(end - begin + 1));
    }
    
    //======================递归
    void _mergeSort(int* arr, int begin, int end, int* tmp){ 
    	
    	if (begin >= end)	//判空
    		return;
    
    	int mid = begin + (end - begin) / 2;		//找到中间元素
    
    	//先进行子序列的合并
    	_mergeSort(arr, begin, mid, tmp);
    	_mergeSort(arr, mid + 1, end, tmp);
    	//上面两部是对于子序列的合并,也就是将一个个的小点点进行合并
    
    	//合并两个有序的子序列
    	merge(arr, begin, mid, end, tmp);
    }
    void mergeSort(int* arr, int n){ 
    	
    	//申请辅助空间
    	int* tmp = (int*)malloc(sizeof(int)*n);		//申请空间方便存放
    	_mergeSort(arr, 0, n - 1, tmp);		//调用函数
    	
    	free(tmp);		//将申请用完的空间进行释放
    }

### 2.非递归实现 ###

//归并排序
    
    void merge(int* arr, int begin, int mid, int end, int* tmp){ 
    	
    	//递增
    	int begin1 = begin;		//前半个区间
    	int end1 = mid;
    	
    	int begin2 = mid + 1;	//后半个区间
    	int end2 = end;
    
    	//辅助空间
    	int idx = begin;
    	
    	//合并有序的序列
    	//检查是否越界
    	while (begin1 <= end1&&begin2 <= end2){ 		//如果没有越界
    		
    		if (arr[begin1] <= arr[begin2])			//如果第一个元素小
    			tmp[idx++] = arr[begin1++];			//先将第一个输入
    
    		else
    			tmp[idx++] = arr[begin2++];			//否则,先将第二个输入
    	}
    	//上面的循环进行,直到结束
    	
    	//判断是否有没有合并的元素
    	if (begin1 <= end1)		//如果1中有剩余
    	
    		//直接将1中剩余的元素拷贝到序列中
    		memcpy(tmp + idx, arr + begin1, sizeof(int)*(end1 - begin1 + 1));
    	
    	if (begin2 <= end2)
    		//如果2中有剩余,直接将2中的拷贝过去
    		memcpy(tmp + idx, arr + begin2, sizeof(int)*(end2 - begin2 + 1));
    
    	//合并后的序列拷贝到原始的数据
    	memcpy(arr + begin, tmp + begin, sizeof(int)*(end - begin + 1));
    }
    
    //=========================非递归
    void mergeSortNoR(int* arr, int n){ 
    
    	int* tmp = (int*)malloc(sizeof(int)*n);		//动态内存申请
    	//子序列的步长
    	int step = 1;		//步长也就是内部有一个元素步长为1,两个则为2
    	
    	while (step < n){ 		//步长最大就是原来的序列
    	
    		for (int idx = 0; idx < n; idx += 2 * step){   //注意这里,步长每次增加2!!!!!!!!
    
    			//找到两个待合并的子序列区间
    			//[begin,mid] [mid+1,end]
    			int begin = idx;
    			int mid = idx + step - 1;
    			
    			//判断是否存在第二个子序列
    			if (mid >= n - 1)
    				continue;	//不存在第二个子序列,直接跳过
    			int end = idx + 2 * step - 1;
    			//判断第二个子序列是否越界
    			if (end > n)
    				end = n - 1;
    				
    			merge(arr, begin, mid, end, tmp);
    		}
    
    		//更新步长
    		step *= 2;
    	}
    }

## 八.计数排序 (CountSort) ##

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

//====================================3.非比较排序(计数排序)
    //所消耗的空间过大 空间复杂度大
    void countSort(int* arr, int n){ 
    	
    	//找到最大和最小值
    	int max, min;
    	min = max = arr[0];
    	
    	for (int i = 1; i < n; ++i){ 	//这里是进行循环选出最大值和最小值
    	
    		if (arr[i]>max)
    			max = arr[i];
    		if (arr[i ]< min)
    			min = arr[i];
    	}
    	
    	//计算出范围
    	int range = max - min + 1;
    	//创建一个计数数组,初始化为0
    	int* countArr = (int*)calloc(range, sizeof(int));  //动态开辟一个全0的数组
    
    	//计数
    	for (int i = 0; i < n; ++i){ 
    		
    		countArr[arr[i] - min]++;		//对其进行计数
    	}
    	
    	//遍历计数数组
    	int idx = 0;
    	for (int i = 0; i < range; ++i){ 	//遍历整个范围
    		
    		while (countArr[i]--){ 		//依次减减
    
    			arr[idx++] = i + min;		//对其进行循环赋值
    		}
    	}
    }

[56c441d56fbc41f68a274277c0630802.png]: /images/20220829/21b8455987854d50a2ad9d52e898d087.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]: /images/20220829/3a9cb62e67fc43fcb36d83537c423420.png
[ae6b3f9dd8454f48903b44de0010b111.gif_pic_center]: /images/20220829/519a83d4402840518ab31fa3bb0d2b71.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 1]: /images/20220829/1bdb5822debe471db4b7370e894f8c66.png
[222c7393e1ad48368e8bbdfb5226724f.gif_pic_center]: /images/20220829/90ef01fae41342c1ad58e88b12f40a92.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 2]: /images/20220829/1ceb73b671c544e29c9a8b2e181783c8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 3]: /images/20220829/cd8d8eed7b454481becedc31eca7f3b4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 4]: /images/20220829/eadf25dc2dce40748cd1001379803f4e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 5]: /images/20220829/7a6d1064a4784d65ac77b08881c84227.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 6]: /images/20220829/8b8fb5cbf5fd4e0784bcc8726c874ee2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 7]: /images/20220829/e4da491bcaef430bb6ad58db1180f7d8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 8]: /images/20220829/b4468034cb7f485ab30107f7c31b7396.png