排序面试-java版

作者: 小楠总 | 来源:发表于2016-10-12 21:57 被阅读1217次
    image

    冒泡排序

    /**
     * 从后往前,不断向前比较,小的向前面浮起来(交换)
     * 如果发现一趟排序没有交换,那么flag=false,程序就提前退出了
     * 时间复杂度O(n^2)
     */
    private static int[] bubbleSort(int[] arr) {
        boolean flag = true;
        for (int i = 0; i < arr.length && flag; i++) {
            flag = false;
            for (int j = arr.length - 1; j > i; j--) {
                if (arr[j] < arr[j - 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
    
                    flag = true;
                }
            }
        }
        return arr;
    }
    

    插入排序

    /**
     * 基本思想:在要排序的一组数中,假设前面n-1个数已经是排好顺序的,
     * 把第n个数插到前面的有序数中,使得这n个数也是排好顺序的。如此反复循环。
     * 时间复杂度O(n^2)
     */
    private static int[] insertSort(int[] arr) {
    
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < arr[i - 1]) {
                //假设下标i前面的数已经排好序,把当前下标i的元素插入到前面
                //具体插入位置:如果前面的元素比下标i的元素小,不断向前覆盖一格
                //最后把下标i的元素插入到正确位置
                int temp = arr[i];
                int j = i - 1;
                for (; j >= 0 && arr[j] > temp; j--) {
                    arr[j + 1] = arr[j];
                }
                arr[j + 1] = temp;
            }
        }
        return arr;
    }
    

    选择排序

    /**
     * 选择排序的思想是,先假设一个为最小,然后用剩下的元素去比较
     * 如果发现有比假设值小的,先把下标记录下来,最后再进行交换
     * 时间复杂度O(n^2)
     */
    private static int[] selectSort(int[] arr) {
    
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;//先选择一个最小的,然后用其他去跟这个比较,直到找到最小的那个为止
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    //先记录下来,最后再交换
                    min = j;
                }
            }
            if (min != i) {
                int temp = arr[min];
                arr[min] = arr[i];
                arr[i] = temp;
            }
        }
        return arr;
    }
    

    快速排序

    /**
     * 快速排序
     * 时间复杂度O(n * log(n))
     * 优化方式:1三数取中 2优化不必要的交换 3小数组的方案 4尾递归优化
     *
     * @return 返回排序后的数组
     */
    private static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            //计算基准点
            int pivot = partition(arr, low, high);
            //分别对基准点左右两边进行递归
            quickSort(arr, low, pivot - 1);
            quickSort(arr, pivot + 1, high);
        }
    }
    
    private static int partition(int[] arr, int low, int high) {
        int pivotKey = arr[low];
        while (low < high) {
            while (low < high && arr[high] >= pivotKey) {
                high--;
            }
            System.out.println("交换" + low + ":" + high);
            swap(arr, low, high);
            System.out.println(Arrays.toString(arr));
            while (low < high && arr[low] <= pivotKey) {
                low++;
            }
            swap(arr, low, high);
        }
        return low;
    }
    

    希尔排序

    /**
     * 希尔排序,元素的分组跳跃式排序
     * 直接插入排序的改版
     * 时间复杂度O(n * log(n))
     */
    private static int[] shellSort(int[] arr) {
    
        int inc = arr.length;
        do {
            inc = inc / 3 + 1;
            for (int i = inc; i < arr.length; i++) {
                if (arr[i] < arr[i - inc]) {
                    int temp = arr[i];
                    int j = i - inc;
                    for (; j >= 0 && arr[j] > temp; j = j - inc) {
                        arr[j + inc] = arr[j];
                    }
                    arr[j + inc] = temp;
                }
            }
        } while (inc > 1);
        return arr;
    }
    

    归并排序

    /**
     * 归并排序
     * 时间复杂度O(n * log(n))
     */
    private static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            //数组拆分
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            //拆到不能再拆的时候,开始合并
            merge(arr, left, right);
        }
    }
    
    private static void merge(int[] arr, int left, int right) {
        int[] temp = new int[arr.length];
        int mid = (left + right) / 2;
        int i = left;
        int j = mid;
        int k = left;
        //逐一比较大小,把小的存到临时数组里面
        while (i < mid && j < right) {
            if (arr[i] < arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        //把剩下的元素写进去
        while (i < mid) {
            temp[k++] = arr[i++];
        }
        while (j < right) {
            temp[k++] = arr[j++];
        }
        //把临时数组的内容拷贝回去
        int l = left;
        while (l < right) {
            arr[l] = temp[l];
            l++;
        }
    }
    

    堆排序

    /**
     * 堆排序是通过不断构造大顶堆
     * 时间复杂度O(n * log(n))
     */
    private static int[] heapSort(int[] arr) {
        int len = arr.length - 1;
        //从下往上,从右往左构建大顶堆
        for (int i = len / 2; i > 0; i--) {
            adjust(arr, i, len);
        }
        for (int i = len; i > 1; i--) {
            //交换最后一个元素与大顶堆的根结点
            int temp = arr[i];
            arr[i] = arr[1];
            arr[1] = temp;
            adjust(arr, 1, i - 1);
        }
        return arr;
    }
    
    private static void adjust(int[] arr, int s, int m) {
        int temp = arr[s];
        for (int i = s * 2; i <= m; i = i * 2) {
            //判断左右子结点哪个大
            if (i < m && arr[i] < arr[i + 1]) {
                i++;
            }
            //如果当前的双亲结点是最大的那个,那么不用继续调整
            if (temp >= arr[i]) {
                break;
            }
            //把当前左右结点中的最大值赋值给双亲结点
            arr[s] = arr[i];
            //以当前最大结点为双亲结点,继续下一次循环,直到找到
            //temp应该存放的位置为止
            s = i;
        }
        //找到temp应该存放的位置
        arr[s] = temp;
    }
    

    如果觉得我的文字对你有所帮助的话,欢迎关注我的公众号:

    公众号:Android开发进阶

    我的群欢迎大家进来探讨各种技术与非技术的话题,有兴趣的朋友们加我私人微信huannan88,我拉你进群交(♂)流(♀)

    相关文章

      网友评论

        本文标题:排序面试-java版

        本文链接:https://www.haomeiwen.com/subject/bnaiyttx.html