当前位置：首页 > news >正文

【算法】【排序模块】冒泡排序和希尔排序

news 来源：原创 2024/11/16 7:44:29

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
使用冒泡排序和希尔排序对整数数组进行排序计算

解决方案

冒泡排序（从小到大）：
1、遍历每一个节点，从当前节点往回比较，比自己大的就交换，小的就退出，下一个
时间：O(n^2) 空间：O（1）
是否稳定排序：是
是否原地排序：是
希尔排序：
1、将数组分 len/2组、len/2/2组、len/2/2/2组…直到除法结果为0为止
2、每一轮分组都对每一组进行插入排序即可
时间：O(nlogn) 空间：O（1）
是否稳定排序：否
是否原地排序：是

代码编写

java语言版本

冒泡排序：

   /**
     * 冒泡排序(极简)
     * 1、跟插入整体逻辑非常像
     * 2、冒泡是一种交换排序，插入没有交换，是通过覆盖达到的部分数组后移
     * @param arr
     * @return
     */
    public static int[] BubbleSortCP(int[] arr){
        if (arr == null || arr.length == 1){
            return arr;
        }
        for (int i = 0; i < arr.length; i++){
            for (int j = i; j >= 1; j--){
                if (arr[j] < arr[j-1]){
                    CommonUtils.swap(arr, j, j-1);
                }else{
                    break;
                }
            }
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] arr = {3, 4, 1, 5, 2, 8, 6, 9};
        int[] ints = BubbleSortCP(arr);
        CommonUtils.printArr(ints);
    }

希尔排序:

    /**
     * 希尔排序
     * @param arr
     */
    public static int[] shellSortCP(int[] arr) {
        if (arr == null || arr.length == 1){
            return arr;
        }
        int len = arr.length;
        for (int i = len/2; i > 0; i /= 2) {
            // 这里的i其实是offset，也就是偏移量
            for (int j = 0; j < i; j++){
                insertSortForOffset(arr, j, i);
            }

        }
        return arr;
    }

    /**
     * 间隔元素之间的插入排序
     * @param arr
     * @param start
     * @param offset
     */
    private static void insertSortForOffset(int[] arr, int start, int offset) {
        if (arr == null || arr.length <= start){
            return;
        }
        // 从第二个元素开始，插入排序的要求
        for (int i = start+offset; i < arr.length; i += offset) {
            // 保存当前状态
            int index = i;
            int curValue = arr[i];
            // 找到第一个比自己小的
            while (index >= 0 && arr[i] <= arr[index]){
                index-=offset;
            }
            // 找到刚好不小于自己的
            index += offset;
            int move = i;
            while (move > index){
                arr[move] = arr[move - offset];
                move -= offset;
            }
            arr[move] = curValue;
        }
    }



    public static void main(String[] args) {
        int[] arr = {3, 4, 1, 5, 2, 8, 6, 9};
        int[] ints = shellSortCP(arr);
        CommonUtils.printArr(ints);
    }