排序算法：基础入门篇

一、选择排序

1.1 常规选排思路

选择排序算法是排序算法中最简单直观的排序法其思路也是简单明了它的时间复杂度为$O(n^2)$空间复杂度为$O(1)$。选择排序具有不稳定的特点因此我们在排序量大的时候尽量不选择选择排序会导致运行效率大大降低在比赛中会导致超过时间限制。此算法的基本思路如下

如图所示先从数列中找到最小数$1$将它放到数列的最前端。

继续在数列中寻找最小值然后放到第二个位置。以此类推直至将整个数列排序完成。代码如下

#include <iostream>
using namespace std;
int main(){
    int a[8]={2,1,6,7,5,4,3,8};
    for(int i=0;i<8;i++){
        int num,min=9999;
        for(int j=i;j<8;j++){
            if(a[j]<min){
                num=j;
                min=a[j];
            }
        }
        int temp=a[i];
        a[i]=min;
        a[num]=temp;
    }
    for(int i=0;i<8;i++) cout<<a[i];
    return 0;
}

1.2 优化选排思路

根据上述思路我们不仅可以将最小的找出来放到最前端也能将最大的找出来放到最后端这样运行的效率增快了一倍。

代码如下

#include <iostream>
using namespace std;
int main(){
    int a[8]={2,1,6,7,5,4,3,8};
    for(int i=0;i<4;i++){
        int num,num_x,min=9999,max=-1;
        for(int j=i;j<8-i;j++){
            if(a[j]<min){
                num=j;
                min=a[j];
            }
            if(a[j]>max){
                num_x=j;
                max=a[j];
            }
        }
        int temp=a[7-i];
        a[7-i]=max;
        a[num_x]=temp;
        temp=a[i];
        a[i]=min;
        a[num]=temp;
    }
    for(int i=0;i<8;i++) cout<<a[i];
    return 0;
}

二、冒泡排序

冒泡排序是通过每次比较相邻数大小每次将最大的数放到数列末端从而达到排序目的。它的时间复杂度为$O(n^2)$空间复杂度为$O(1)$。代码如下

#include <iostream>
using namespace std;
int main(){
    int arr[8]={2,1,6,7,5,4,3,8};
    for(int i = 0; i < 8; i++){
        for(int j = 0; j < 8 - 1 - i; j++){
            if(arr[j] > arr[j+1]){
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    for(int i = 0;i < 8; i++) cout<< arr[i];
    return 0;
}

三、插入排序

插入排序也是比较好理解的一种排序办法其主要思路是在待排序的元素中假设前$n-1$个元素已有序现将第$n$个元素插入到前面已经排好的序列中使得前$n$个元素有序。按照此法对所有元素进行插入直到整个序列有序。

在移位到第一个数也大于目标数的时候就令$a_0$为目标数值即可。
代码如下

#include <iostream>
using namespace std;
int main(){
    int a[8]={2,1,6,7,5,4,3,8};
    for(int i=1;i<8;i++){
        int temp=a[i];
        for(int j=i-1;j>=0;j--){
            if(a[j]>temp){
                a[j+1]=a[j];
            }else{
                a[j+1]=temp;
                break;
            }
            if(j==0&&a[1]>temp) a[0]=temp;
        }
    }
    for(int i=0;i<8;i++) cout<<a[i];
    return 0;
}