排序算法用法详解

算法思想

相邻的元素两两比较，较大的数下沉，较小的数冒起来，这样一趟比较下来，最大(小)值就会排列在一端。整个过程如同气泡冒起，因此被称作冒泡排序。

时间复杂度O( n 2 n^2 n2) ( markdown编辑器 n 2 n^2 n2 用$ n^2 $表示)

适用： 冒泡排序适用于数据量很小的排序场景

C/C++

#include
using namespace std;
int a[10]={2,5,3,1,9,6,8,7,0,10};
void sort1()
{
    for(int i=0;i<10;i++)
    {
        for(int j=i+1;j<10;j++)
        {
            if(a[i]>a[j])//从小到大
            {
                swap(a[i],a[j]);
            }
            
            
            if(a[i]
                swap(a[i],a[j]);
            }
        }
    }
    for(int i=0;i<10;i++)
        printf("%d ",a[i]);
}
int main()
{
    sort1();
    return 0;
}

Java

public static void main (String[] args)  {
      int[] arr=new int []{2,5,3,1,9,6,8,7,0,10};
      int l=arr.length;
      int t;
      for(int i=0;i
          for(int j=i+1;j
              if(arr[i]>arr[j])
              {
                 t=arr[i];
                 arr[i]=arr[j];
                 arr[j]=t;
              }
          }
      }
      for(int i=0;i 
二、选择排序 
算法思想：
 
先定义第一个元素为最小（大）值，然后再从剩余的未元素中寻找到最小（大）元素，继续放在起始位直到遍历结束
 
时间复杂度为O(
     
      
       
        
         
          n
         
         
          2
         
        
       
       
        n^2
       
      
     n2)
 
适用： 适用于数据量很小的排序
 
C/C++
 
#include
using namespace std;
int a[10]= {2,5,3,1,9,6,8,7,0,10};
void sort1()
{
    int minn;
    for(int i=0; i<10; i++)
    {
        minn=i;
        for(int j=0; j<10; j++)
        {
            if(a[minn]>a[j])
            {
                minn=j;
                swap(a[i],a[j]);
            }
        }
    }
    for(int i=0; i<10; i++)
    {
        printf("%d ",a[i]);
    }
}
int main()
{
    sort1();
    return 0;
}
 
Java
 
public static void main (String[] args)  {
      int[] arr=new int []{2,5,3,1,9,6,8,7,0,10};
      int l=arr.length;
      int t,minn;
      for(int i=0;i
          minn=i;
          for(int j=0;j
              if(arr[minn]>arr[j])
              { 
                  minn=j;
                 t=arr[i];
                 arr[i]=arr[j];
                 arr[j]=t;
              }
          }
      }
      for(int i=0;i 
三、插入排序 
直接插入排序
 
算法思想
 
每一步将一个待排序的数据插入到前面已经排好序的有序序列中，直到插完所有元素为止。
 
实现步骤
 
每次从无序部分中取出一个元素，与有序部分中的元素从后向前依次进行比较，并找到合适的位置，将该元素插到有序组当中。
 
时间复杂度O（
     
      
       
        
         
          n
         
         
          2
         
        
       
       
        n^2
       
      
     n2）
 
**适用：**待排序的元素个数不多(<=50)，且元素基本有序
 C/C++
 
#include
using namespace std;
int a[10]= {2,5,3,1,9,6,8,7,0,10};
void insertsort()
{
    int t,j;
    //从小到大
    for(int i=1;i<10;i++)
    {
        t=a[i];
        for(j=i-1;i>=0&&a[j]>t;j--)
        {
            a[j+1]=a[j];
        }
        a[j+1]=t;
    }
    for(int i=0; i<10; i++)
    {
        printf("%d ",a[i]);
    }
}
int main()
{
    insertsort();
    return 0;
}
 
Java
 
public static void main (String[] args)  {
      int[] arr=new int []{2,5,3,1,9,6,8,7,0,10};
      int l=arr.length;
      int t,j;
      for(int i=1;i
          t=arr[i];
          for(j=i-1;j>=0&&arr[j]>t;j--) {
              arr[j+1]=arr[j];
          }
          arr[j+1]=t;
      }
      for(int i=0;i 
插入排序的优化有 折半插入排序 和 2-路插入排序
 
折半插入排序
 
算法思想
 
二分思想，将待排序的元素与有序部分的元素比较时，不再一 一比较，采取用二分的方式进行比较
 
C/C++
 
#include
using namespace std;
int a[10]= {2,5,3,1,9,6,8,7,0,10};
void insertsort()
{
    int left,right,mid,t;
    for(int i=1;i<10;i++)
    {
        left=0;
        right=i-1;
        t=a[i];
        //找到合适的插入位置
        //如果中间位置元素的值大于要插入的值,则查找区间更改为小的区间
        //否则，将区间改为大的区间
        while(left<=right)
        {
            mid=(left+right)/2;
            if(a[mid]>t)
                right=mid-1;
            else
                left=mid+1;
        }
        int j;
        for(j=i-1;j>=right+1;j--)
        {
            a[j+1]=a[j];
        }
        a[j+1]=t;
    }
    for(int i=0; i<10; i++)
    {
        printf("%d ",a[i]);
    }
}
int main()
{
    insertsort();
    return 0;
}
 
Java
 
public class Main {
    public static void main (String[] args)  {
      int[] arr=new int []{2,5,3,1,9,6,8,7,0,10};
      int l=arr.length;
      int left,right,mid,t,j;
      for(int i=1;i
          left=0;
          right=i-1;
          t=arr[i];
          while(left<=right){
              mid=(left+right)/2;
              if(arr[mid]=right+1;j--){
              arr[j+1]=arr[j];
          }
          arr[j+1]=t;
      }
      for(int i=0;i 
四、希尔排序 
希尔排序(又称为缩小增量排序)
 
算法思想：
 设待排序的元素的个数为n，首先取一个整数increment（小于序列总数）作为间隔所有距离为increment的元素放在同一个逻辑数组中，在每一个逻辑数组中分别实行直接插入排序，然后缩小间隔increment，重复上述逻辑数组划分和排序，直到最后increment=1，将所有元素放在同一个数组中排序即可
 
实现步骤
 
 
 
1、选increment。划分逻辑数组，逻辑数组内进行直接插入排序
 2、不断缩小increment，继续在逻辑数组内进行插入排序
 3、直到increment=1，在包含所有元素的序列内继续直接插入排序
 
 
时间复杂度O（
     
      
       
        
         
          n
         
         
          2
         
        
       
       
        n^2
       
      
     n2）
 
C/C++
 
#include
using namespace std;
int a[12]= {2,5,3,1,9,6,8,7,0,10};
void shellsort()
{
    //初始化increment增量
    int increment=10,j,t;
    //每次减小increment，直到increment=1
    while(increment>1){
        //增量的取法之一：除以3向下取整后加1
        increment=increment/3+1;
    //对每个按increment间距划分的逻辑数组，实行直接插入排序
        for(int i=increment;i<10;i++)
        {
            if(a[i-increment]>a[i])
            {
                t=a[i];
                j=i-increment;
                //移动元素并寻找位置
                while(j>=0&&a[j]>t){
                    a[j+increment]=a[j];
                    j-=increment;
                }
                //插入元素
                a[j+increment]=t;
            }
        }
    }
    for(int i=0; i<10; i++)
    {
        printf("%d ",a[i]);
    }
}
int main()
{
    shellsort();
    return 0;
}