Java教程

重刷搜索排序算法

本文主要是介绍重刷搜索排序算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

文章目录

      • 一、二分搜索算法
        • 1. 非递归代码
        • 2. 递归代码
      • 二、冒泡排序算法
      • 三、选择排序
      • 四、插入排序
      • 五、希尔排序
      • 六、快速排序
      • 七、归并排序
      • 八、堆
        • 1. 二叉堆的概念
        • 2. 调堆
        • 3. 用堆实现优先级队列
        • 4. 堆排序
      • 九、STL中的sort
      • 十、基数排序

一、二分搜索算法

1. 非递归代码

// 找到返回索引,找不到返回-1
int binary_search(const vector<int>& vec, int val) {
	int left = 0;
	int right = vec.size() - 1;
	while (left <= right) {
		int mid = (left + right) >> 1;
		if (vec[mid] == val) {
			return mid;
		}
		else if (vec[mid] < val) {
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}
	return -1;
}

2. 递归代码

递归函数特点:

  1. 不管什么数据规模,求解问题的方式是一样的
  2. 有递推公式

写递归函数注意点:

  1. 搞清楚递归函数的意义,返回值、参数列表以及完成什么功能
  2. 递要有结束的条件
  3. 每个数据规模要写好计算关系,即递推公式

递归问题的思考是水平方向上的,递归问题的执行是竖直方向上的

在这里插入图片描述

// 函数功能:在[left, right]区间内搜索val,找到返回下标,找不到返回-1
int recur_binary_search(const vector<int>& vec, int left, int right, int val) {
	// 递归结束条件
	if (left > right) {
		return -1;
	}
	int mid = (left + right) >> 1;
	if (vec[mid] == val) {
		return mid; // 找到返回索引
	}
	else if (vec[mid] > val) {
		return recur_binary_search(vec, left, mid - 1, val); //在[left, mid - 1]区间内搜索val,找到返回下标,找不到返回-1
	}
	else {
		return recur_binary_search(vec, mid + 1, right, val); //在[mid + 1, right]区间内搜索val,找到返回下标,找不到返回-1
	}
}

二、冒泡排序算法

在这里插入图片描述

void bubble_sort(vector<int>& vec) {
	// 外层控制趟数,n个元素最多n-1趟,最后一趟只有一个元素所以可以减1
	for (int i = 0; i < vec.size() - 1; i++) {
		// 假设这一趟排序没有交换元素
		bool is_swap = false;
		// 每趟会处理一个元素,所以减i。减1是因为用vec[j]和vec[j+1]比较
		for (int j = 0; j < vec.size() - 1 - i; j++) {
			if (vec[j] > vec[j + 1]) {
				int tmp = vec[j];
				vec[j] = vec[j + 1];
				vec[j + 1] = tmp;
				is_swap = true;
			}
		}
		// 一趟排序结束,判断是否进行了元素交换
		if (!is_swap) {
			break;
		}
	}
}

冒泡排序的效率较低,原因在于交换元素的次数过多,但是可以提前终止

三、选择排序

在这里插入图片描述

void choice_sort(vector<int>& vec) {
	if (vec.size() < 2) {
		return;
	}
	// 外循环用于控制趟数
	for (int i = 0; i < vec.size() - 1; i++) {
		int min_val = vec[i]; // 用于记录当前最小值
		int min_i = i;        // 记录最小值的位置
		// 找到无序序列中最小的元素,并记录准备交换
		for (int j = i+1; j < vec.size(); j++) {
			if (vec[j] < min_val) {
				min_val = vec[j];
				min_i = j;
			}
		}
		if (min_i != i) {
			int tmp = vec[i];
			vec[i] = vec[min_i];
			vec[min_i] = tmp;
		}
	}	
}

选择排序的效率比冒泡排序的效率稍微高一点,原因在于没有很多的赋值操作(每一趟只交换赋值一次),但是有很多的比较操作,而且也不像冒泡排序一样可以提前终止。

不稳定: 比如有序列5、5、3,第一个5和3交换,就成了3、5、5

四、插入排序

如果数据趋于有序,插入排序是所有排序算法中,效率最高的排序算法。不仅仅没有交换,比较次数也较少

算法思想:前面的序列是有序的,把无序序列中第一个元素按顺序插入到有序序列,一边找一边移动元素,找第一个 小于等于(可保证稳定性) 自己的元素,查到该元素后面

在这里插入图片描述

void insert_sort(vector<int>& vec) {
	if (vec.size() < 2) {
		return;
	}
	for (int i = 1; i < vec.size(); i++) {
		int val = vec[i];
		int j;
		// 在有序序列中查找第一个小于等于当前元素的元素
		for (j = i - 1; j >= 0; j--) {
			// 注意这个地方是<=val,不是<=vec[i],vec[i]可能早就被覆盖了
			if (vec[j] <= val) {
				break;
			}
			else {
				vec[j + 1] = vec[j];
			}
		}
		vec[j + 1] = val;
	}
}

五、希尔排序

如果数据趋于有序,插入排序是所有排序算法中,效率最高的排序算法。而 希尔排序是从全局的角度把数据调整得趋于有序 ,利用插入排序的这一特点,最后进行一次插入排序(gap=1)

在这里插入图片描述

void shell_sort(vector<int>& vec) {
	if (vec.size() < 2) {
		return;
	}
	for (int gap = vec.size() >> 1; gap > 0; gap >>= 1) {
		for (int i = gap; i < vec.size(); i++) {
			int val = vec[i];
			int j;
			// 在有序序列中查找第一个小于等于当前元素的元素
			for (j = i - gap; j >= 0; j -= gap) {
				// 注意这个地方是<=val,不是<=vec[i],vec[i]可能早就被覆盖了		
				if (vec[j] <= val) {
					break;
				}
				else {
					vec[j + gap] = vec[j];
				}
			}
			vec[j + gap] = val;
		}
	}
}

在这里插入图片描述

六、快速排序

在这里插入图片描述

可以看出,如果这棵二叉树比较平衡,那么深入的层数会更少,也就是数据分布比较均匀,比较乱序的时候,二叉树会比较平衡,快速排序的效率较高。若二叉树不平衡,则导致排序下效率低下

int partition(vector<int>& vec, int l, int r) {
	int val = vec[l];
	while (l < r) {
		while (l < r && vec[r] > val) {
			r--;
		}
		if (l < r) {
			vec[l] = vec[r];
			l++;
		}
		while (l < r && vec[l] < val) {
			l++;
		}
		if (l < r) {
			vec[r] = vec[l];
			r--;
		}
	}
	// 这里l == r,循环退出
	vec[l] = val;
	return l;
}

// 这是一个递归函数,主要功能是使得区间[begin, end]内的数据有序
void quick_sort(vector<int>& vec, int begin, int end) {
	// 先写结束条件
	// 这里是归,归的时候已经排序完成了
	if (begin >= end) {
		return;
	}
	// 这个操作是让[begin, end]区间内的第一个元素找到自己有序后的位置pos
	// 先划分,找到基准元素的正确位置
	int pos = partition(vec, begin, end);
	// 再递
	quick_sort(vec, begin, pos-1);
	quick_sort(vec, pos+1, end);
}

平均时间复杂度:O(nlogn)
最坏时间复杂度:当数列本身有序的时候,除了叶子节点,所有节点都只有1个孩子节点,O(n^2)
空间复杂度:主要指的是递归的时候开辟的函数栈帧,O(logn)
最坏空间复杂度:同理,O(n)

快排算法优化

优化一:快排不断递归后,作用区间会越来越小,数据会越 趋于有序,这个时候使用插入排序 对该区间进行排序可以提升效率

void quick_sort(vector<int>& vec, int begin, int end) {
	if (begin >= end) {
		return;
	}
	// COUNT是数据规模
	if(end - begin < COUNT / 10){
		insert_sort(vec, begin, end);
		return;
	}
	int pos = partition(vec, begin, end);
	quick_sort(vec, begin, pos-1);
	quick_sort(vec, pos+1, end);
}

优化二:三数取中法

void right_order(const vector<int>& vec, int& small, int& mid, int& big) {
	int tmp;
	if (vec[small] > vec[mid]) { 
		tmp = small; 
		small = mid;
		mid = tmp; 
	}

	if (vec[small] > vec[big]) {
		tmp = small;
		small = big;
		big = tmp; 
	}

	if (vec[mid] > vec[big]) {
		tmp = mid; 
		mid = big; 
		big = tmp; 
	}
}

int partition(vector<int>& vec, int l, int r) {
	int small = l;
	int mid = (l + r) >> 1;
	int big = r;

	// 执行后,vec[small] < vec[mid] < vec[big]
	right_order(vec, small, mid, big); 

	int val = vec[mid];
	if (l != mid) {
		int tmp = vec[l];
		vec[l] = vec[mid];
		vec[mid] = tmp;
	}

	while (l < r) {
		while (l < r && vec[r] > val) {
			r--;
		}
		if (l < r) {
			vec[l] = vec[r];
			l++;
		}
		while (l < r && vec[l] < val) {
			l++;
		}
		if (l < r) {
			vec[r] = vec[l];
			r--;
		}
	}
	// 这里l == r,循环退出
	vec[l] = val;
	return l;
}

// 这是一个递归函数,主要功能是使得区间[begin, end]内的数据有序
void quick_sort(vector<int>& vec, int begin, int end) {
	// 先写结束条件
	if (begin >= end) {
		return;
	}
	// 这个操作是让[begin, end]区间内的第一个元素找到自己有序后的位置pos
	// 先划分
	int pos = partition(vec, begin, end);
	quick_sort(vec, begin, pos-1);
	quick_sort(vec, pos+1, end);
}

在递的过程中就进行分割,在归的过程中什么都不做

七、归并排序

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

// 将vec内[begin, mid],[mid+1, end]进行有序合并
void merge(vector<int>& vec, int l, int mid, int r) {
	int* tmp = new int[r - l + 1]();
	int i = l;        // 左子序列的索引
	int j = mid + 1;  // 右子序列的索引
	int idx = 0;      // 合并后序列的索引
	while (i <= mid && j <= r) {
		if (vec[i] <= vec[j]) {
			tmp[idx++] = vec[i++];
		}
		else {
			tmp[idx++] = vec[j++];
		}
	}
	while (i <= mid) {
		tmp[idx++] = vec[i++];
	}
	while (j <= r) {
		tmp[idx++] = vec[j++];
	}
	for (i = l, j = 0; i <= r; i++, j++) {
		vec[i] = tmp[j];
	}
	delete[] tmp;
}

// 使得vec区间[begin, end]内的元素变得有序
void merge_sort(vector<int>& vec, int begin, int end) {
	if (begin >= end) {
		return;
	}
	int mid = (begin + end) >> 1;
	
	// 再分别对[begin, mid], [mid+1, end]进行归并排序
	// 这是递的过程,并没有进行排序
	merge_sort(vec, begin, mid);
	merge_sort(vec, mid+1, end);

	// 归并的过程
	merge(vec, begin, mid, end);
}

最好最坏时间复杂度:是一颗完美的平衡二叉树,树的深度都是O(logn),每层为O(n)O(nlogn)
空间复杂度:指的是递的时候开辟的函数栈帧O(logn),以及合并的时候额外的空间O(n),取大的O(n)

在递的过程中什么都不做,在归的过程中就进行合并排序

八、堆

1. 二叉堆的概念

在这里插入图片描述
最后一个非叶子节点计算公式:(n-1)/2
在这里插入图片描述

2. 调堆

入堆: 入堆只能从堆底入,然后进行调堆
在这里插入图片描述
出堆: 出堆只能从堆顶出,然后进行调堆
在这里插入图片描述

从堆顶出元素后,先将堆底元素放到堆顶,然后进行下沉:不断地将值大的孩子节点上调,自己下沉,直到没有孩子节点为止(即当前下标大于(n-1)/2

调堆的时间复杂度都是树的高度:O(logn)

3. 用堆实现优先级队列

class PriorityQueue {
public:
	// 定义函数对象类型
	using Comp = function<bool(int, int)>;
	PriorityQueue(int cap = 20, Comp comp = greater<int>())
		:_size(0)
		, _cap(cap)
		, _comp(comp) {
		_queue = new int[_cap];
	}
	PriorityQueue(Comp comp)
		:_size(0)
		, _cap(20)
		, _comp(comp) {
		_queue = new int[_cap];
	}
	~PriorityQueue(){
		delete[] _queue;
	}

public:
	bool empty() const{
		return _size == 0;
	}

	int top() const {
		if (empty()) {
			throw "queue is empty!";
		}
		return _queue[0];
	}

	int size() const {
		return _size;
	}

	// push pop top size
	void push(int val) {
		if (_size == _cap) {
			expand();
		}
		if (_size == 0) {
			_queue[_size] = val;
		}
		else {
			sift_up(_size, val); // 从堆底入堆
		}
		_size++;
	}

	void pop() {
		if (empty()) {
			throw "queue is empty!";
		}
		_size--;
		// 堆中只有一个元素,出堆就不用管了
		// 出堆后还有元素,需要继续调堆
		if (_size > 0) {
			sift_down(0, _queue[_size]); // 把最后一个节点放到0号位置,然后调整
		}
	}

private:
	void expand() {
		const int time = 2;
		int* tmp = new int[_cap * time];
		memcpy(tmp, _queue, _cap * sizeof(int));  // 逐字节拷贝,如果对于浅拷贝出错的对象,不可用memcpy
		delete _queue;
		_queue = tmp;
		_cap *= time;
	}
	
	// 节点上浮操作:把正处于cur位置,值为val的节点上浮
	void sift_up(int cur, int val) {
		while (cur > 0) {
			int father = (cur - 1) >> 1;
			if (_comp(val , _queue[father])) {
				_queue[cur] = _queue[father];   // 父节点被拉下来
				cur = father;                   // 更新此时所处位置
			}
			else {
				break;
			}
		}
		_queue[cur] = val;
	}

	// 节点下沉,把正处于cur位置值为val的节点下沉
	void sift_down(int cur, int val) {
		// 当前节点cur不能超过最后一个内部节点
		while (cur <= (_size - 1) / 2) {
			int max_child = 2 * cur + 1; // 假定左孩子大
			// 存在右孩子,且右孩子更大
			if (2 * cur + 2 <= _size && _comp(_queue[2 * cur + 2], _queue[max_child])) {
				max_child = 2 * cur + 2;
			}
			// 选出大孩子后,若大孩子大于当前val,则交换
			if (_comp(_queue[max_child], val)) {
				_queue[cur] = _queue[max_child];
				cur = max_child;
			}
			else {
				// 否则退出
				break;
			}
		}
		_queue[cur] = val;
	}

private:
	int* _queue;
	int _size;
	int _cap;
	Comp _comp;
};

int main(){
	const int COUNT = 10;
	srand(time(nullptr));
	
	PriorityQueue q([](int a, int b)->bool {return a < b; });
	for (int i = 0; i < COUNT; i++) {
		int val = rand() % 100;
		q.push(val);
		cout << val << " ";
	}
	cout << endl;

	while (!q.empty()) {
		cout << q.top() << " ";
		q.pop();
	}
	cout << endl;
	
	return 0;
}

写法1:

PriorityQueue q(less<int>()); // 写法在VS中不被当成构造对象,VS认为这是一个函数声明
cout<<typeid(q).name();  // class PriorityQueue __cdecl(struct std::less<int> (__cdecl*)(void))

PriorityQueue fun(int a);
cout << typeid(fun).name(); // class PriorityQueue __cdecl(int)

PriorityQueue q1(std::move(less<int>())); // 强行修改为右值,程序可以正常执行

用less类型显示生成临时对象当做实参传递,被处理成函数指针类型,VS认为这是一个函数声明,而不是构造一个对象,这属于编译器解析错误。

本应该是一个右值,这里没有被当成右值

注意: 最好不要显示构造临时对象,当作实参传递

写法2:

function<bool<int, int>> comp = less<int, int>();
PriorityQueue q(comp); // 不报错

写法3:

PriorityQueue q([](int a, int b){return a < b;}); // 不报错

4. 堆排序

从最后一个内部节点开始调堆,使得0号节点到第一个内部节点(n-1)/2全都满足堆性质,n表示最后一个节点的索引
在这里插入图片描述
堆顶元素和最后一个元素交换,则完成一个元素的排序任务

在这里插入图片描述
下一次排序,则少考虑一个元素

// 使索引为cur的节点满足堆性质,当前容器中需要排序的元素数量为size
void sift_down(vector<int>& vec, int cur, int size) {
	int val = vec[cur];
	int n = size - 1;   // 最后一个节点的下标
	while (cur <= (n - 1) >> 1) {
		// 先找出大孩子
		int max_child = 2 * cur + 1;
		if (2 * cur + 2 <= n && vec[2 * cur + 2] > vec[max_child]) {
			max_child = 2 * cur + 2;
		}
		if (vec[max_child] > val) {
			vec[cur] = vec[max_child];
			cur = max_child;
		}
		else {
			// 已经满足堆性质,退出下沉过程
			break;
		}
	}
	vec[cur] = val;
}

void heap_sort(vector<int>& vec) {
	// 首先进行堆化,从最后一个内部节点开始调堆
	int n = vec.size() - 1;  // 最后一个节点的下标
	for (int i = (n - 1) >> 1; i >= 0; i--) {
		sift_down(vec, i, vec.size()); // O(logn)
	}
	// 堆化以后,每次将堆顶元素和最后一个元素交换位置,并对堆顶元素sift_down,使堆顶元素满足堆性质
	// i表示当前容器需要进行排序的元素个数
	for (int i = vec.size(); i > 1; i--) {//O(logn)
		// 和最后一个元素交换
		int tmp = vec[0];
		vec[0] = vec[i-1];
		vec[i-1] = tmp;
		sift_down(vec, 0, i-1);  // 0表示每次只需要对堆顶元素sift_down
	}
}

不稳定,只有两个相同元素能建立起比较关系的时候才有机会稳定。
在堆排序中,相同的值如果处于不同的子树,这两个值就无法比较,不稳定

在这里插入图片描述
总结:
在这里插入图片描述

数据量比较大,且均匀的时候,快排排序>归并排序>希尔排序>堆排序

  1. 归并排序比快排慢在,需要把合并的数据放在临时数组,最后拷贝到原数组
  2. 不管是快排还是归并排序,遍历数组的时候都是按顺序访问,这对CPU缓存是友好的(局部性原理),但是堆排序不是顺序访问,这不符合局部性原理,所以排序较慢
  3. 每次下沉调整的时候,需要把堆底的元素和堆顶元素交换,由于堆底元素是比较小的,所以下沉操作需要进行很多次,才能重新调成一个堆,这就耗费时间

九、STL中的sort

部分源码

template <class _RanIt, class _Pr>
_CONSTEXPR20 void sort(const _RanIt _First, const _RanIt _Last, _Pr _Pred) { // order [_First, _Last)
    _Adl_verify_range(_First, _Last);
    const auto _UFirst = _Get_unwrapped(_First);
    const auto _ULast  = _Get_unwrapped(_Last);
    _Sort_unchecked(_UFirst, _ULast, _ULast - _UFirst, _Pass_fn(_Pred));
}
template <class _RanIt, class _Pr>
_CONSTEXPR20 void _Sort_unchecked(_RanIt _First, _RanIt _Last, _Iter_diff_t<_RanIt> _Ideal, _Pr _Pred) {
    // order [_First, _Last)
    for (;;) {
    	// 随着快排的进行,元素会趋于有序
  	  	// 快排过程中如果区间不大于 _ISORT_MAX = 32,转入插入排序
        if (_Last - _First <= _ISORT_MAX) { // small
            _Insertion_sort_unchecked(_First, _Last, _Pred);
            return;
        }
		// _Ideal表示当前区间元素的个数
		// 每次递归的时候,都会让_Ideal缩小
		// 为了避免递归太深,当_Ideal <= 0的时候,停止递归,采用时间复杂度稳定为O(log2n)的堆排序
        if (_Ideal <= 0) { // heap sort if too many divisions
            _Make_heap_unchecked(_First, _Last, _Pred);
            _Sort_heap_unchecked(_First, _Last, _Pred);
            return;
        }

        // divide and conquer by quicksort
        auto _Mid = _Partition_by_median_guess_unchecked(_First, _Last, _Pred);

        _Ideal = (_Ideal >> 1) + (_Ideal >> 2); // allow 1.5 log2(N) divisions

        if (_Mid.first - _First < _Last - _Mid.second) { // loop on second half
            _Sort_unchecked(_First, _Mid.first, _Ideal, _Pred);
            _First = _Mid.second;
        } else { // loop on first half
            _Sort_unchecked(_Mid.second, _Last, _Ideal, _Pred);
            _Last = _Mid.first;
        }
    }
}
  1. 快速排序不是稳定的O(log2n),最坏的情况会变成O(n^2),可以通过 改插入排序 或者 三数取中 的方法改善情况恶化
  2. 参考STL中sort的源码,可设置变量_Ideal控制递归深度
  3. 递归太深可能导致函数调用开销过多,甚至栈溢出,程序崩溃
  4. 若递归到已经快溢出了,还没排完,在sort中选择的是时间复杂度稳定的堆排序

在这里插入图片描述
冒泡会导致比较和交换次数过多,选择排序的比较次数也很多,在基本逆序的情况下,插入排序和快排的时间复杂度是O(n^2),不了解数列特征的时候选择稳定的堆排序O(log2n)

在这里插入图片描述
考察空间复杂度,归并排序O(n),此时肯定需要使用磁盘IO,效率很低。快速排序递归的空间复杂度为O(log2n)

在这里插入图片描述
外排序算法过程:

  1. 创建11个txt文件,分别写入1024M/11的数据,此时每个文件的数据不足100M
  2. 分别将11个文件的数据读入内存进行排序,然后写回硬盘,此时11个文件的数据都有序
  3. 从11个文件中分别读取1个数字,按照归并的思想选出最小的一个写入最终的文件,从写入数字对应的文件中再读取一个数,如此循环,直到所有数据排序完成

十、基数排序

在这里插入图片描述
在这里插入图片描述

void radix_sort(vector<int>& vec) {
	if (vec.size() < 2) {
		return;
	}
	vector<vector<int>> buckets(10);
	// int max_num = *max_element(vec.begin(), vec.end());
	int max_num = vec[0];
	for (int i = 1; i < vec.size(); i++) {
		if (vec[i] > max_num) {
			max_num = vec[i];
		}
	}

	int len = to_string(max_num).size();
	int mod = 10; // 先取出取模后剩下的值
	int dev = 1;  // 再取出最高位

	for (int i = 0; i < len; i++, mod *= 10, dev *= 10) {
		for (int j = 0; j < vec.size(); j++) {
			// 按照每个位放入对应的桶
			int index = vec[j] % mod / dev;
			buckets[index].push_back(vec[j]);
		}
		// 从每个桶中取出元素放回原始数组,并清空桶
		int cur = 0;
		for (int j = 0; j < 10; j++) {
			for (int v : buckets[j]) {
				vec[cur++] = v;
			}
			buckets[j].clear();
		}
	}
}

缺点:由于是按照数值进行索引,无法处理负数

void radix_sort(vector<int>& vec) {
	if (vec.size() < 2) {
		return;
	}
	// 生成20个桶,1-9号桶放负数,10-19号桶放正数
	int bucket_num = 20;
	vector<vector<int>> buckets(bucket_num);
	int longest_num = abs(vec[0]);
	for (int i = 1; i < vec.size(); i++) {
		if (abs(vec[i]) > longest_num) {
			longest_num = abs(vec[i]);
		}
	}

	int len = to_string(longest_num).size();
	int mod = 10; // 先取出取模后剩下的值
	int dev = 1;  // 再取出最高位

	for (int i = 0; i < len; i++, mod *= 10, dev *= 10) {
		for (int j = 0; j < vec.size(); j++) {
			// 按照每个位放入对应的桶
			int index = vec[j] % mod / dev + 10;
			buckets[index].push_back(vec[j]);
		}
		// 从每个桶中取出元素放回原始数组,并清空桶
		int cur = 0;
		for (int j = 0; j < bucket_num; j++) {
			for (int v : buckets[j]) {
				vec[cur++] = v;
			}
			buckets[j].clear();
		}
	}
}

在这里插入图片描述
d表示数据的位数,空间复杂度主要是和桶相关

这篇关于重刷搜索排序算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!