算法❤ 八大排序算法

八大排序法【内部排序】：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序

排序算法的特点

【插入排序】：
从第二个数字开始到最后一个数字，与前面的数字依次比较，然后放进合适的地方
代码

void insert_sort(int[] a){
 int num=a.length;
        for(int i=1;i<num;i++){
            int j=i-1;
            int temp=a[i];
            for(;j>=0&&a[j]>temp;j--){
                a[j+1]=a[j];;
            }
            a[j+1]=temp;
        }
}

【希尔排序】
分组排序——每次去当前数组长度的一半直到该数组长度为2，在数组内进行插入排序。

    static void shellSorts(int[] a){
        int num=a.length;
        for (int j=num/2;j>0;j=j/2){
//插入排序
            for(int i=j;i<num;i++){
                int temp=a[i];
                int m=i;
                for(;m>=j && a[m-j]>temp;m=m-j){
                    a[m]=a[m-j];
                }
                a[m]=temp ;
            }
        }
        System.out.println(Arrays.toString(a));
    }
}

【简单选择排序】
在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

static void selectSorts(int[] a){
        int num=a.length;
        for(int i=0;i<num;i++){
            int temp=a[i];
            int nowPositoin=i;
            for(int j=i+1;j<num;j++){
                if(a[j]<temp){
                    temp=a[j];
                    nowPositoin=j;
                }
            }
            a[nowPositoin]=a[i];
            a[i]=temp;
        }
        System.out.println(Arrays.toString(a));
    }

【堆排序】
大顶堆-》交换首位位置

    static void heapSorts(int[] a){
        //完全二叉树里 i节点的孩子节点为2i+1 和 2i+2最后一个非子节点为 n/2-1

        int n=a.length;
        //构建一个大顶堆
        for (int i= n/2-1;i>=0;i--) {
            adjustchildTree(a, i, n);
        }
        for(int j=n-1;j>0;j--){
            int tmp=a[0];
             a[0]=a[j];
             a[j]=tmp;
            adjustchildTree(a,0,j);
        }

        System.out.println(Arrays.toString(a));
    }
    //哪个节点进行了调整，就去将他的子树给调整
    static void  adjustchildTree(int a[],int i,int len){
            int temp=a[i];
            for(int k=2*i+1;k<len;k=2*k+1){
                if(k+1<len && a[k]<a[k+1]){
                    k++;
                }
                if(a[k]>temp){
                    a[i]=a[k];
                    i=k;
                }else{
                    break;
                }
            }
            a[i]=temp;
        }

【冒泡排序】
循环对每一个
自上而下对相邻的两个数依次进行比较

    static void bubbleSorts(int[] a){
        int num=a.length;
        for (int i=num;i>0;i--){
            for (int j=num-1;j>0;j--){
                if(a[j]>a[j+1]){
                    int  temp=a[j];
                    a[j]=a[i];
                    a[i]=temp;

                }
            }
        }
    }

【快速排序】
个人理解： 其实是从左右开弓，左边找大于基准数（数组第一个）有边找小于基准数的，右边开始找，找到了跟基准数换位置。然后从最左边开始找找到 大于基准数的，又换位置，再从上次换位置的地方再继续以上查找
图解：http://blog.csdn.net/as02446418/article/details/47395867

static void onceQuickSorts(int[] a,int low,int high){
        int i=low , j=high;
        if(low>high)
            return;
        int tmp = a[i];
        while (i<j){
            while (i < j && a[j]>=tmp){
                j--;
            }
            if(i<j) {
                a[i] = a[j];
                i++;
            }
            while (i < j && a[i]<tmp){
                i++;
            }
            if(i<j) {
                a[j] = a[i];
                j--;
            }
        }
        a[i]=tmp;
        onceQuickSorts(a,low,i-1);
        onceQuickSorts(a,i+1,high);

    }

【归并排序】
分治-合并相邻有序
图解参考 https://www.cnblogs.com/chengxiao/p/6194356.html

    static void mergeSorts(int[] a){
        int num=a.length;
        int[] temp = new int[num];
       sort(a,0,a.length-1,temp);
        System.out.println(Arrays.toString(a));


    }
    static void merge(int[] a,int left, int mid,int right ,int[] temp){
        int i=left;
        int j=mid+1;
        int t = 0;
            while (i<= mid && j<=right) {
                if (a[j] >= a[i]) {
                    temp[t] = a[i];
                    i++;
                    t++;
                }else {
                    temp[t] = a[j];
                    j++;
                    t++;
                }
            }
        while(i<=mid){//将左边剩余元素填充进temp中
            temp[t++] = a[i++];
        }
        while(j<=right){//将右序列剩余元素填充进temp中
            temp[t++] = a[j++];
        }

        t = 0;
        //将temp中的元素全部拷贝到原数组中
        while(left <= right){
            a[left++] = temp[t++];
        }
    }


    static void sort(int[] a,int left,int right,int[] temp){
        if(left<right){
            int mid=(left+right)/2;
            sort(a,left,mid,temp);
            sort(a,mid+1,right,temp);
            merge(a,left,mid,right,temp);
        }
    }

【桶排序-基数排序】
个人理解：比较倾向于小时候个十位来比较数字大小的感觉
理解 https://www.cnblogs.com/skywang12345/p/3603669.html
图解参考;https://www.cnblogs.com/skywang12345/p/3603669.html

    static void bucketSorts(int[] a, int max) {

        int n = 1;
        int k = 0;
        int num = a.length;
        int[][] buckets = new int[10][num];
        int[] order = new int[num];  //保存桶里的数字数量
        while (n < max) {
            for (int each : a) {
                int digit = (each / n) % 10;
                buckets[digit][order[digit]] = each;
                order[digit]++;
            }

            for (int i = 0; i < num; i++) {
                if (order[i] != 0) {
                    for (int j = 0; j < order[i]; j++) {
                        a[k] = buckets[i][j];
                        k++;
                    }
                }
                order[i] = 0;
            }
            n*= 10;
            k = 0;

        }

    }
    static int getMax(int[] a ){
        int max = a[0];
        for (int i = 0; i < a.length; i++) {
            if (a[i] > max) {
                max = a[i];
            }
        }
        int tmp = 1, d = 1;
        while (true) {
            tmp *= 10;
            if (max / tmp != 0) {
                d++;
            } else
                break;
        }
        return d;
    }

为什么要从低位开始向高位排序?

如果要从高位排序, 那么次高位的排序会影响高位已经排好的大小关系. 在数学中, 数位越高,数位值对数的大小的影响就越大.从低位开始排序,就是对这种影响的排序. 数位按照影响力从低到高的顺序排序,数位影响力相同则比较数位值

其实我的理解就是比如有2个数 123和321
如果从高位开始比
百位时候：【从小到大】
123
321
十位的时候：
123
321
排到最后个位的时候，
321
123
这个就不对了
但是如果从低位开始比
百位时候：【从小到大】
321
123
十位的时候：
321
123
排到最后个位的时候，
123
321

其实这样就保证了我们在每个层级只需要保证当前的比较位按照数值排序 就可以了。不然排好了高位 再去排低位，高位的排序就会被影响。