Data Structure--排序--冒泡排序--快速排序(hoare)

朴灿烈づ我的快乐病毒、 2022-11-01 05:29 54阅读 0赞

### 排序 ###

*  冒泡排序
 *  快速排序(hoare)

接上一篇博客.

# 冒泡排序 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]  
上图已经详细的讲解了过程,大家仔细看就好,下来我直接讲代码.

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;		//主要进行循环
    	}
    }

很简单,重点理解下面这个排序方式.

# 快速排序(hoare) #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 1]  
上图看起来可能比较难理解,大家耐心起来看,很简单的,一起加油!!!

//获取基准值
    //下面输出的都会基准值
    //这段代码主要是理解,其结构不难,不进行过多的注释
    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);
    }

注意这里的div的理解:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 2]  
这两种排序我就讲解到这里,相信大家如果完全看懂的话就没有问题了!!最最最主要的还是要多敲代码!!!一起加油啊!!!

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]: /images/20221024/74960bc579bc4f92a5f7b85b70f40621.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 1]: /images/20221024/2d220b1ac8084e2f9e7b6fc3a757538c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 2]: /images/20221024/8dce65cb4bb24942af33f3da725ab32f.png