快速排序之——挖坑法实现

69 阅读 0 评论 46 点赞

我是靠谱客的博主知性小天鹅，最近开发中收集的这篇文章主要介绍快速排序之——挖坑法实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

挖坑法思想：

挖坑图解：

代码实现：

测试结果：

上一篇文章中，我着重介绍了快速排序的代码实现——Hoare方法，但第一种代码对于接近有序的序列或者高度有序的序列来说，效率会极低，所以后面又介绍了针对Hoare的两种优化方法，其一是三数取中法，其二是小区间优化法，感兴趣的伙伴们可以看看这篇文章：快速排序之——Hoare方法一实现_ ，接下来我来讲一讲快速排序的第二种方法——挖坑法，这种方法是基于Hoare改造后的方法，效率上要比Hoare要好一些。

挖坑法思想——也是递归快排算法

通过采用三数取中的方法，选择首中尾三个数的中值作为基准元素，这个基准元素就相当于一个坑位(hole)，因为我是将基准元素放在了数组的最左侧，那么需要数组的Right变量先走，大家若是想要Left变量先走，那么就把基准元素放在数组的最右侧即可！

Right也是和Hoare方法类似，先寻找比基准元素值小的元素，找到后把该值放到坑位上，然后该值的位置便会成为新的坑位；之后Left走，寻找比基准元素值大的元素，找到后的步骤也是和Right同理，放值于坑位，更新坑位。就这样，你一步我一步，直到Left==Right，它俩走到同一个位置便不再走了，最后把key值放到坑中，这样基准值就放到了数组序列的中间，再通过快排递归的方法进行整合排序即可完成！

挖坑图解：

代码实现：

#define _CRT_SECURE_NO_WARNINGS 1
# include<stdio.h>

//挖坑法

void PrintArr(int* arr, int n) {
	for (int i = 0; i < n; i++) {
		printf("%d ", arr[i]);
	}
	printf("n");
}
void Swap(int* p1, int* p2) {
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}



//三数取中法
int GetMidIndex(int* arr, int left, int right) {
	int mid = (right - left) / 2 + left;
	if (arr[left] < arr[mid]) {
		if (arr[mid] < arr[right]) {
			return mid;
		}
		else if (arr[left] > arr[right]) {
			return left;
		}
		else {
			return right;
		}
	}
	else {			//arr[left]>=arr[mid]
		if (arr[mid] > arr[right]) {
			return mid;
		}
		else if (arr[left] < arr[right]) {
			return left;
		}
		else {
			return right;
		}
	}
}


//挖坑法
int PartSort(int* arr, int left, int right) {
	int mid = GetMidIndex(arr, left, right);
	Swap(&arr[left], &arr[mid]);
	int key = arr[left];
	int hole = left;
	while (left < right) {
		while (left < right && arr[right] >= key) {
			right--;
		}
		if (arr[right] < key) {
			arr[hole] = arr[right];
			hole=right;
		}
		while (left < right && arr[left] <= key) {
			left++;
		}
		if (arr[left] > key) {
			arr[hole] = arr[left];
			hole = left;
		}
	}
	arr[hole] = key;
	return hole;
}


//快排递归
void QuickSort(int* arr, int begin, int end) {
	if (begin >= end) {
		return;
	}
	int keyi = PartSort(arr, begin, end);
	QuickSort(arr, begin, keyi - 1);
	QuickSort(arr, keyi + 1, end);
}