排序算法

内排

冒泡

选择

快排

public class Quicksort {
    // “挖坑填数+分治
    public static void main(String[] args) {
        int[] nums = new int[]{10,5,4,11,9,8,12,7};
        int[] nums1 = new int[]{1, 1, 6, 1, 3, 55, 12, 33,12,44,56,22,33,88};
        Quicksort1(nums, 0, nums.length - 1);
        Quicksort2(nums1, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
        System.out.println(Arrays.toString(nums1));
    }

    //这种写法 没有优化
    public static void Quicksort1(int[] nums, int start, int stop) {
        // 代表索引
        if (start>stop) {return;}

        int i = start;
        int j = stop;
        //优化方法一:基点的随机
        int index = start + (int)(Math.random()*(stop-start+1));
        int  tmp = nums[index];
        //优化方法二:基点为中间数
       // int tmp = nums[start +(stop-start) >> 1];

        while (i < j) {

                while (i < j && tmp < nums[j])
                j--;
            nums[i] = nums[j];

            while (i < j && tmp >= nums[i])
                i++;
            nums[j] = nums[i];



           /* nums[start] = nums[start] ^ nums[stop];
            nums[stop] = nums[start] ^ nums[stop];
            nums[start] = nums[start] ^ nums[stop];*/
        }
         nums[i] = tmp;
        System.out.println(Arrays.toString(nums));

        Quicksort1(nums, start, i - 1);
        Quicksort1(nums, i + 1, stop);

    }

    public static void Quicksort2(int[] arr, int begin, int end) {
        if (begin < end) {
            int temp = arr[begin]; //将区间的第一个数作为基准数
            int i = begin; //从左到右进行查找时的“指针”，指示当前左位置
            int j = end; //从右到左进行查找时的“指针”，指示当前右位置
            //不重复遍历
            while (i < j) {
                //当右边的数大于基准数时，略过，继续向左查找
                //不满足条件时跳出循环，此时的j对应的元素是小于基准元素的
                while (i < j && arr[j] > temp)
                    j--;
                //将右边小于等于基准元素的数填入右边相应位置
                arr[i] = arr[j];
                //当左边的数小于等于基准数时，略过，继续向右查找
                //(重复的基准元素集合到左区间)
                //不满足条件时跳出循环，此时的i对应的元素是大于等于基准元素的
                while (i < j && arr[i] <= temp)
                    i++;
                //将左边大于基准元素的数填入左边相应位置
                arr[j] = arr[i];
            }
            //将基准元素填入相应位置
            arr[i] = temp;
            //此时的i即为基准元素的位置
            //对基准元素的左边子区间进行相似的快速排序
            Quicksort2(arr, begin, i - 1);
            //对基准元素的右边子区间进行相似的快速排序
            Quicksort2(arr, i + 1, end);
        }
        //如果区间只有一个数，则返回
    }
}

归并

public class MergeSort {
    /**
     * Created with IntelliJ IDEA.
     * Description:
     * User:
     * Date: 2020-12-29
     * Time: 23:08
     */
    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 5, 7, 2, 6, 8, 9};
        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);
        }
    }

    //合并的方法
    //mid为中间的索引
    public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;
        //j是第二个数组的初始索引
        int j = mid + 1;
        //t 为temp的索引
        int t = 0;
        //
        while (i <= mid && j <= right) {
            //这里一定要加 + ?
            if (arr[i] <= arr[j]) {
                temp[t] = arr[i];
                t += 1;
                i += 1;
            } else {
                temp[t] = arr[j];
                t += 1;
                j += 1;
            }
        }
        //把左右边剩余的数据全部填充到临时的数组中
        while (i <= mid) {
            temp[t] = arr[i];
            t += 1;
            i += 1;
        }
        while (j <= right) {
            temp[t] = arr[j];
            t += 1;
            j += 1;

        }

        //并不是每次都拷贝....这是一个难点
        //把temp数组的元素拷贝到arr数组
        t = 0;
        int templeft = left;
        System.out.println(templeft + "  " + right);
        while (templeft <= right) {

            arr[templeft] = temp[t];
            templeft += 1;
            t += 1;
        }
    }
}

基数

public class RadixSort {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 4, 23, 2, 67, 8, 5, 2};
        //获取最大的数,并且求取位数
        int max = 0;
        for (int i : arr) {
            if (max < i) {
                max = i;
            }
        }
        int len = (max + "").length();

        sort(arr, len);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr, int len) {


        //定义桶的大小
        int[][] bucket = new int[10][arr.length];
        //定义一个计数器来统计桶中数据的多少
        int[] bucketElentCount = new int[10];
        //例如 bucketElentCount[0] = ? 为桶 0 的数据的多少,用来表示数据的位置

        //把arr中的数据放入到桶中
        //这是对个位的处理

        //循环一次处理个位 十位 百位 ......
        for (int i1 = 0, n = 1; i1 < len; i1++, n *= 10) {


            for (int i : arr) {
                //表示个位
                // int count = (i / 1) % 10;

                //表示十 百.....
                int count = (i / n) % 10;
                //bucketElentCount[count]用来统计桶的数据的多少
                bucket[count][bucketElentCount[count]] = i;
                //这个桶的计数加一
                bucketElentCount[count] += 1;
            }

            //把桶的数据拷贝到arr数组中,完成个位数的排序

            int index = 0;
            for (int k = 0; k < bucket.length; k++) {
                //遍历桶
                //某个桶有数据才把数据放置到arr数组中
                //桶里的数据仍然是存在的

                //这里为什么是0 ,为什么不能是bucket?因为bucket中数据没有清空
                if (bucketElentCount[k] != 0) {
                    for (int j = 0; j < bucketElentCount[k]; j++) {
                        arr[index] = bucket[k][j];
                        index += 1;
                    }
                }
                //把数据放置到arr之后,把计数器清0,重新开始计数
                bucketElentCount[k] = 0;

            }

        }
    }
}

堆排

外排