绝密笔记 | 排序算法 - V2CE

排序算法，我们要从冒泡排序说起。

冒泡排序

何为冒泡排序，废话不多说，直接上图

从图可以看出，有多少组数据，冒泡排序就要进行多少趟，而每一趟，都是把相邻的元素进行比较，如果符合排序要求，则下一步，如果不符合就进行调换。

冒泡排序比较简单，在这里不做太多的解释，直接上代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)    cin>>a[i];
    for(int i=0;i<n;i++){
        for(int j=0;j<n-i;j++){
            if(a[j]<a[j+1]){
                    a[j]  +=   a[j+1];
                    a[j+1] = a[j]-a[j+1];
                    a[j] -= a[j+1];
/*
第三层循环可以不要，只是为了将每次调换位置后的过程给显现出来
你也可以放到外层循环中，看一下每一趟跑完后是什么样子
*/              
for (int k = 0; k < n; k++){
            cout<<a[k]<<" ";
            }
            cout<<endl;
                } 
       
        }
        
    }
    for (int i = 0; i < n; i++)
    {
        /* code */
        cout<<a[i]<<" ";
    }
    
}

桶排序

这个排序，有点意思，我们一般的排序算法，操控的是元素来移动，而桶排序，利用的确实数组的索引，没错，就是数组的索引。

为什么会用数组索引呢？首先数组的下标（索引号）是固定的 0，1，2，3，4，5，6，……

它们具有一个固定的顺序结构，所以我们找到需要排序的数字所对应的下标，对这个下标所对应的值加一（记得提前memset数组），最后输出的时候按照顺序（逆序）输出下标，输出的次数便是每个数字出现的次数（也就是索引值）

具体的可以看图片和代码操作

下面我直接放代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,b;
    cin>>n;
    int a[10000]={};
    for (int i = 0; i < n; i++)
    {
//输入第i数字，假设这个数字为b，那么a[b]++；
        cin>>b;
        a[b]++;
    }
    cout<<"升序：";
    for (int i = 0; i < n; i++)
    {
        if(a[i]){
            for(int j=0;j<a[i];j++)
                cout<<i<<" ";
        }
    }
    cout<<endl<<"降序：";
    for (int i = n+1; i >= 0; i--)
    {
        if(a[i]){
            for(int j=0;j<a[i];j++)
                cout<<i<<" ";
        }
    }
    return 0;
}

时间太晚了，关于插入排序与归并排序~~明天更新~~，内容有点多，可能后面两个不太好理解，但理解到了也就那样

昨天说了冒泡排序，今天来说下插入排序以及归并排序（归并可能要明天才能上线，今天有点事情）

插入排序

插入排序，一种排序方法，就像我们打扑克牌一样将牌插入指定位置。

平时我们是怎么给扑克牌排序的呢，都是把牌插到合适的位置上去，就像这样

但是依靠程序语言如何表达呢。

插入排序

这个是我自己整理的笔记，详细的说明也再上面，下面我直接上代码，还有自己曾经手写演算的图片

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,temp; //temp为临时变量，用于a[j]和a[j+1]间的交换
    cin>>n;
    int a[n];
    for (int i = 0; i < n; i++)
    {
        /* code */
        cin>>a[i];
    }
    for (int i = 1; i < n; i++)
    {
        /* code */
        temp=a[i];
        int j=i-1;
        while (j>=0&&temp<a[j])
        {
            /* code */
            a[j+1]=a[j];
            j--;
        }
        
        // for(j=i-1;j>=0&&temp<a[j];j--){
        //     a[j+1]=a[j];
        // }
        a[j+1]=temp;
    }
    for(int i=0;i<n;i++)    cout<<a[i]<<" ";    
    return 0;
}

插入排序手算演绎图

归并排序（利用分治算法的思想，分而治之，分到根部，再在返回值的同时进行排序）

下面是归并排序（有时间再写，我先上代码和自己的理解，代码可能无法运行）

截自YouTuBe用户：五点七边的视频

这个是我自己整理的笔记

下面是我自己写的代码，能运行，不过程序会终止，可能有点问题，大家可以尝试着改一下然后再下方评论

#include <bits/stdc++.h>
using namespace std;
/*原数组，待拷贝数组,起始位置,最终位置*/
void mergesort(int array[],int copyarr[],int low,int hight);
/*原数组，待拷贝数组,起始位置,中间分治位置,最终位置*/
void merge(int array[],int copyarr[],int low,int mid,int hight);
int main(){
    int n;
    cin>>n;
    int array[n],copyarr[n]={0};
    memset(array,0,sizeof(array));
    memset(copyarr,0,sizeof(copyarr));

    for (int i = 0; i < n; i++) cin>>array[i];
    mergesort(array,copyarr,0,n-1);
    for (int i = 0; i < n; i++) cout<<copyarr[i]<<" ";
    return 0;
}
void mergesort(int array[],int copyarr[],int low,int hight){
    if(hight <= low) return;
    int mid=(low+hight)/2;
    mergesort(array,copyarr,low,mid);
/*递归时每一次的hight等于上一次的mid*/
    mergesort(array,copyarr,mid+1,hight); 
    merge(array,copyarr,low,mid,hight);
}
void merge(int array[],int copyarr[],int low,int mid,int hight){
     int left=low;
     int right=mid+1;
     int k=low;
/*也可以写成<mid+1和hight+1同理*/
     while (left<=mid&&right<=hight)    
     {  
        if(array[left]>array[right]) copyarr[k++]=array[right++];
        else copyarr[k++]=array[left++];
     }
     //将未移入的移入
     while (left<=mid)  copyarr[k++]=array[left++];
     while (right<=hight) copyarr[k++]=array[right++];
 }