// 找到返回索引,找不到返回-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; }
递归函数特点:
写递归函数注意点:
递归问题的思考是水平方向上的,递归问题的执行是竖直方向上的
// 函数功能:在[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)
在递的过程中什么都不做,在归的过程中就进行合并排序
最后一个非叶子节点计算公式:(n-1)/2
入堆: 入堆只能从堆底入,然后进行调堆
出堆: 出堆只能从堆顶出,然后进行调堆
从堆顶出元素后,先将堆底元素放到堆顶,然后进行下沉:不断地将值大的孩子节点上调,自己下沉,直到没有孩子节点为止(即当前下标大于(n-1)/2
)
调堆的时间复杂度都是树的高度:O(logn)
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;}); // 不报错
从最后一个内部节点开始调堆,使得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 } }
不稳定,只有两个相同元素能建立起比较关系的时候才有机会稳定。
在堆排序中,相同的值如果处于不同的子树,这两个值就无法比较,不稳定
总结:
数据量比较大,且均匀的时候,快排排序>归并排序>希尔排序>堆排序
部分源码
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; } } }
_Ideal
控制递归深度
冒泡会导致比较和交换次数过多,选择排序的比较次数也很多,在基本逆序的情况下,插入排序和快排的时间复杂度是O(n^2),不了解数列特征的时候选择稳定的堆排序O(log2n)
考察空间复杂度,归并排序O(n),此时肯定需要使用磁盘IO,效率很低。快速排序递归的空间复杂度为O(log2n)
外排序算法过程:
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表示数据的位数,空间复杂度主要是和桶相关