c++史上最全算法详解，0基础可秒懂！（爆肝上万字）

这里推荐大家使用万能头文件#include

#include2.C++命名空间命名空间（Namespace）用于避免命名冲突，将全局作用域划分为不同的区域。标准库中的函数和对象位于std命名空间。

示例代码：

#includeusingnamespacestd;//c++命名空间intmain(){std::cout<<"Hello,World!"<

intmain(){//主函数体return0;}4.变量类型C++中有多种变量类型，包括整数、浮点数、字符等。以下是一些常见的变量类型及其范围：

ASCII码是字符编码系统，将字符映射到数字。以下是一些常见ASCII码的示例：

注释用于在代码中添加说明，不会被编译器执行。

//这是单行注释/*这是多行注释*/以上是C++语法基础的一些要点，可根据需要深入学习每个部分的详细知识。

C++中的顺序结构是指按照代码的顺序执行程序的过程。在顺序结构中，程序从上到下依次执行代码块，没有分支和循环。

#includeusingnamespacestd;intmain(){intx=10;inty=5;intz=x+y;cout<<"x+y="<

思路：我们可以先输入圆的半径，然后根据圆的面积公式πr2计算面积，并将结果输出到控制台。

代码如下：

#include#includeusingnamespacestd;intmain(){doubleradius,area;cout<<"请输入圆的半径："<>radius;area=M_PI*radius*radius;//使用cmath库中的M_PI常量计算π的值。cout<<"圆的面积为："<

#include#includeusingnamespacestd;intmain(){doublea,b,c,x1,x2;cout<<"请输入一元二次方程的系数a、b和c："<>a>>b>>c;doublediscriminant=b*b-4*a*c;//判别式的值。if(discriminant<0){//判别式小于0时方程无实数解。cout<<"方程无实数解。"<

C++中的分支结构是指程序在执行过程中根据条件判断选择不同的执行路径。分支结构通常使用if语句、switch语句等来实现。

#includeusingnamespacestd;intmain(){intx=10;if(x>5){cout<<"x大于5"<

思路：我们可以先输入一个整数，然后使用if语句判断该数是否为偶数，并输出相应的结果。

#includeusingnamespacestd;intmain(){intnum;cout<<"请输入一个整数："<>num;if(num%2==0){//判断是否为偶数。cout<<"该数是偶数。"<

#includeusingnamespacestd;intmain(){intyear;cout<<"请输入一个年份："<>year;if((year%4==0&&year%100!=0)||year%400==0){//判断是否为闰年。cout<<"该年是闰年。"<

C++中的循环结构是指程序在执行过程中根据循环条件重复执行一段代码块。循环结构通常使用for语句、while语句和do-while语句等来实现。

#includeusingnamespacestd;intmain(){intn;cout<<"请输入一个整数："<>n;for(inti=1;i<=n;i++){//从1到n的循环。cout<

思路：我们可以使用for语句实现从1到n的循环，每次循环将当前的数累加到总和中，最后输出总和。

#includeusingnamespacestd;intmain(){intn,sum=0;cout<<"请输入一个整数："<>n;for(inti=1;i<=n;i++){//从1到n的循环。sum+=i;//将当前的数累加到总和中。}cout<<"1到"<

#includeusingnamespacestd;intmain(){intn,f1=0,f2=1,fn;cout<<"请输入一个整数n："<>n;for(inti=0;i

#includeusingnamespacestd;intmain(){intarr[5]={1,2,3,4,5};//定义一个包含5个整数的数组。for(inti=0;i<5;i++){//循环访问数组元素。cout<

思路：我们可以定义两个变量，分别用于存储数组中的最大值和最小值。然后遍历数组，比较每个元素与最大值和最小值的值，更新最大值和最小值。

#includeusingnamespacestd;intmain(){intarr[]={3,7,2,9,1};//定义一个包含5个整数的数组。intn=sizeof(arr)/sizeof(arr[0]);//计算数组元素的个数。intmax=arr[0];//假设第一个元素为最大值。intmin=arr[0];//假设第一个元素为最小值。for(inti=1;imax){//如果当前元素大于最大值。max=arr[i];//更新最大值。}if(arr[i]

#includeusingnamespacestd;intmain(){intarr[]={1,2,3,4,5};//定义一个包含5个整数的数组。intn=sizeof(arr)/sizeof(arr[0]);//计算数组元素的个数。for(inti=0;i

以上，我们通过2个例题展示了数组的基本应用，包括如何计算数组中的最大值和最小值、如何将数组中的所有元素乘以2。

然而，请注意，对于大规模的数据处理，通常建议使用其他数据结构，例如向量（std::vector），因为它更灵活，并且可以动态地调整大小。

总的来说，数组在C++中是一种基本且重要的数据结构，理解并掌握其使用方法对于编写高效、可靠的代码至关重要。

C++中的字符串是一个非常重要的数据类型，它提供了许多操作来处理文本数据。下面我将为你提供字符串的基本操作和三个例题的详细思路和正确代码，最后进行总结。

stringstr1="Hello,";stringstr2="world!";stringstr3=str1+str2;//使用+运算符拼接字符串字符串的长度获取

stringstr="Hello,world!";intlength=str.length();//获取字符串长度字符串的查找

stringstr="Hello,world!";size_tpos=str.find("world");//查找子串的位置，如果不存在则返回一个特殊值（string::npos）表示结束循环的条件。这里使用了size_t类型来存储位置值。字符串的替换

正确代码：

在处理字符串时，我们可能会遇到一些特殊的问题，比如检查回文字符串、替换字符串中的字符和截取字符串中的子串等。针对这些问题，我们可以使用C++提供的算法和函数来实现。比如，我们可以使用双指针法或循环法来检查一个字符串是否是回文字符串；可以使用替换函数来替换字符串中的特定字符；可以使用切片操作来截取字符串中的子串。

在实际应用中，我们需要注意选择合适的算法和数据结构来处理字符串，以提高程序的效率和可读性。此外，我们还应该注意输入的合法性，确保程序能够正确处理各种输入情况。同时，我们还应该注意程序的健壮性，尽可能地减少程序中的错误和异常情况。

总之，C++中的字符串操作是一个重要的知识点，可以帮助我们更好地处理文本数据。在实际应用中，我们应该根据具体需求选择合适的算法和数据结构来处理字符串，以提高程序的效率和可读性。同时，我们也应该注意输入的合法性和程序的健壮性，确保程序能够正确地处理各种输入情况和异常情况。

函数是C++程序的基本组成单位，用于实现特定的功能。以下是函数的一些基本操作和核心代码实例：

intmain(){printHello();//调用函数printHello()return0;}除了普通函数外，递归函数是一种特殊的函数，它直接或间接地调用自身来解决问题。递归函数的基本操作包括定义递归终止条件、编写递归函数体和调用递归函数。

定义递归终止条件：递归函数必须有一个或多个终止条件，当满足这些条件时，递归将停止。终止条件是递归函数的出口，确保递归不会无限进行下去。编写递归函数体：递归函数体中必须包含对递归的调用，以便处理更小的子问题。函数体中还需要包含一些逻辑来处理当前问题，并将当前问题的结果与子问题的结果结合起来，以获得最终答案。调用递归函数：在程序中，需要有一个或多个地方调用递归函数，以便开始递归过程。这些调用可以是直接或间接的，具体取决于问题的性质和所需解决的问题的复杂性。递归函数通常用于解决具有递归性质的问题，例如树、图和集合等数据结构的遍历，以及分治算法等。通过将问题分解为更小的子问题，递归函数能够简化问题的解决过程，并使代码更加简洁和易于理解。然而，使用递归函数需要注意避免栈溢出和正确处理终止条件，以确保程序的正确性和效率。

以下是一个简单的C++程序，其中包含了一个主函数main()和一个自定义函数printHello()：

#includeusingnamespacestd;//自定义函数：打印Hello,world!voidprintHello(){cout<<"Hello,world!"<

题目描述：编写一个C++程序，实现交换两个整数的值。要求使用函数来实现交换操作。思路分析：首先定义两个整数变量a和b，然后定义一个函数swap()来交换它们的值。在主函数中调用swap()函数，并输出交换后的结果。AC代码：

思路分析：我们可以使用递归或迭代的方式来计算斐波那契数列的第n项。这里我们选择迭代的方式，因为它更加高效且不易出错。我们定义两个变量f1和f2分别表示斐波那契数列的前两项，初始值为0和1。然后，我们使用一个循环来计算第n项的值，直到达到所需的项数。

递推AC代码：

#includeintfibonacci(intn){if(n<=1){returnn;}intf1=0,f2=1;for(inti=2;i<=n;++i){inttemp=f1+f2;f1=f2;f2=temp;}returnf2;}intmain(){intn=10;//要计算的斐波那契数列的项数intresult=fibonacci(n);//调用fibonacci()函数计算第n项的值std::cout<<"斐波那契数列的第"<

当然，递归版本的斐波那契数列计算代码如下：

#includeintfibonacci(intn){if(n<=1){returnn;}else{returnfibonacci(n-1)+fibonacci(n-2);}}intmain(){intn=10;//要计算的斐波那契数列的项数intresult=fibonacci(n);//调用fibonacci()函数计算第n项的值std::cout<<"斐波那契数列的第"<

#includeintn;//假设n<=1000intmark[1005];intfibonacci(intn){if(mark[n]!=0)returnmark[n];//记忆化if(n<=1)returnn;else{intres=fibonacci(n-1)+fibonacci(n-2);mark[n]=res;returnres;}}intmain(){std::cin>>n;intresult=fibonacci(n);std::cout<<"斐波那契数列的第"<

#include#include//定义结构体structPerson{std::stringname;intage;doubleheight;};intmain(){//创建结构体实例Personperson1;//初始化结构体成员person1.name="John";person1.age=25;person1.height=175.5;//输出结构体成员std::cout<<"Name:"<

题目描述：定义一个结构体存储学生的信息，包括学生的姓名、学号和三门课程的成绩。编写一个程序，输入5个学生的信息，然后输出每个学生的总分。

思路：1.定义一个结构体Student，包括成员变量name（姓名）、id（学号）和数组grades（存储三门课程的成绩）。2.定义一个函数calculateTotal，该函数接受一个Student类型的参数，计算该学生的总分，并返回总分。3.在主程序中，定义一个包含5个Student对象的数组，输入每个学生的信息。4.遍历数组，调用calculateTotal函数计算每个学生的总分，输出结果。

AC代码：

#include#include//定义结构体存储学生信息structStudent{std::stringname;//学生姓名intid;//学号intgrades[3];//三门课程的成绩};//计算学生总分的函数intcalculateTotal(constStudent&student){inttotal=0;for(inti=0;i<3;++i){total+=student.grades[i];}returntotal;}intmain(){constintnumStudents=5;Studentstudents[numStudents];//输入学生信息for(inti=0;i>students[i].name;std::cout<<"ID:";std::cin>>students[i].id;std::cout<<"Gradesforthreecourses:"<>students[i].grades[j];}}//输出每个学生的总分for(inti=0;i

题目：给定学生结构体（姓名、年龄），求所有学生的平均年龄。

思路：遍历结构体数组，累加年龄，然后除以学生人数。

#include#includestructStudent{std::stringname;intage;};intmain(){intn;std::cin>>n;std::vectorstudents(n);for(inti=0;i>students[i].name>>students[i].age;}intsumAge=0;for(constauto&student:students){sumAge+=student.age;}doubleaverageAge=static_cast(sumAge)/n;std::cout<<"AverageAge:"<

思路：遍历结构体数组，记录最大年龄。

在一些需要处理大量数据的场景，使用结构体可以帮助简化代码结构。通过定义合适的结构体，可以使代码更易读，减少冗余。

在排序或比较对象较为复杂的情况下，结构体提供了一种便捷的方式。可以使用std::sort等函数，通过自定义比较函数或Lambda表达式，灵活地进行排序。

当题目中涉及到模拟实体对象的场景时，结构体是一种自然的选择。例如，模拟一个游戏中的角色，结构体可以包含角色的属性和状态。

可读性提升：结构体使得代码更加直观，通过成员变量的命名，可以清晰地了解数据的含义，提升了代码的可读性。

灵活性：结构体在定义时可以包含各种类型的数据，使得其在不同场景下的应用更加灵活。

代码简化：在处理多属性的数据时，使用结构体可以减少代码的冗余，使得代码更加简洁。

排序与比较：结构体可以方便地进行排序与比较，对于需要处理大量数据的竞赛题目非常实用。

问题：乌龟棋

题目与简单思路：题目中需要模拟一个棋盘，每个格子上有不同的得分。可以使用结构体表示每个格子的坐标和得分，方便进行模拟操作。最后按照规则计算得分即可。

#include#include#includestructCell{intx,y,score;};boolcompareCell(constCell&a,constCell&b){returna.score>b.score;}intmain(){intn,m,k;std::cin>>n>>m>>k;std::vectorcells;for(inti=0;i>cell.x>>cell.y>>cell.score;cells.push_back(cell);}std::sort(cells.begin(),cells.end(),compareCell);inttotalScore=0;for(inti=0;i

C++模拟详解

作用：模拟是通过编写程序，按照问题描述的规则逐步执行操作，最终得到问题的答案。在算法竞赛和编程中，模拟常用于解决具体问题的实现。

应用范围：模拟广泛应用于模拟真实场景、计算机系统行为、物理过程等方面。在算法竞赛中，常用于实现问题的特定规则和操作。

题目背景：给定一个整数，要求将其数字翻转。

数据范围：输入整数在[-2^31,2^31-1]范围内。

详细思路：1.判断输入数字的正负。2.将数字转为字符串，对字符串进行翻转。3.转回整数，注意溢出情况。

数据范围：字符串长度不超过1000。

详细思路：1.从字符串末尾开始逐位相加，注意进位。2.使用两个指针分别指向两个字符串的末尾。3.处理两字符串长度不等的情况。

classSolution{public:stringaddStrings(stringnum1,stringnum2){inti=num1.size()-1,j=num2.size()-1,carry=0;stringresult="";while(i>=0||j>=0||carry>0){intx=i>=0num1[i--]-'0':0;inty=j>=0num2[j--]-'0':0;intsum=x+y+carry;carry=sum/10;result=to_string(sum%10)+result;}returnresult;}};例题3：报数题目背景：报数序列是一个整数序列，第n项的描述如下：”1,11,21,1211,111221,…”。

数据范围：1≤n≤30。

详细思路：1.从第一个数开始，依次生成下一个数。2.对上一个数进行遍历，统计相同数字的个数。3.将统计结果与数字拼接，作为下一个数。

classSolution{public:stringcountAndSay(intn){if(n==1)return"1";stringprev=countAndSay(n-1);stringresult="";intcount=1;for(inti=0;i

拓展：1.学习更复杂的模拟算法，如模拟物理过程、模拟系统行为等。2.探索其他算法领域，如动态规划、贪心算法等。3.参与实际项目，提高问题抽象和解决能力。

高精度是争对c++本身变量变量无法运算的情况而产生的算法。以下是第0节的各个变量的范围：|类型|字节|范围|示例代码||-------------|------|----------------------------------------------------|---------------------||int|4|-2,147,483,648到2,147,483,647|intnum=42;||unsignedint|4|0到4,294,967,295|unsignedintx=10;||short|2|-32,768到32,767|shorts=32767;||long|4|-2,147,483,648到2,147,483,647|longl=123456789;||longlong|8|-9,223,372,036,854,775,808到9,223,372,036,854,775,807|longlongll=123456789012345;||float|4|3.4e-38到3.4e+38|floatf=3.14f;||double|8|1.7e-308到1.7e+308|doubled=3.14;||char|1|-128到127或0到255|charch='A';||bool|1|true或false|boolflag=true;|

假设我们做简单的$a+b$问题，正常代码是这样的：

#includeusingnamespacestd;inta,b;intmain(){cin>>a>>b;cout<

高精度加法是针对大整数的加法运算，通常是在数字超出了语言的整数表示范围时使用。在C++中，可以通过字符串来表示大整数，然后进行高精度加法操作。以下是高精度加法的基本原理：

表示大整数：将大整数按位逆序存储在字符串中，即个位存储在字符串的首位。这样方便从低位到高位进行遍历和计算。

对齐操作：如果两个大整数长度不同，需要在短的整数高位补零，使得两个整数的位数相同。

逐位相加：从低位到高位，逐位相加，将结果存储在一个新的字符串中。同时，考虑进位的情况。

处理最高位进位：在计算完所有位数后，检查最高位是否有进位，如果有，需要将进位添加到结果的最高位。

下面是一个简单的C++代码示例，实现高精度加法，这个代码可以完全替代上面的建议代码：

#include#includeusingnamespacestd;stringadd(stringnum1,stringnum2){intcarry=0;stringresult="";//对齐操作while(num1.length()=0;i--){intdigit_sum=(num1[i]-'0')+(num2[i]-'0')+carry;carry=digit_sum/10;result=char(digit_sum%10+'0')+result;}//处理最高位进位if(carry>0)result=char(carry+'0')+result;returnresult;}intmain(){stringnum1="123456789012345678901234567890";stringnum2="987654321098765432109876543210";stringsum=add(num1,num2);cout<<"Sum:"<

接下来就是高精度乘法：

例如，数值123456789在字符串中表示为“987654321”。

逐位相乘：高精度乘法的核心是逐位相乘。从低位到高位，将一个数字的每一位与另一个数字的每一位相乘。乘积保存在一个新的数组或字符串中，并需要考虑到可能的进位。

对齐相加：将所有逐位相乘的结果相加。对齐相加是逐位相加的过程，需要考虑到可能的进位。每一位相加的结果除以10得到当前位的数字，余数作为当前位的结果，而商则作为进位被加到下一位的计算中。

处理进位：在逐位相乘和对齐相加的过程中，需要处理进位。进位是由乘法和加法中某一位的计算产生的，需要被加到相邻的高位上。

下面是一个具体的高精度乘法的C++示例：

#include#includeusingnamespacestd;stringmultiply(stringnum1,stringnum2){intm=num1.size();intn=num2.size();vectorresult(m+n,0);//逐位相乘for(inti=m-1;i>=0;i--){for(intj=n-1;j>=0;j--){intmul=(num1[i]-'0')*(num2[j]-'0');intsum=mul+result[i+j+1];//当前位的数字与乘积之和result[i+j+1]=sum%10;//当前位的数字result[i+j]+=sum/10;//进位}}//转换为字符串stringresultStr;for(intdigit:result){if(!(resultStr.empty()&&digit==0)){resultStr.push_back(digit+'0');}}returnresultStr.empty()"0":resultStr;}intmain(){stringnum1="123456789";stringnum2="987654321";stringproduct=multiply(num1,num2);cout<<"Product:"<

高精度除法虽然实用度较小，但我也讲一下吧。

高精度除法是处理大整数的除法运算，通常用于解决数字超出语言整数表示范围的情况。在C++中，我们可以使用字符串来表示大整数，然后实现高精度除法。以下是高精度除法的基本原理：

表示大整数：大整数通常用字符串来表示，其中字符串中的每个字符表示一个数字位，字符串的顺序是从低位到高位的逆序，即个位在字符串的首位。

逐位相除：从高位到低位，逐位进行相除。每一步中，将被除数的当前位与除数相除，得到商和余数。商作为当前位的结果，余数作为下一位的被除数。

对齐取商：将每一位的商拼接起来，得到最终的商。

处理余数：如果余数不为零，可以选择继续除以下一位，或者将余数作为小数部分添加到结果中。

下面是一个简单的C++代码示例，实现高精度除法：

#include#includeusingnamespacestd;stringdivide(stringnum,intdivisor){intn=num.size();stringquotient;intremainder=0;for(inti=0;i

计算高精度开根涉及到数值计算的数学问题，特别是平方根的计算。以下是一个基于牛顿迭代法的高精度开根算法的详细解释：

设被开方数为num，初始猜测值x0为num/2。

迭代公式为xi=(xi+num/xi)/2。

具体来说，对于每次迭代，计算xi的新值，然后用新值替代旧值，直到xi的值不再发生显著变化。

即判断abs(xi-xi-1)

C++代码实现：

下面是一个简单的C++代码示例，使用牛顿迭代法计算高精度平方根：

#include#include#includeusingnamespacestd;stringadd(stringnum1,stringnum2){//实现高精度加法//...}stringdivideByTwo(stringnum){//实现高精度除以2//...}stringsqrt(stringnum){stringx=num;stringy="0";stringtwo="2";//设置收敛阈值epsilondoubleepsilon=1e-12;while(abs(stod(x)-stod(y))>epsilon){y=x;x=divideByTwo(add(x,divideByTwo(num,x)));//x=(x+num/x)/2}returnx;}intmain(){stringnum="123456789";stringresult=sqrt(num);cout<<"SquareRootof"<

给定一个整数n，计算n!的值，其中n!=n*(n-1)*(n-2)*...*2*1。

使用字符串表示大整数，然后按照乘法的方法进行计算。使用一个数组或字符串保存当前的结果，逐位进行乘法和进位的处理。

#include#includeusingnamespacestd;stringmultiply(stringnum1,stringnum2){//实现高精度乘法//...}stringfactorial(intn){stringresult="1";for(inti=2;i<=n;i++){result=multiply(result,to_string(i));}returnresult;}intmain(){intn;cout<<"Enteranumber:";cin>>n;stringresult=factorial(n);cout<

使用字符串表示大整数，按照递推公式计算斐波那契数列的值。需要处理大整数的加法。

#include#includeusingnamespacestd;stringadd(stringnum1,stringnum2){//实现高精度加法//...}stringfibonacci(intn){if(n==0)return"0";if(n==1)return"1";stringa="0";stringb="1";for(inti=2;i<=n;i++){stringtemp=b;b=add(a,b);a=temp;}returnb;}intmain(){intn;cout<<"Enteranumber:";cin>>n;stringresult=fibonacci(n);cout<<"F("<

给定一个整数n（$1\leqn\leq10^9$），你需要统计数字k在上述数字序列中出现的次数。

一行两个整数n和k，表示要统计的数字和目标数字。

一个整数，表示数字k在序列中出现的次数。

151示例输出8提示在序列中，数字1出现了8次（1,10,100,1000,10000,100000,1000000,10000000）。

观察序列可以发现，数字k在这个序列中出现的次数可以通过统计序列的每一位上k出现的次数来得到。具体地，设数字n有d位，那么从高位到低位，对于每一位i，数字k在这一位上出现的次数为n/(10^i)*10^(i-1)。最后，还需要统计最高位的情况。

#includeusingnamespacestd;intcountDigitK(intn,intk){intcount=0;longlongbase=1;//初始为最低位的位数while(n/base>0){intcurDigit=(n/base)%10;//当前位的数字inthigherDigits=n/(base*10);//高位数字if(curDigit>n>>k;intresult=countDigitK(n,k);cout<

1.O(n2)的排序算法

冒泡排序

选择排序

插入排序

2.O(nlogn)的排序算法

归并排序

快速排序

堆排序

3.线性的排序算法

计数排序

桶排序

基数排序

各种排序的具体信息

###冒泡排序（BubbleSort）

冒泡排序（BubbleSort）是一种基础的交换排序。

冒泡排序之所以叫冒泡排序，是因为它每一种元素都像小气泡一样根据自身大小一点一点往数组的一侧移动。

算法步骤如下：

比较相邻的元素。如果第一个比第二个大，就交换他们两个；

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数；

针对所有的元素重复以上的步骤，除了最后一个；

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

图示如下：

voidbubbleSort(vector&a){intlen=a.size();for(inti=0;ia[j+1]){swap(a[j],a[j+1]);//不满足偏序，交换}}}}还有一种假的写法就是保证第一个最小，第二个次小，比较的是i和j，虽然也是对的，有点像选择排序，但也不是。其不是冒泡排序

选择排序（Selectionsort）是一种简单直观的排序算法。

选择排序的主要优点与数据移动有关。

如果某个元素位于正确的最终位置上，则它不会被移动。

选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

选择排序的算法步骤如下：

在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；

然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；

以此类推，直到所有元素均排序完毕。

voidselectionSort(vector&a){intlen=a.size();for(inti=0,minIndex;i

插入排序（Insertionsort）是一种简单直观的排序算法。

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序的算法步骤如下：

从第一个元素开始，该元素可以认为已经被排序；

取出下一个元素，在已经排序的元素序列中从后向前扫描；

如果该元素（已排序）大于新元素，将该元素移到下一位置；

重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

将新元素插入到该位置后；

重复步骤2~5。

voidinsertionSort(vector&a){intlen=a.size();for(inti=0,j,temp;i=0&&a[j]>temp){a[j+1]=a[j];j--;}a[j+1]=temp;}}希尔排序（ShellSort）希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；

但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

步长的选择是希尔排序的重要部分。

只要最终步长为1任何步长序列都可以工作。

算法最开始以一定的步长进行排序。

然后会继续以一定步长进行排序，最终算法以步长为1进行排序。

当步长为1时，算法变为普通插入排序，这就保证了数据一定会被排序。

希尔排序的算法步骤如下：

定义一个用来分割的步长；

按步长的长度K，对数组进行K趟排序；

不断重复上述步骤。

voidshell_Sort(vector&a){intlen=a.size();for(intgap=len/2;gap>0;gap/=2){for(inti=0;i=0&&a[preIndex]>temp){a[preIndex+gap]=a[preIndex];//被替换preIndex-=gap;//向下走一步}a[preIndex+gap]=temp;//恢复被替换的值}}}}}快速排序（QuickSort）快速排序（Quicksort），又称划分交换排序（partition-exchangesort）。

快速排序（Quicksort）在平均状况下，排序n个项目要O(nlogn)次比较。在最坏状况下则需要O(n^2)次比较，但这种状况并不常见。事实上，快速排序O(nlogn)通常明显比其他算法更快，因为它的内部循环（innerloop）可以在大部分的架构上很有效率地达成。

快速排序使用分治法（Divideandconquer）策略来把一个序列分为较小和较大的2个子序列，然后递归地排序两个子序列。

快速排序的算法步骤如下：

挑选基准值：从数列中挑出一个元素，称为“基准”（pivot）；

分割：重新排序序列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成；

递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

递归到最底部的判断条件是序列的大小是零或一，此时该数列显然已经有序。

其实说白了就是将两个已经排序的序列合并成一个序列的操作。

并归排序有两种实现方式

第一种是自上而下的递归，算法步骤如下：

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

设定两个指针，最初位置分别为两个已经排序序列的起始位置；

比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

重复步骤3直到某一指针到达序列尾；

将另一序列剩下的所有元素直接复制到合并序列尾。

voidmergeSort(vector&a,vector&T,intleft,intright){if(right-left==1)return;intmid=left+right>>1,tmid=left+right>>1,tleft=left,i=left;mergeSort(a,T,left,mid),mergeSort(a,T,mid,right);while(tleft=right||(tleft&a){intlen=a.size();vectorT(len);mergeSort(a,T,0,len);}迭代比起递归还是安全很多，太深的递归容易导致堆栈溢出。所以建议可以试下迭代实现，acm里是够用了

堆排序（Heapsort）是指利用二叉堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。

二叉堆是什么？

二叉堆分以下两个类型：

1.最大堆：最大堆任何一个父节点的值，都大于等于它左右孩子节点的值。

数组表示如下：

[10,8,9,7,5,4,6,3,2]

2.最小堆：最小堆任何一个父节点的值，都小于等于它左右孩子节点的值。

[1,3,2,6,5,7,8,9,10]

堆排序的算法步骤如下：

把无序数列构建成二叉堆；

循环删除堆顶元素，替换到二叉堆的末尾，调整堆产生新的堆顶。

voidadjustHeap(vector&a,inti,intlen){intmaxIndex=i;//如果有左子树，且左子树大于父节点，则将最大指针指向左子树if(i*2+1a[maxIndex])maxIndex=i*2+1;//如果有右子树，且右子树大于父节点和左节点，则将最大指针指向右子树if(i*2+2a[maxIndex])maxIndex=i*2+2;//如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。if(maxIndex!=i){swap(a[maxIndex],a[i]);adjustHeap(a,maxIndex,len);}}voidSort(vector&a){intlen=a.size();//1.构建一个最大堆for(inti=len/2-1;i>=0;i--)//从最后一个非叶子节点开始{adjustHeap(a,i,len);}//2.循环将堆首位（最大值）与末位交换，然后在重新调整最大堆for(inti=len-1;i>0;i--){swap(a[0],a[i]);adjustHeap(a,0,i);}}我这里用了递归写法，非递归也很简单，就是比较哪个叶子节点大，再继续for下去

计数排序的算法步骤如下：

找出待排序的数组中最大和最小的元素；

统计数组中每个值为i的元素出现的次数，存入数组C的第i项；

对所有的计数累加（从数组C中的第一个元素开始，每一项和前一项相加）；

反向填充目标数组：将每个元素i放在新数组的第C[i]项，每放一个元素就将C[i]减去1。

桶排序的算法步骤如下：

设置一个定量的数组当作空桶子；

寻访序列，并且把项目一个一个放到对应的桶子去；

对每个不是空的桶子进行排序；

从不是空的桶子里把项目再放回原来的序列中。

我觉得递归调用桶排序比较慢，这里直接用了sort函数，其实这个函数能决定这个算法的优劣，这些排序都是针对固定的序列的，可以自己尝试不同的算法去优化

size为1是，其实和计数排序是一样的，不过这里使用了辅助的空间，没有合并相同的，内存消耗要更大

voidbucketSort(vector&a,intbucketSize){intlen=a.size();if(len<2)return;intMin=a[0],Max=a[0];for(inti=1;ibucketArr[bucketCount];for(inti=0;i

工作原理是将所有待比较数值（正整数）统一为同样的数字长度，数字较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

基数排序的方式可以采用LSD（Leastsignificantdigital）或MSD（Mostsignificantdigital）。

LSD的排序方式由键值的最右边（最小位）开始，而MSD则相反，由键值的最左边（最大位）开始。

MSD方式适用于位数多的序列，LSD方式适用于位数少的序列。

基数排序、桶排序、计数排序原理都差不多，都借助了“桶”的概念，但是使用方式有明显的差异，其差异如下：

基数排序：根据键值的每位数字来分配桶；

桶排序：每个桶存储一定范围的数值；

计数排序：每个桶只存储单一键值。

LSD图示如下：

LSD实现如下：

注意不要用负数，用负数完全相反，正负都有可以都转换为正数

voidRadixSortSort(vector&a){intlen=a.size();if(len<2)return;intMax=a[0];for(inti=1;ibucketList[10];for(inti=0;i

稳定排序：如果a原本在b的前面，且a==b，排序之后a仍然在b的前面，则为稳定排序。

非稳定排序：如果a原本在b的前面，且a==b，排序之后a可能不在b的前面，则为非稳定排序。

原地排序：原地排序就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序。