[数据结构与算法]DAY1-简单排序

简单排序

• 插入排序
  选择正确位置进行插入在此选择从小到大依次排列
  由首个元素开始（首个元素默认有序）依次从后扫描如果后一个元素小于前一个元素则进行插入重复操作在三种简单排序中插入排序效率较高且相对稳定。

//插入排序
public class insertsort {
    public static void main(String [] args){
        int [] arr={2,1,5,7,3,9,4,6};
        System.out.println("排序前：");
        print(arr);
        sort(arr);
        System.out.println("排序后：");
        print(arr);
    }
    //排序算法
   static  void sort(int [] arr){
        for(int i=1;i<arr.length;i++){
            for(int j=i;j>0 && arr[j]<arr[j-1];j--){
             //   if(arr[j]<arr[j-1])
                swap(arr,j,j-1);
            }
        }
    }
    //数组交换
    static void swap(int [] arr,int i,int j){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
    //打印方法
    static void print(int [] arr){
        for (int i=0;i<arr.length;i++) {
            System.out.println(arr[i]+"");
        }
    }

}

- 冒泡排序
在数组中冒泡排序就是从数组首元素开始元素与下一元素两两比较大的数位置后移内层循环结束后外层下标加1重复操作直至数组有序

//冒泡排序
public class mpSort {
    public static void main(String [] args){
        int [] arr={5,6,4,3,7,9,2};
        System.out.println("排序前：");
        print(arr);
        sort(arr);
        System.out.println("排序后：");
        print(arr);
    }
    static void sort(int [] arr) {
        for (int i = arr.length - 1; i > 0; i--) {
            for (int j = 0; j < arr.length - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
            }
        }
    }
//  static   void sort(int [] arr){
//        for (int i=0;i<arr.length-1;i++){
//            for(int j=0;j<arr.length-i-1;j++){
//                if (arr[j] > arr[j + 1]) {
//                  swap(arr, j, j + 1);
//              }
//            }
//        }
//    }
 static    void swap(int [] arr,int i,int j){
        int temp=arr[i];
         arr[i]=arr[j];
         arr[j]=temp;
    }
   static  void print(int [] arr){
        for (int i=0;i<arr.length;i++) {
            System.out.println(arr[i]+"");
        }
      }
    }

• 选择排序
  在数组中分连个区间，有序区间无序区间，初始默认首元素开始依次与后面的元素相比将最小的元素挑出来并位置前移数组放入有序区间在无序区间重复操作直至数组有序

//选择排序
// 在每次遍历时找到基准与后面的值进行比较放前后均可依次循环
public class selecttest {
   public static void main(String [] args) {
        int[] arr = {3,1,5,2,4,9,7,6};
        for(int i=0;i<arr.length-1;i++){
            int minPos=i;
        for(int j=i+1;j<arr.length;j++){
            if(arr[j]<arr[minPos])
                minPos=arr[j] < arr[minPos] ? j:minPos;
        }
   //     System.out.println("minPos:"+minPos);
        swap(arr,i,minPos);
          //      System.out.println("经过第"+(i+1)+"次循环后的内容,");
   }
        print(arr);
    }
    



static void swap(int [] arr,int i,int j){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
    static void print(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]+"");
        }
    }
}