三种基本排序方法-冒泡排序，选择排序，插入排序

65 阅读 0 评论 43 点赞

我是靠谱客的博主顺利香水，最近开发中收集的这篇文章主要介绍三种基本排序方法-冒泡排序，选择排序，插入排序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

排序一入深似海，从此加入算法门~~
冒泡排序，选择排序和插入排序算得上是最基本的三种排序方式了，当年我的c语言老师和我们说，冒泡排序和选择排序能会一个就行了，结果c语言考试（机考）有一个沙雕题的评测库只能用冒泡才能过，于是我一个经常用选择排序的人，愣是憋了半个小时才憋出来冒泡排序的代码…扯远了。

先说冒泡排序，冒泡排序，顾名思义，就是让一个数组里最大/最小的数像冒泡一样跑到右边（或者左边）,就以让最大数“冒”到右边为例，对一个序列A中的元素A[1]~A[n],进行n-1趟操作，从1到n分别对相邻的两个元素进行比较，如果前面的元素大于后面的元素，则交换；完成第一趟操作后，最大数就会”冒“到最后面。接下来再对前n-1个元素做同样的操作，当n-1趟操作完毕后，即排序完毕。
废话不多说，直接给代码：

#include <bits/stdc++.h>
using namespace std;
int main(){
int a[5]={5,3,1,4,2};
int i,j,temp;
for(i=1;i<=4;i++)
{
for(j=0;j<5-i;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
for(i=0;i<5;i++)cout<<a[i]<<' ';
return 0;
}

选择排序
选择排序也是经典而又基础的排序算法之一，简单选择排序，即对一个序列A中的元素A[1]~A[n]，令i从1到n进行枚举，进行n趟操作，每趟从待排序部分[i,n]中选择最小的元素，令其与待排序部分的第一个元素A[i]进行交换，这样元素A[i]就会与当前有序区间[1,i-1]形成新的有序区间[1,i]。于是在n趟操作后，所有元素就会是有序的。

直接上代码：

void selectSort()
{
int i,j,k,temp;
for(i=0;i<n;i++)//进行n趟操作
{
k=i;
for(j=i;j<n;j++)//选出最小的元素交换
{
if(a[j]<a[k])
k=j;
}
if(k!=i)//k=i时不交换，可以减小一点时间复杂度
{
temp=a[i];
a[i]=a[k];
a[k]=temp;
}
}
}

插入排序
这里介绍直接插入排序。直接插入排序即是将一个序列分成两组，前一组是已经有序的数列，后一组是无序的数列，然后将后一组数列的元素依次插入前一组，插入的同时保证前一组仍有序；最后，直到后一组数列全部插入前一组，排序完毕。
代码如下：

int n=5;
int A[maxn];
void insertSort()
{
for(int i=2;i<=n;i++)//进行n-1趟
{
int temp=A[i],j=i;//设置temp存放要插入的元素
while(j>1&&temp<A[j-1])//这个循环结构用于将temp插入有序序列
{
A[j]=A[j-1];
j--;
}
A[j]=temp;
}
}