重刷搜索排序算法

重刷搜索排序算法

文章目录

​​一、二分搜索算法​​

​​1. 非递归代码​​​​2. 递归代码​​

​​二、冒泡排序算法​​​​三、选择排序​​​​四、插入排序​​​​五、希尔排序​​​​六、快速排序​​​​七、归并排序​​​​八、堆​​

​​1. 二叉堆的概念​​​​2. 调堆​​​​3. 用堆实现优先级队列​​​​4. 堆排序​​

​​九、STL中的sort源码解析​​​​十、基数排序​​

一、二分搜索算法

1. 非递归代码

// 找到返回索引，找不到返回-1int binary_search(const vector& 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. 递归代码

递归函数特点：

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

写递归函数注意点：

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

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

// 函数功能：在[left, right]区间内搜索val，找到返回下标，找不到返回-1int recur_binary_search(const vector& 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& 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& 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& 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& 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& nums, int l, int r){ int val = nums[l]; while(l < r){ while(l < r && nums[r] > val){ r--; } if(l < r){ nums[l] = nums[r]; l++; } while(l < r && nums[l] < val){ l++; } if(l < r){ nums[r] = nums[l]; r--; } } nums[l] = val; return l;}// 这是一个递归函数，主要功能是使得区间[begin, end]内的数据有序void quick_sort(vector& 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& 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& 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& 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& 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& 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& 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; PriorityQueue(int cap = 20, Comp comp = greater()) :_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 - 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-() << " "; q.pop(); } cout << endl; return 0;}

写法1：

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

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

写法2：

function> comp = less();PriorityQueue q(comp); // 不报错

写法3：

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

4. 堆排序

从最后一个内部节点开始调堆，使得0号节点到第一个内部节点​​(n-1)/2​​全都满足堆性质，n表示最后一个节点的索引

堆顶元素和最后一个元素交换，则完成一个元素的排序任务

下一次排序，则少考虑一个元素

// 使索引为cur的节点满足堆性质，当前容器中需要排序的元素数量为sizevoid sift_down(vector& 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& 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 }}

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

总结：

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

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

九、STL中的sort源码解析

部分源码

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

快速排序不是稳定的O(log2n)，最坏的情况会变成O(n^2)，可以通过改插入排序或者三数取中的方法改善情况恶化参考STL中sort的源码，可设置变量​​_Ideal​​控制递归深度递归太深可能导致函数调用开销过多，甚至栈溢出，程序崩溃若递归到已经快溢出了，还没排完，在sort中选择的是时间复杂度稳定的堆排序

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

考察空间复杂度，归并排序O(n)，此时肯定需要使用磁盘IO，效率很低。快速排序递归的空间复杂度为O(log2n)

外排序算法过程：

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

十、基数排序

void radix_sort(vector& vec) { if (vec.size() < 2) { return; } vector> 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& vec) { if (vec.size() < 2) { return; } // 生成20个桶，1-9号桶放负数，10-19号桶放正数 int bucket_num = 20; vector> 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表示数据的位数，空间复杂度主要是和桶相关

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。