数据结构排序算法

2021-07-18 10:30:34

作为编程小白，最近在学习算法，所以想把几种排序算法温习一遍，本文所有排序都为升序，并且描述代码为java

1选择排序

1.1过程分析

对于一个不确定的整形数组，首先将i=0所在的数和后面的所有数进行比较，找出最小的数i=j交换数组中的数，下一次再从i=1开始比较，直到i=num.length-1

1.2动画分析

1.2算法描述

public class selectsort {
    public static void main(String[] args) {

    int[] num= {2,3,5,4,1,9,8,7,56,3,66,56,52,51,20,32};//要排序的数组
    selectsort(num);
    for(int n:num)    //增强型for语句用于输出排序后的数组
    {
        System.out.println(n);
    }
    }
    public static void selectsort(int[] num)     //构造方法
    {
        for(int i=0;i<num.length;i++)
        {
            int minindex=i;
            for(int j=i+1;j<num.length;j++)
            {
                if(num[minindex]>num[j])
                {
                    minindex=j;
                }
                            }
            swap(num,i,minindex);
        }
    }
    public static void swap(int[] num,int i,int minindex)//交换下标为i和minindex中的数组元素
    {
        int temp;
        temp=num[minindex];
        num[minindex]=num[i];
        num[i]=temp;
    }
}

1.4复杂度

时间复杂度：O（n^2）

2插入排序

2.1算法描述

在一个整形数组中，从第二个数开始，将其与前面的数比较，如果比前面的数小，则与其交换位置，直到其到达数组最左侧为止，如果比前面的数大，则开始从第三个数和前面的数比较大小

2.2动画分析

2.3算法代码

public class Insertsort {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] num= {2,3,5,4,1,9,8,7,56,66,56,52,51,20,32};//要排序的数组
          Insertsort(num);
          for(int n:num)    //增强型for语句用于输出排序后的数组
          {
              System.out.print(n+",");
          }
    }
    public static void Insertsort(int[] num)   //排序算法
    {
        for(int i=1;i<num.length;i++)
        {
                  
            for(int j=i;j>0;j--)
            {
                if(num[j]<num[j-1])
                {
                    swap(num,j-1,j);
                }
                else{
                    break;
                }
            }
        }
    }
  public static void swap(int[] num,int index,int j)//交换两个数的下标
  {
      int temp;
      temp=num[index];
      num[index]=num[j];
      num[j]=temp;
  }
}

2.4复杂度

时间复杂度：O（n^2）

3冒泡排序（也叫气泡排序）

3.1算法描述

对于一个要排序的数组，首先从下标I=0开始+1，每当遇到两个数i和i+1,当num[i]>num[i++1]时，交换两个数的位置，在第一次遍历后，最大元素肯定在最右侧，第二次遍历后，倒数第二个大树也在右侧第二个位置上，进行num.length-1次遍历后，素组中元素被升序排序完成

3.2动态分析

3.3算法描述

public class Bobblesort {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] num= {2,3,5,4,1,9,8,7,56,66,56,52,51,20,32};//要排序的数组
        Bobblesort(num);
        for(int n:num)    //增强型for语句用于输出排序后的数组
        {
            System.out.print(n+",");
        }
    }

    private static void Bobblesort(int[] num) {
        for(int i=0;i<num.length;i++)
        {
            for(int j=0;j<num.length-i-1;j++)
            {
                if(num[j]>num[j+1])
                {
                    swap(num,j,j+1);
                }
            }
        }
        
    }
    public static void swap(int[] num,int index,int j)//交换两个数的下标
      {
          int temp;
          temp=num[index];
          num[index]=num[j];
          num[j]=temp;
      }
}

3.4复杂度

时间复杂度：O（n^2）
未完待续..........................

码农公寓