专栏首页后端码事基本排序算法(冒泡排序 选择排序 插入排序 快速排序 归并排序 基数排序 希尔排序)

基本排序算法(冒泡排序 选择排序 插入排序 快速排序 归并排序 基数排序 希尔排序)

项目地址:https://github.com/windwant/windwant-service/tree/master/algorithm

冒泡排序:两两比较,大数冒泡

升序:

public static void bubbleSort(int[] arr){
        int lgn = arr.length;
        for (int i = 0; i < lgn - 1; i++) {
            for (int j = 0; j < lgn - 1 - i; j++) {
                if(arr[j] > arr[j + 1]){
                    int temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }

降序:

...

选择排序:选择剩余元素中最小(最大)的元素放置到初始选择集合中(空)

public static void SelectionSortAsc(int[] arr){
    int min = 0;
    for (int i = 0; i < arr.length - 1; i++) {
        min = i;
        for (int j = i + 1; j < arr.length ; j++) {
            if(arr[j] < arr[min]){
                min = j;
            }
        }
        if(min != i){
            int tmp = arr[i];
            arr[i] = arr[min];
            arr[min] = tmp;
        }
    }
}

public static void SelectionSortDesc(int[] arr){
    int max = 0;
    for (int i = 0; i < arr.length - 1; i++) {
        max = i;
        for (int j = i + 1; j < arr.length ; j++) {
            if(arr[j] > arr[max]){
                max = j;
            }
        }
        if(max != i){
            int tmp = arr[i];
            arr[i] = arr[max];
            arr[max] = tmp;
        }
    }
}

插入排序:设定一个初始已排序的集合(一般选择一个元素),从剩余的集合中将各个元素以此插入到初始集合中的正确位置

public static void insertionSort(int [] array){
        for(int i = 1; i < array.length; i++){
            int temp = array[i];//被标记的值或者说是当前需要插入的值
            int j = i;
            //如果轮循值大于被标记值则往后移
            while( j > 0 && temp < array[j - 1]){
                array[j] = array[j - 1];
                j-- ;
            }
            //将被标记值插入最终移出的空位置
            array[j] = temp;
        }
    }

快速排序:选取锚点,划分小于,大于两个集合,递归处理子集合

public static void quikeSort(int[] arr, int low, int high) {
        int start = low;
        int end = high;
        int anchor = arr[low];

        while (end > start) {
            //比较 anchor---end
            while (end > start && arr[end] >= anchor) {  //从末尾向前寻找小于等于anchor的值
                end--;
            }

            //交换位置
            if (arr[end] <= anchor) {
                int temp = arr[end];
                arr[end] = arr[start];
                arr[start] = temp;
            }

            //比较start---anchor
            while (end > start && arr[start] <= anchor) {//从起始位置向后寻找大于等于anchor的值
                start++;
            }

            //交换位置
            if (arr[start] >= anchor) {
                int temp = arr[start];
                arr[start] = arr[end];
                arr[end] = temp;
            }
        }
        //anchor位置确定。左边的元素值都小于anchor值,右边的值都大于anchor值,递归排序左右两侧排序
        //左边元素。low---anchor值索引-1
        if (start > low) {
            quikeSort(arr, low, start - 1);
        }

        //右边元素。从anchor值索引+1---high
        if (end < high) {
            quikeSort(arr, end + 1, high);
        }
    }

归并排序:中分两个结合,分别归并排序,然后合并两个有序结合;递归进行

public static void mergeSort(int[] data) {
        sort(data, 0, data.length - 1);
    }

    public static void sort(int[] data, int left, int right) {
        if (left >= right)
            return;
        // 找出中间索引
        int center = (left + right) / 2;
        // 对左边数组进行递归
        sort(data, left, center);
        // 对右边数组进行递归
        sort(data, center + 1, right);
        // 合并
        merge(data, left, center, right);
    }

    /**
     * 将两个数组进行归并,归并前面2个数组已有序,归并后依然有序
     *
     * @param data
     *            数组对象
     * @param left
     *            左数组的第一个元素的索引
     * @param center
     *            左数组的最后一个元素的索引,center+1是右数组第一个元素的索引
     * @param right
     *            右数组最后一个元素的索引
     */
    public static void merge(int[] data, int left, int center, int right) {
        // 临时数组
        int[] tmpArr = new int[data.length];
        // 右数组第一个元素索引
        int mid = center + 1;
        // third 记录临时数组的索引
        int third = left;
        // 缓存左数组第一个元素的索引
        int tmp = left;
        while (left <= center && mid <= right) {
            // 从两个数组中取出最小的放入临时数组
            if (data[left] <= data[mid]) {
                tmpArr[third++] = data[left++];
            } else {
                tmpArr[third++] = data[mid++];
            }
        }
        // 剩余部分依次放入临时数组(实际上两个while只会执行其中一个)
        while (mid <= right) {
            tmpArr[third++] = data[mid++];
        }
        while (left <= center) {
            tmpArr[third++] = data[left++];
        }
        // 将临时数组中的内容拷贝回原数组中
        // (原left-right范围的内容被复制回原数组)
        while (tmp <= right) {
            data[tmp] = tmpArr[tmp++];
        }
    }

基数排序:逐位排序

//LSD
    public static void radixLSDSort(int[] arr){
        //最高位数
        int maxBit = getMaxBit(arr);
        //十个bulk 分别存放 每个位数 数字 相应的元素 如个位为3 则放入bulk[3]
        Queue<Integer>[] bulk = new Queue[10];
        for (int i = 0; i < bulk.length; i++) {
            bulk[i] = new ArrayDeque();
        }
        //分别处理不同位数 存放 处理
        for (int i = 0; i < maxBit; i++) {
            for (int j = 0; j < arr.length; j++) {
                int ivalue = (int) (arr[j] % Math.pow(10, i + 1) / Math.pow(10, i)); //去相应位数上的数字作为 存入bulk index
                bulk[ivalue].offer(arr[j]);
            }

            //取出bulk中的元素 重新放入数组 并清除bulk中的元素。
            int arrIndex = 0;
            for (int j = 0; j < bulk.length; j++) {
                while (bulk[j].size()>0){
                    arr[arrIndex++] = bulk[j].poll();
                }
            }
        }
    }

    public static int getMaxBit(int[] arr){
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if(arr[i] > max){
                max = arr[i];
            }
        }

        int b = 0;
        while (max > 0){
            max /= 10;
            b++;
        }
        return b;
    }

    public static void radixMSDSort(int[] arr){
        msdSort(arr, 0, arr.length, getMaxBit(arr));
    }

    //MSD
    public static void msdSort(int[] arr, int left, int right, int maxBit){
        //十个bulk 分别存放 每个位数 数字 相应的元素 如个位为3 则放入bulk[3]
        Queue<Integer>[] bulk = new Queue[10];
        for (int i = 0; i < bulk.length; i++) {
            bulk[i] = new ArrayDeque();
        }
        //依据最高位分别放入不同的bulk
        for (int j = left; j < right; j++) {
            int ivalue = (int) (arr[j] % Math.pow(10, maxBit) / Math.pow(10, maxBit - 1)); //去相应位数上的数字作为 存入bulk index
            bulk[ivalue].offer(arr[j]);
        }

        //取出bulk中的元素 重新放入数组 并清除bulk中的元素。记录bulk中queue大小大于1的数组索引 递归使用
        List<Integer> count = new ArrayList<Integer>();
        int arrIndex = left;
        for (int j = 0; j < bulk.length; j++) {
            int start = arrIndex;
            while (bulk[j].size()>0){
                arr[arrIndex++] = bulk[j].poll();
            }
            if(arrIndex - start > 1){
                count.add(start);
                count.add(arrIndex);
            }
        }
        //递归最小位判断
        int nextBit = maxBit - 1;
        if(nextBit > 0) {
            for (int i = 1; i < count.size(); i += 2) {
                msdSort(arr, count.get(i - 1), count.get(i), nextBit);
            }
        }
    }

shell排序:插入排序+步长改进

public static void shellSort(int[] arr){
        int step = arr.length/2;
        while (step >= 1) { //步长为1时 包含所有数组序列
            for (int i = 0; i < step; i++) { //步长为n则数组将分为n组分别排序
                for (int j = step + i; j < arr.length; j += step) { //对跨步长每组元素进行插入排序
                    int temp = arr[j];
                    int preIndex = j - step;
                    while (preIndex > -1 && temp < arr[preIndex]) {
                        arr[preIndex + step] = arr[preIndex];
                        preIndex -= step;
                    }
                    arr[preIndex + step] = temp;
                    System.out.println(" middle: " + Arrays.toString(arr));
                }
            }
            step /= 2; //每次步长处理
        }
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 从零开始认识堆排序

    维基百科的解释是:堆是一种特别的树状数据结构,它需要满足任意的子节点必须都大于等于(最大堆)或者小于等于(最小堆)其父节点。

    WindWant
  • 台阶很高,青蛙跳不跳?

    一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法?

    WindWant
  • PHP 替换标签和标签内的内容

    $filter_arr=array('/#(.*?)#/','/\$(.*?)\$/','/\^(.*?)\^/');//要替换的标签

    WindWant
  • 快速排序与寻找第k小的数算法

    慕课网 首发了,放在垂直领域吧。简书备份。 出现了一点小问题,就是index,要注意。想法网上一大堆,不多说了。 ubuntu18下输入法有问题,sogou...

    东风冷雪
  • 2个线性表查找的优化

    实际上,如果待查的数据比较均匀,那么1/2是一个很好的选择,一旦待查数据中的数据是极度不均匀的,那么就需要考虑插值查找法。

    大学里的混子
  • 排序算法之快速排序

    快速排序是一种非常优秀的排序算法,应用的也非常广泛,面试时面试官也经常让你手写一个快排,所以说学习快速排序是非常有必要的。

    dejavu1zz
  • 调整数组顺序使奇数位于偶数前面

    输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相...

    用户3003813
  • 归并排序

    用户6055494
  • [Go] Golang练习项目-快速排序的GO语言实现

    快速排序首先选一个基准(你也可以认为是要放到排序后数组正确位置的元素)pivot,然后将数组按照选取的基准 pivot 进行划分。而选取 pivot 的方式又有...

    陶士涵
  • Sort Algorithm

    生成随机的n个数量的数组,输出数组每一个元素的内容。测试排序算法使用的标准就是运行时间和排序的正确性,所以需要一个验证正确性和计算排序时间的:

    西红柿炒鸡蛋

扫码关注云+社区

领取腾讯云代金券