希尔排序

  1. 基本介绍

    希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效率的版本，也称为缩小增量排序。

  2. 基本思想

    希尔排序是把计录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量的减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

  3. 代码实现【交换式】

    public static  void sellSort(int[] arr){
        int temp =0;
        //第一层for循环时每一次的分组情况
        for (int gap =arr.length / 2; gap >0 ; gap/=2) {
            for (int i =gap; i <arr.length ; i++) {
                for (int j = i-gap; j>=0 ; j-=gap) {//遍历各组中所有的元素
                    if (arr[j]>arr[j+gap]){
                        temp = arr[j];
                        arr[j] =arr[j+gap];
                        arr[j+gap] =temp;
                    }
                }
            }
       
        }
        System.out.println(Arrays.toString(arr));
    }

  4. 代码实现【插入式】

    //希尔排序的插入式
       public static  void sellSort2(int[] arr){
           //第一层for循环时每一次的分组情况
           for (int gap =arr.length / 2; gap >0 ; gap/=2) {
               //从第gap个元素，逐个对其所在的组进行直接插入排序
               for (int i =gap; i <arr.length; i++) {
                   int j =i;
                   int temp =arr[j];
                   if (arr[j]<arr[j-gap]){
                       while(j-gap>=0 && temp <arr[j-gap]){
                           //移动
                           arr[j] =arr[j-gap];
                           j-=gap;
                       }
                       //当退出while后，就给temp找到插入的位置
                       arr[j]=temp;
                   }
               }
           }
           System.out.println(Arrays.toString(arr));
       }

快速排序

  1. 基本介绍

    QuickSort 是对冒泡排序的一种改进。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对两部分数据分别进行快速排序

  2. 代码实现

    public  static  void quicksort(int[] arr, int left,int right){
            int l =left; //左下标
            int r =right; //右下标
            //pivot 中轴值
            int pivot = arr[(left + right) / 2];
            int temp= 0;//临时变量，交换使用
            //while 循环的目的是让比pivot值小放到左边
            //比pivot 值大放到右边
            while(l < r){
                // 在pivot的左边一直找，找到大于等于pivot值，才退出
                while(arr[l] < pivot){
                    l +=1;
                }
                //在 pivot 的右边一直找，找到小于等于piovt值，才退出
                while( arr[r] >pivot){
                    r-=1;
                }
                //if l>=r 说明pivot 的左右两边的已经完成
                if (l >= r){
                    break;
                }

                //交换
                temp = arr[l];
                arr[l] = arr[r];
                arr[r] = temp;

                //如果交换完后，发现arr[l]=pivot值 相等 l--
                if (arr[l] == pivot){
                    r-=1;
                }
                //如果交换完后，发现这个arr[r] == pivot 相等l++,后移
                if (arr[r] == pivot){
                    l +=1;
                }
            }
            //如果l == r,必须l++,r--，否则为出现栈溢出
            if (l == r){
                l += 1;
                r -= 1;
            }
            //向左递归
            if (left < r){
                quicksort(arr, left, r);
            }
            //向右递归
            if (right > l){
                quicksort(arr, l, right);
            }
        }

归并排序

package 排序;

import java.util.Arrays;

