目录
个人观点：
排序的概念：
排序的稳定性：
内排序与外排序：
概念：
排序用到的结构与函数：
代码：
最简单排序的实现：
举例：
代码：
时间复杂度:
冒泡排序：
举例：
代码：
时间复杂度：
在优化：
举例：
代码：
简单选择排序：
思想:
代码:
时间复杂度：
直接插入排序：
举例：
代码：
时间复杂度：
希尔排序：
分析：
举例：
推荐视频：
代码：
注意：
堆排序：
堆定义;
举例：
基本思想：
举例：
代码：
归并排序：
算法思想：
理解图解：
举例：
分析一下它的合并操作是如何进行的：
代码实现：
快速排序：
算法思想：
举例：
代码：
（仅代表个人）
对于我初学者来讲，排序这个章节我们注重的思想而不是用法（个人看法而言，因为我刷题量很少，对我来说sort现在够用），那么我们就先注重这些算法的内容思想。
排序的概念：排序的稳定性：通俗来讲就是相同的关键字，在排序之后，它们的前后关系不会变
举例
内排序是在整个排序过程中，待排序的所有记录全部被放置在内存中。
外排序是由于排序记录个数过多，不能同时防止在内存中，整个排序过程需要在内外存之间多次数据交换才能进行
对于内排序性能而言：
（1）时间性能
（2）辅助空间
（3）算法复杂性
内排序分为插入排序、交换排序、选择排序和归并排序
排序用到的结构与函数： 代码：
#includeusing namespace std;
const int N=1e3+10;
int n;
typedef struct{
int res[N];
int len=0;
}Sqlist;
void swaq(Sqlist*L,int i,int j){
int temp=L->res[i];
L->res[i]=L->res[j];
L->res[j]=temp;
}
int main(){
Sqlist L;
cin>>n;
for(int i=1;i>L.res[i];
L.len++;
}
cout< 它的基本思想就是相邻两两比较，有冒泡思想但不是冒泡排序
举例：
下标从1开始
代码：#includeusing namespace std;
const int N=1e3+10;
int n;
typedef struct{
int res[N];
int len;
}Sqlist;
void swaq(Sqlist*L,int i,int j){
int temp=L->res[i];
L->res[i]=L->res[j];
L->res[j]=temp;
}
void BubbleSort0(Sqlist*L){
for(int i=1;i<=L->len;i++){
for(int j=1;j<=L->len;j++){
if(L->res[i]>L->res[j])
swaq(L,i,j);
}
}
}
int main(){
Sqlist L;
cin>>n;
for(int i=1;i>L.res[i];
L.len++;
}
for(int i=1;i<=L.len;i++)cout< 时间复杂度高，O(n^2)
从后往前交换，则必定会把相对小的数向前移动，时间复杂度提高了
代码：#includeusing namespace std;
const int N=1e3+10;
int n;
typedef struct{
int res[N];
int len;
}Sqlist;
void swaq(Sqlist*L,int i,int j){
int temp=L->res[i];
L->res[i]=L->res[j];
L->res[j]=temp;
}
void Bubblesort(Sqlist*L){
for(int i=1;ilen;i++){
for(int j=L->len-1;j>=i;j--){
if(L->res[j]>L->res[j+1])
swaq(L,j,j+1);
}
}
}
int main(){
Sqlist L;
cin>>n;
for(int i=1;i>L.res[i];
L.len++;
}
Bubblesort(&L);
for(int i=1;i<=L.len;i++){
cout< O(n^2)，但是相对来说总归有优化
#includeusing namespace std;
const int N=1e3+10;
int n;
typedef struct{
int res[N];
int len;
}Sqlist;
void swaq(Sqlist*L,int i,int j){
int temp=L->res[i];
L->res[i]=L->res[j];
L->res[j]=temp;
}
void Bubblesort(Sqlist*L){
for(int i=1;ilen;i++){
bool flag=1;
for(int j=L->len-1;j>=i;j--){
if(L->res[j]>L->res[j+1])
swaq(L,j,j+1);
flag=0;
}
if(flag)
break;
}
}
int main(){
Sqlist L;
cin>>n;
for(int i=1;i>L.res[i];
L.len++;
}
Bubblesort(&L);
for(int i=1;i<=L.len;i++){
cout< 与冒泡排序差不多，只不过不是遇见小的就交换，而是每次循环遇到最小的才交换
代码:#includeusing namespace std;
const int N=1e3+10;
int n;
typedef struct{
int res[N];
int len;
}Sqlist;
void swaq(Sqlist*L,int i,int j){
int temp=L->res[i];
L->res[i]=L->res[j];
L->res[j]=temp;
}
void Selectsort(Sqlist*L){
int j,mn;
for(int i=1;ilen;i++){
mn=i;
bool flag=0;
for(j=i+1;j<=L->len;j++){
if(L->res[mn]>L->res[j]){
mn=j;
flag=1;
}
}
if(flag)
swaq(L,i,mn);
}
}
int main(){
Sqlist L;
cin>>n;
for(int i=1;i>L.res[i];
L.len++;
}
Selectsort(&L);
for(int i=1;i<=L.len;i++){
cout< O(n^2)，但是相对于冒泡排序，总归有一定的优化
直接插入排序： 举例：此时哨兵（L.res[0]）就起到了作用
#includeusing namespace std;
const int N=1e3+10;
int n;
typedef struct{
int res[N];
int len;
}Sqlist;
void swaq(Sqlist*L,int i,int j){
int temp=L->res[i];
L->res[i]=L->res[j];
L->res[j]=temp;
}
void Insertsort(Sqlist*L){
int j;
for(int i=2;i<=L->len;i++){
if(L->res[i]res[i-1]){
L->res[0]=L->res[i];
for(j=i-1;L->res[j]>L->res[0];j--)
L->res[j+1]=L->res[j];
L->res[j+1]=L->res[0];
}
}
}
int main(){
Sqlist L;
cin>>n;
for(int i=1;i>L.res[i];
L.len++;
}
Insertsort(&L);
for(int i=1;i<=L.len;i++){
cout< O(n^2)，但是时间效率更好点
希尔排序： 分析：希尔排序是在直接插入排序上的优化
直接插入排序的最好情况：{2,3,4,5,6}，时间复杂度为O（n）
最坏情况：{6,5,4,3,2}，时间复杂度为O（n^2）
希尔排序是将一个数组分为若干个子序列，然后各自排序然后合并，实现基本有序
基本有序，就是小的关键字基本在前面，大的关键字基本在后面
采用跳跃式分割策略。。。
举例：
排序算法：希尔排序【图解+代码】_哔哩哔哩_bilibili
代码：#includeusing namespace std;
const int N=1e3+10;
int n;
typedef struct{
int res[N];
int len;
}Sqlist;
void shellsort(Sqlist*L){
int i,j,k=0;
int lon=L->len;
do{
lon=lon/3+1;
for(i=lon+1;i<=L->len;i++){
if(L->res[i]res[i-lon]){
L->res[0]=L->res[i];
for(j=i-lon;j>0&&L->res[0]res[j];j-=lon){
L->res[j+lon]=L->res[j];
}
L->res[j+lon]=L->res[0];
}
}
}while(lon>1);
}
int main(){
Sqlist L;
cin>>n;
for(int i=1;i>L.res[i];
L.len++;
}
shellsort(&L);
for(int i=1;i<=L.len;i++){
cout< 增量序列的最后一个增量必须等于1才行
堆排序： 堆定义;其实就是特殊的完全二叉树
举例：
大顶堆，所有结点大于其左右孩子结点，小顶堆反之
基本思想：将待排序的序列构造成一个大顶堆。此时整个序列的大值就是堆顶的根结点
将它移走（其实就是将其与堆数组末尾元素交换，此时末尾元素就是大值），然后将剩余的n-1
个序列重新构造一个堆，这样就会得到n个元素中的次大值，反复执行，便能得到一个有序序列
举例：（建树）
是利用归并的思想实现的排序方法，通俗理解起来就是
对于一个无序的数组，先让子序列为1的序列两两归并，然后让子序列为2的序列两两归并，以此类推
理解图解：
举例：
通过一趟排序将待排记录分割成两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后对这两部分继续进行排序，以达到整个序列有序的目的
举例：
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
