BetterTs

鸢飞戾天者,望峰息心;经纶世务者,窥谷忘反

初等排序

初等排序

冒泡排序、选择排序和插入排序的时间复杂度都是$$ O(n^2)$$,都是排序算法中较为基础的算法,也统称为初等排序算法。一般作为排序算法的入门。
三种排序算法的思想都是将数据分为已排序部分和未排序部分再做相应处理。

实例

输入 第一行输入数组长度整数N,第二行输入N个整数,以空格隔开
输出 输出排序结果
限制 1<=N<=100

插入排序

伪代码

InsertionSort(A,N)//包含n个元素的数组A
    for i=1 to N-1
        v=A[i]
        j=i-1
        while j>=0 and A[j]>v//移动比A[i]大的元素
            A[j+1]=A[j]
            j--
        A[j+1]=v//插入操作

算法原理

  1. 将开头元素视作已排序部分
  2. 取出未排序部分的开头元素赋值给v
  3. 在已排序部分,所有比v大的元素都往后移动一个单位
  4. 将取出的元素v插入空位
  5. 循环2-4直至未排序部分消失

源码

#include <iostream>
using namespace std;

void InsertionSort(int A[],int N){
    int j,v;
    for(int i=1;i<N;i++){
        v=A[i];
        j=i-1;
        while(j>=0&&A[j]>v){
            A[j+1]=A[j];
            j--;
        }
        A[j+1]=v;
    }
} 
int main(){
    int N,i,j;
    int A[100];

    cin>>N;
    for(i=0;i<N;i++){
        cin>>A[i];
    }
    InsertionSort(A,N);
    for(i=0;i<N;i++){
        cout<<A[i]<<" ";
    }
}

输出结果
《初等排序》

冒泡排序

伪代码

BubbleSort(A,N)
    flag=1//存在顺序相反的相邻元素
    i=0//未排序部分的起始下标
    while(flag)
        flag=0
        for j=N-1 downto 1
            if A[j]<A[j-1]
                swap(A[j-1],A[j])//交换
                flag=1
        i++

算法思想

  1. 待排序数组A分为已排序部分和未排序部分
  2. 从数组末尾开始依次比价相邻元素,如果大小相反则交换位置

源码

#include <iostream>
using namespace std;

void Swap(int *a,int *b){
    *a=*a+*b;
    *b=*a-*b;
    *a=*a-*b;
}

void BubbleSort(int A[],int N){
    bool flag=1;
    int j=0;
    while(flag){
        flag=0;
        for(int i=N-1;i>=j+1;i--){
            if(A[i]<A[i-1]){
                Swap(A+i,A+i-1);
                flag=1;
            }
        }
        j++;

    }
}

int main(){
    int N;
    int A[100];

    cin>>N;
    for(int i=0;i<N;i++){
        cin>>A[i];
    }
    BubbleSort(A,N);
    for(int i=0;i<N;i++){
        cout<<A[i]<<" ";
    }
}

输出结果
《初等排序》

选择排序

伪代码

SelectionSort(A,N)
    for i=0 to N-1
        minj=i
        for j to N-1
            if A[j]<A[minj]
                minj=j
        swap(A[i],A[minj])

算法原理

  1. 将数组分为未排序部分和已排序部分
  2. 选出未排序部分的最小值的位置minj
  3. 将未排序部分的最小值和未排序部分的起始元素进行交换,直至未排序部分的元素为0

源码

#include <iostream>
using namespace std;

void Swap(int *a,int *b){
    *a=*a+*b;
    *b=*a-*b;
    *a=*a-*b;
}
void SelectionSort(int A[],int N){
    int minj;
    for(int i=0;i<N-1;i++){
        minj=i;
        for(int j=i;j<N;j++){
            if(A[j]<A[minj]){
                minj=j;
            }
        }
        Swap(A+minj,A+i);
    }
}
int main(){
    int N;
    int A[100];

    cin>>N;
    for(int i=0;i<N;i++){
        cin>>A[i];
    }
    SelectionSort(A,N);
    for(int i=0;i<N;i++){
        cout<<A[i]<<" ";
    }
}

输出结果
《初等排序》

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注