public class MergetSort {
    public static void main(String[] args) {
        int arr[] = {8,4,5,7,1,3,6,2};
        int temp[] = new int[arr.length];//归并排序需要一个额外的空间
        mergeSort(arr, 0, arr.length-1, temp);
        System.out.println(Arrays.toString(arr));

    }
    public  static  void mergeSort(int[] arr, int left, int right, int[] temp){
        if (left <right){
            int mid = (left+right)/2;
            //向左递归进行分解
            mergeSort(arr, left, mid, temp);
            //向右递归进行分解
            mergeSort(arr, mid+1, right, temp);
            //合并
            merge(arr, left, mid, right, temp);
        }
    }
    public static void merge(int[] arr,int left,int mid,int right,int[] temp) {
        int i = left; //初始化i，左边有序序列的初始索引
        int j = mid + 1; //初始化就，右边有序序列的初始序列
        int t = 0; //指向temp的当前数组

        //（一）
        //先把左右两边有序的数据按照规则填充到temp数组
        //直到左右两边的有序序列，有一边处理完毕为止
        while (i <= mid && j <= right) {//继续
            /*
            如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
            即将左边的当前元素，填充到temp数组
            然后 t++,i++
             */
            if (arr[i] <= arr[j]) {
                temp[t] = arr[i];
                t += 1;
                i += 1;
            } else {//反之，将右边有序序列的当前元素，填充到temp数组
                temp[t] = arr[j];
                t += 1;
                j += 1;
            }
        }
        /*
        (二)
        将剩余数据的一边的数据依次全部填充到temp
         */
        while (i <= mid) {//左边的有序序列还有剩余的元素，就全部填充到temp
            temp[t] = arr[i];
            t += 1;
            i += 1;
        }
        while (j <= right) {//右边的有序序列还有剩余，就全部填充到temp
            temp[t] =arr[i];
            t += 1;
            j += 1;
        }

        /*
        (三)
        将temp数组的元素拷贝到arr
        注意，并不是每次都要拷贝所有
         */
        t=0;
        int tempLift =left;
        while(tempLift <= right){
            /*
              第一次合并tempLeft = 0, right = 1// tempLeft =2 right =3
              tL=0 ri =3
              最后一次 tempLeft = 0 right =7
             */
            arr[tempLift] = temp[t];
            t += 1;
            tempLift +=1;
        }

    }
}

基数排序‘

  1. 基本思想

    将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

  2. 第一轮排序： 将每个元素的个位数取出，然后看这个数应该方在哪个对应的桶（一个一维数组）。按照这个桶的顺序（一维数组的下标依次取出数据，放入原来数组）

  3. 第二轮排序：将每个元素的十位数取出，然后看这个数应该方在哪个对应的桶（一个一维数组）。按照这个桶的顺序（一维数组的下标依次取出数据，放入原来数组）

  4. 第三轮排序：将每个元素的百位数取出，然后看这个数应该方在哪个对应的桶（一个一维数组）。按照这个桶的顺序（一维数组的下标依次取出数据，放入原来数组）

  5. import java.util.Arrays;

public class RadixSort {
    public static void main(String[] args) {
        int arr[] ={53,3,542,748,14,22,435,768};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));

    }
    public static  void radixSort(int[] arr) {

        //得到数组中最大的数的位数
        int max = arr[0];//假设第一个数就是最大数
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        //得到最大数是几位数
        int maxLength = (max + "").length();
        //第一轮：针对每个元素的个位数进行排序处理
        //定义一个二维数组，表示十个桶，每个桶就是一个一维数组
        /*
        1.二维数组包含10个一维数组
        2.为了防止在放入数的时候，数据溢出，则每一个一维数组（桶），大小定义为arr.length
        3.明确，基数排序是使用空间换时间的经典算法
         */
        int[][] bucket = new int[10][arr.length];
        //为了计录每个桶中，实际存放了多少个数据，我们定义一个一维数组来计录各个桶的每次放入
        //的数据的个数
        int[] bucketElementCounts = new int[10];

        for (int j = 0,n=1; j < maxLength; j++,n*=10) {
            //第一轮（针对每个元素的个位进行排序处理）
            for (int i = 0; i < arr.length; i++) {
                //取出每个元素的个位的值
                int digittOfElement = arr[i] /n% 10;
                //放入到对应的桶中
                bucket[digittOfElement][bucketElementCounts[digittOfElement]] = arr[i];
                bucketElementCounts[digittOfElement]++;
            }
            //按照这个桶的顺序（一维数组的下标依次取出数据，放入原来数组）
            int index = 0;
            //遍历每一桶，并将桶中的数组，放入原数组
            for (int k = 0; k < bucketElementCounts.length; k++) {
                //如果桶中有数据就放
                if (bucketElementCounts[k] != 0) {
                    for (int i = 0; i < bucketElementCounts[k]; i++) {
                        arr[index++] = bucket[k][i];
                    }
                }
                bucketElementCounts[k] = 0;
            }
        }
    }
}