快速排序的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 快速排序是一种不稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动 快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为...
#include <iostream> using namespace std;const int N = 1e6 + 10; int n; int q[N], tmp[N];void merge_sort(int q[], int l, int r) {if (l >= r) {return;} int mi...
#include <iostream>using namespace std;const int N = 1e6 + 10; int n = 0; int q[N];void quick_sort(int q[], int l, int r) {if (l >= r) {return; // 判断边界，如果区间里面只有一个数或者没有数就直接返回} int x = q[l], i = l - 1, j = r + 1; // 取分节点x， 两个指针while (i < j) {do {i++;} while (q[i] < x); // 当q[i]的值大于等于x的时候则停止指针移动do {j--;} while(q[j] > x); // 当q[j]的值小于等于x的时...
性能分析：时间复杂度：O(n^2)空间复杂度：O(1)#include<iostream> #include<vector> using namespace std;int main() {// 思想：// 在原始待排序序列上操作;// 将原始待排序序列分成无序区和有序区两部分;// 初始状态下整个原始序列为无序区,每遍历一遍就浮现出无序区最大的元素放在有序区;// 随着遍历,最终无序区长度变为0,整个原始序列变为有序序列.int data[] = { 1,3,5,2,7,8,9,6,0 };// 设置一个监控位,用于记录是否无序区碰...
基本思想 冒泡排序（Bubble Sort）是一种交换排序，它的基本思想是: 两两比较相邻记录关键字，如果反序则交换，直到没有反序的记录为止。 冒泡排序算法 #include <iostream> using namespace std;int main() {int a[8]{ 11,2,5,23,6,8,33,12 };for (int i = 0; i < 8; i++){for (int j = 7; j > i; j--){if (a[j] > a[j - 1]){int tmp = a[j - 1];a[j - 1] = a[j];a[j] = tmp;}}}for (int i = 0; i < 8; i++)cout << a[i] << " ";s...
一 总述 排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括： 基数排序 排序原理 基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个...
首先构造cmp比较函数或结构体，再用一个vector容器将map转换为vector，最后用sort进行排序。 bool cmp(const pair<string, int> &a, const pair<string, int> &b)//也可以用结构体{return a.second > b.second; } int main(){vector<pair<string,int>> mpp(mp.begin(),mp.end());//用map对该容器初始化sort(mpp.begin(),mpp.end(),cmp);//用sort排序cout<<mpp.begin()->first; }
class Solution { public:/******************************************************************** 直接插入排序 数组前面维持一个有序区，每次从后面的无序区里选一个数插入到前面的有序区，直至全部已排序 *********************************************************************/ void insertsort(vector<int>& nums) {for (int i = 1; i < nums.size(); i++){//找到插入位置int insertpos = 0, insertval = nums[i];while (n...
随手实现, 直接上代码, 如有错误疏漏欢迎指正 1 //折半插入排序 : 时间复杂度为n^22 void binary_insert_sort(std::vector<size_t> &arr)3 {4 for (size_t idx = 0; idx < arr.size(); ++idx)5 {6 size_t curr_val = arr[idx]; //当前索引值7 size_t curr_pos = idx; //当前索引初始位置8 size_t compare_pos = curr_pos / 2; //比较索引初始位置9 bool needInsert = false; ...
1 #include <iostream>2 #include <climits>3 #include <string>4 #include <cstring>5 #include <vector>6 #include <cmath> 7 using namespace std;8 int main() 9 { 10 string line1 = "We were her pride of 10 she named us:";11 string line2 = "Benjamin, Phoenix, the Prodigal";12 string line3 = "and perspicacious pacific Suzanne";13 string sentence = line1 + " " + line2 + " " + line3;...
假设有如下数组： A = {15,10,6,1} B = {1} C = {20,5} 对数组进行从小到大的排序，随机取一个数组里的值记为BaseValue， 然后将所有小于BaseValue值放在左边，所有大于BaseValue的放在右边（相等的就不动了）。 对于数组B来说不用进行操作就完成了目标，对于C来说进行一次上述操作就能完成排序。 但是对A数组来说就不是那么简单了。 我们用递归的方式来对数组进行拆分，直到数组长度<= 1（也就是B数组一样的状态） 1.先选择数组第...
题目地址：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/ 题目描述 统计一个数字在排序数组中出现的次数。 题目示例 示例 1: 输入: nums = [5,7,7,8,8,10], target = 8输出: 2示例 2: 输入: nums = [5,7,7,8,8,10], target = 6输出: 0 解题思路 思路1：最简单的思路是遍历nums数组，然后如果遇到与目标值相同则计数器cnt++，否则，继续遍历，直到数组末尾。 思路2：二分查找，不难看成，题目给...
0、算法概述 0.1 算法分类 十种常见排序算法可以分为两大类：比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。 0.2 算法复杂度0.3 相关概念稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。 不稳定：如果a原本在...
#include<iostream> using namespace std; int main() {//插入排序理解int arr[] = { 56, 12, 3, 7, 11,55,456,123,55,44,6,7,8,999,1 }; //定义一个int类型数组 int m = 0;for (int i = 0; i < sizeof(arr)/sizeof(int); i++) //定义一个for循环，表示外层需要循环的次数{for (int j = i ; j > 0; j--) //定义一个循环，每次将前数组第i个元素内的元素从后向前进行比大小，{m++;if (arr[j] < arr[j - 1]) //如果前一...
1. Merge Sort / 归并排序/* Divide and conquer* 将一个数组中的两个相邻有序区间合并成一个** 参数说明：* A -- 包含两个有序区间的数组* lo -- 第1个有序区间的起始地址。* mi -- 第1个有序区间的结束地址。也是第2个有序区间的起始地址。* hi -- 第2个有序区间的结束地址。*/1 void merge(int A[],int lo,int hi,int mi){2 //以mi为界、各自有序癿子向量[lo, mi)和[mi, hi) 3 int tem...