算法_选择、插入、希尔排序

时间复杂度

基本算法

1、选择排序

原理是对数组进行a进行遍历，假定a[i]是最小的，然后在与i之后的元素进行对比，如果找到比a[i]更小的，则进行位置替换。

public class SelertSort {

    public void selectSort(int[] array) {
        int min;
        int tmp = 0;
        for (int i = 0; i < array.length; i++) {
            min = array[i];
            for (int j = i; j < array.length; j++) {
                if (array[j] < min) {
                    min = array[j];//最小值
                    tmp = array[i];
                    array[i] = min;
                    array[j] = tmp;
                }
            }
        }
        for(int num:array){
            System.out.println(num);
        }
    }
    
    public static void main(String [] args){
        SelertSort selertSort = new SelertSort();
        selertSort.selectSort(new int[]{9,4,2,6,7,3,10,33,88,1,17});
    }
}

2、插入排序

下面是二分法插入，跟插入排序原理一样，不同的是在找插入元素的位置。普通的插入算法是一个当前节点进行数值比较的while循环，当遇到比插入的值大时就退出循环（从小到大排序）。之后将后面的元素进行后移，腾出位置放入要插入的元素。

2.1、二分法插入

public class BinaryInsertSort {
    public static void main(String[] args) {
        int[] a={49,38,65,97,176,213,227,49,78,34,12,164,11,18,1};
        System.out.println("排序之前：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
        //二分插入排序
        sort(a);
        System.out.println();
        System.out.println("排序之后：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
    }
//二分法插入
    private static void sort(int[] a) {
        for (int i = 0; i < a.length; i++) {
            int temp = a[i];
            int left = 0;
            int right = i-1;
            int mid = 0;
            //确定要插入的位置
            while(left<=right){
                //先获取中间位置
                mid = (left+right)/2;
                if(temp<a[mid]){
                    //如果值比中间值小，让right左移到中间下标-1
                    right = mid-1;
                }else{
                    //如果值比中间值大,让left右移到中间下标+1
                    left = mid+1;
                }
            }
            for (int j = i-1; j >= left; j--) {
                //以左下标为标准，在左位置前插入该数据，左及左后边全部后移
                a[j+1] = a[j];
            }
            if(left != i){
                //左位置插入该数据
                a[left] = temp;
            }
        }
    }
}

2.2、直接插入排序

public class InsertSort {
/**
* 直接插入排序
* @param args
*/
       public static void main(String[] args) {
           int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1};
           System.out.println("排序之前：");
           for (int i = 0; i < a.length; i++) {
               System.out.print(a[i]+" ");
           }
           //直接插入排序
           for (int i = 1; i < a.length; i++) {
               //待插入元素
               int temp = a[i];
               int j;
               for (j = i-1; j>=0; j--) {
                   //将大于temp的往后移动一位
                   if(a[j]>temp){
                       a[j+1] = a[j];
                   }else{
                       break;
                   }
               }
               a[j+1] = temp;//插入进来
           }
           System.out.println();
           System.out.println("排序之后：");
           for (int i = 0; i < a.length; i++) {
               System.out.print(a[i]+" ");
           }
       }
}

3、希尔排序

//不稳定
public class HeerSort {

 //希尔排序   
    public static void main(String[] args) {
        int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,33,85,29};
        System.out.println("排序之前：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
        //希尔排序
        System.out.println();
        int d = a.length/2;
        while(true){
            for(int i=0;i<d;i++){
                for(int j=i;j+d<a.length;j+=d){
                int temp;
                if(a[j]>a[j+d]){
                    temp=a[j];
                    a[j]=a[j+d];
                    a[j+d]=temp;
                    }
                }
            }
            if(d==1){break;}
            d--;
           }
        System.out.println();
        System.out.println("排序之后：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
    }

}