Data Structure--排序--快速排序(挖坑法)--快速排序(前后指针法)

拼搏现实的明天。 2022-11-03 10:38 172阅读 0赞

### 快速排序 ###

*  快速排序(挖坑法)
 *  快速排序(前后指针法)

对于下面要讲的两种进行快排的函数来说,我们都需要利用下面的这两个函数,一个是**获取中间值的接口**,一个是**快排的调用函数的用法**,下面这两个函数都要和下面要讲的接口进行共同利用,在这里我就不写两遍了.

//获取中间值的函数接口
    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;
    	}
    }
    
    //主要的对于下面写的划分方式的调用
    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);
    }

# 快速排序(挖坑法) #

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

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

只要你坚持看完我写的,你一定会深有体会,加油!

# 快速排序(前后指针法) #

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

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

这两个例题加上上一篇的**hoare法**就是**快速排序的基本的三种类型**,主要理解过程,大家一定要搞懂,对于后期的面试会有同类型的题目,加油,多敲代码!!!

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]: /images/20221024/576841f303584144a88209bc4af5a7cb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 1]: /images/20221024/c366020488de4f7db67766aed272c70a.png