以下笔记为jjyaoao本人制作，欢迎借鉴学习和提出相关建议，转载需要标明出处www.jjyaoao.space

之前我们已经学过了……..

快速排序

概述

分而治之

确定轴点

构造轴点

单调性和不变性

算法实现

quickSort()

partition()

实例

通过实例，可以清楚看出，5a和5b的位置已经彼此颠倒，他们是不稳定的

性能分析

不稳定+就地

不稳定：同样数字位置会变动

就地：只需要常数的辅助空间

最好、最坏情况

平均情况

变种

L U G —–> L G U (L:小的 G: 大的 U：轴点)

不变性

单调性

实现

实例

从实现可以看出，稳定性仍然无法保证…..

选取

选取+中位数

从中位数到众数

遍历一趟整个数据集，统计出目标元素的数目，根据定义即可判断是否是众数

从频繁数到众数

在高效的中位数算法未知之前，也许我们应该寻找其他的出路，比如，频繁数

根据定义，众数不仅最多，而且多于其他元素的总和

减而治之

不断减小范围，不断统计m，直到占据半壁江山

算法实现

template <typename T> T majEleCandidate ( Vector<T> A ) { //选出具备必要条件的众数候选者
0002    T maj; //众数候选者
0003 // 线性扫描：借助计数器c，记录maj与其它元素的数量差额
0004    for ( int c = 0, i = 0; i < A.size(); i++ )
0005       if ( 0 == c ) { //每当c归零，都意味着此时的前缀P可以剪除
0006          maj = A[i]; c = 1; //众数候选者改为新的当前元素
0007       } else //否则
0008          maj == A[i] ? c++ : c--; //相应地更新差额计数器
0009    return maj; //至此，原向量的众数若存在，则只能是maj —— 尽管反之不然
0010 }

选取：通用算法

排序计算自身需要高复杂度，如果我们只需要选取众数（选出特定的数）

则可以舍弃排序的思路

尝试

蛮力

堆A

堆B

堆C

quickSelect

template <typename T> void quickSelect ( Vector<T> & A, Rank k ) { //基于快速划分的k选取算法
0002    for ( Rank lo = 0, hi = A.size() - 1; lo < hi; ) {
0003       Rank i = lo, j = hi; T pivot = A[lo]; //大胆猜测
0004       while ( i < j ) { //小心求证：O(hi - lo + 1) = O(n)
0005          while ( ( i < j ) && ( pivot <= A[j] ) ) j--; A[i] = A[j];
0006          while ( ( i < j ) && ( A[i] <= pivot ) ) i++; A[j] = A[i];
0007       } //assert: quit with i == j
0008       A[i] = pivot; // A[0,i) <= A[i] <= A(i, n)
0009       if ( k <= i ) hi = i - 1;
0010       if ( i <= k ) lo = i + 1;
0011    } //A[k] is now a pivot
0012 }

linearSelect

基本上没听了TAT这个

算法

性能分析

复杂度

我的实现

quickSort.h

#pragma once
#include "partition.h"
using Rank = int;
template <typename T>
void quickSort(T* _elem, Rank lo, Rank hi) {
	if (hi - lo < 2) return;
	T mi = partition(_elem, lo, hi - 1);
	quickSort(_elem, lo, mi);
	quickSort(_elem, mi + 1, hi);
}

partition.h

#pragma once
#include "quickSort.h"
#include<iostream>
using Rank = int;
template <typename T>//partitionLRU版本，我的最爱
Rank partition(T* _elem, Rank lo, Rank hi) {
	std::swap(_elem[lo], _elem[lo + rand() % (hi - lo + 1)]);
	T pivot = _elem[lo];
	int mi = lo;

	for (int k = lo + 1; k <= hi; k++)//k <= hi 而不是k < hi，第一次写写错了
		if (_elem[k] < pivot)         //因为传进来的时候已经hi-1了
			std::swap(_elem[k], _elem[++mi]);
	
	std::swap(_elem[lo], _elem[mi]);
	return mi;
	
}

quickSelect.h

#pragma once
using Rank = int;
#include <iostream>;
template <typename T>
void quickSelect(T* A,int capacity ,Rank k) {
	//std::cout << sizeof(A) / sizeof(A[0]) - 1 << std::endl;
	for (Rank lo = 0, hi = capacity-1 ; lo < hi;) {
		Rank i = lo, j = hi; T pivot = A[lo];
		while (i < j) {
			while (i < j && pivot <= A[j]) j--;
			A[i] = A[j];
			while (i < j && A[i] <= pivot) i++;
			A[j] = A[i];
		}//assert i == j; 快排中partition的LUR版本
		A[i] = pivot;
		if (k <= i)hi = i - 1;
		if (i <= k)lo = i + 1;
	}//A[k] is now a pivot
}

main.cpp

#include <iostream>
#include "quickSort.h"
#include "qucikSelect.h"
using namespace std;
int main() {
	int *test =new int[20];
	for (int i = 0; i < 20; i++) {
		test[i] = rand() % 88 + 1;//随机生成0-87的随机数，再加上1也就是
		if (i < 19)				  //随机生成1-88的随机数
			std::cout << test[i] << " ";
		else
			std::cout << test[i] << std::endl;
	}
							 //1 4 13 18 20 35 39 42 50 52 55 61 63 69 74 74 74 76 76 87
	//quickSort(test, 0, 20);//默认规范，左闭右开
	quickSelect(test,20 ,5);//1 4 18 13 20 35 39 42 55 61 74 74 50 74 87 52 76 63 76 69
							//至少秩为5时的35是在正确的位置
	for (int i = 0; i < 20; i++) {
		std::cout << test[i] << " ";
	}
}