一、

//直接插入排序//思路：先取一个有序的队列，然后将其他数字一个一个和这个有序数列排序//稳定//时间复杂度  最好情况：O（n） 最坏情况O（n²）//空间复杂度 O（n）public class InsertAlgorithm {    static  int[] arr={5,7,3,9,10,50};    public void  sort(){        for(int i=0;i<arr.length-1;i++){            for(int j=0;j<i;j++){                if(arr[i]>arr[j]){                }                else{                    int temp=0;                    temp=arr[i];                    arr[i]=arr[j];                    arr[j]=temp;                }            }        }    }    public static void main(String[] args){        InsertAlgorithm ia=new InsertAlgorithm();        ia.sort();        for(int i=0;i<arr.length;i++){            System.out.println(arr[i]);        }    }}

二、插入排序-希尔排序

1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2. 按增量序列个数k，对序列进行k 趟排序；
3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度

   void print(int a[], int n ,int i){      cout<<i <<":";      for(int j= 0; j<8; j++){          cout<<a[j] <<" ";      }      cout<<endl;  }  /**  * 直接插入排序的一般形式  *  * @param int dk 缩小增量，如果是直接插入排序，dk=1  *  */    void ShellInsertSort(int a[], int n, int dk)  {      for(int i= dk; i<n; ++i){          if(a[i] < a[i-dk]){          //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入              int j = i-dk;                 int x = a[i];           //复制为哨兵，即存储待排序元素              a[i] = a[i-dk];         //首先后移一个元素              while(x < a[j]){     //查找在有序表的插入位置                  a[j+dk] = a[j];                  j -= dk;             //元素后移              }              a[j+dk] = x;            //插入到正确位置          }          print(a, n,i );      }        }    /**  * 先按增量d（n/2,n为要排序数的个数进行希尔排序  *  */  void shellSort(int a[], int n){        int dk = n/2;      while( dk >= 1  ){          ShellInsertSort(a, n, dk);          dk = dk/2;      }  }  int main(){      int a[8] = {3,1,5,7,2,4,9,6};      //ShellInsertSort(a,8,1); //直接插入排序      shellSort(a,8);           //希尔插入排序      print(a,8,8);  }  

    

十种基本排序算法