常见算法总结 - 排序篇

栏目: IT技术 · 发布时间: 4年前

内容简介:本文总结了常见高频的关于排序的算法考察。冒泡排序的思想是元素两两比较,将较大或者较小的元素往一端进行移动快速排序的思想是随机选取一个数字,并以这个数字为临界点,将数组分成小于临界点的的子数组和大于临界点的子数组,并递归这个过程,即可实现最终的排序。

本文总结了常见高频的关于 排序 的算法考察。

1.冒泡排序

冒泡排序的思想是元素两两比较,将较大或者较小的元素往一端进行移动

public static void bubble(int[] array) {

        for (int i = 0; i < array.length - 1; i++) {

            for (int j = 0; j + 1 < array.length - i; j++) {

                if (array[j] > array[j + 1]) {

                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;

                }

            }

        }

}

2.快速排序

快速排序的思想是随机选取一个数字,并以这个数字为临界点,将数组分成小于临界点的的子数组和大于临界点的子数组,并递归这个过程,即可实现最终的排序。

public static void quick(int[] array, int begin, int end) {

        if (begin >= end) {
            return;
        }

        int beginRange = begin;
        int endRange = end;

        int compareInt = array[begin];

        begin++;

        while (begin < end) {

            if (array[end] > compareInt) {
                end--;
                continue;
            }

            if (array[begin] < compareInt) {
                begin++;
                continue;
            }


            int tmp = array[begin];
            array[begin] = array[end];
            array[end] = tmp;

        }

        if (array[beginRange] > array[begin]) {

            int tmp = array[begin];
            array[begin] = array[beginRange];
            array[beginRange] = tmp;

        }

        quick(array, beginRange, begin - 1);
        quick(array, end + 1, endRange);

        return;


    }

3.选择排序

选择排序的思想在于每一轮选择一个本轮的极大值,然后放入数组的尾部。最终可实现排序。

public static void selectSort(int[] array) {

        if (array.length == 0) {
            return;
        }

        for (int i = 0; i < array.length; i++) {

            int min = array[i];
            int minIndex = i;

            for (int j = i; j < array.length; j++) {
                if (array[j] < min) {
                    min = array[j];
                    minIndex = j;
                }
            }

            int tmp = array[i];
            array[i] = min;
            array[minIndex] = tmp;
        }
    }

4.归并排序

归并排序的思想在于先排序小的数组,再由小的数组合并成大数组,直到最后合并的数组大小是原数组的大小时,即完成了归并排序。

public static void sort(int[] array, int left, int right) {

        //1.设置递归的base case
        if (left == right) {
            return;
        }
        //2.分别排两边
        int mid = left + (right - left) / 2;
        sort(array, left, mid);
        sort(array, mid + 1, right);
        //3.合并
        merge(array, left, mid + 1, right);

    }

public static void merge(int[] array, int leftPtr, int rightPtr, int rightBound) {

        int mid = rightPtr - 1;
        int[] temp = new int[rightBound - leftPtr + 1];

        int i = leftPtr, j = rightPtr, k = 0;
        while (i <= mid && j <= rightBound) {
            temp[k++] = array[i] <= array[j] ? array[i++] : array[j++];
        }

        while (i <= mid) {
            temp[k++] = array[i++];
        }
        while (j <= rightBound) {
            temp[k++] = array[j++];
        }

        //不要忘了把temp数组复制到arr中
        for (int m = 0; m < temp.length; m++) {
            array[leftPtr + m] = temp[m];
        }

    }

5.桶排序

桶排序的思想在于,根据数组中的最大值和最小值的差值作为区间拆分为N个桶,将元素落入这些桶当中,进行排序再合并。

public static void bucketSort(int[] array){

        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;

        for(int i = 0; i < array.length; i++){
            max = Math.max(max, array[i]);
            min = Math.min(min, array[i]);
        }

        //桶数
        int bucketNum = (max - min) / array.length + 1;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
        for(int i = 0; i < bucketNum; i++){
            bucketArr.add(new ArrayList<Integer>());
        }

        //将每个元素放入桶
        for(int i = 0; i < array.length; i++){
            int num = (array[i] - min) / (array.length);
            bucketArr.get(num).add(array[i]);
        }

        //对每个桶进行排序
        for(int i = 0; i < bucketArr.size(); i++){
            Collections.sort(bucketArr.get(i));
        }

        int k = 0;

        for (int i = 0; i < bucketArr.size(); i++) {

            for (Integer integer : bucketArr.get(i)) {
                array[k++] = integer;
            }

        }

    }

6.计数排序

计数排序为特殊的桶排序,一个桶的值区间为1。

public static int[] countSort(int[] array) {
        if (array == null || array.length == 0) {
            return null;
        }

        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;

        //找出数组中的最大最小值
        for (int i = 0; i < array.length; i++) {
            max = Math.max(max, array[i]);
            min = Math.min(min, array[i]);
        }

        int help[] = new int[max];

        //找出每个数字出现的次数
        for (int i = 0; i < array.length; i++) {
            int mapPos = array[i] - min;
            help[mapPos]++;
        }

        int index = 0;
        for (int i = 0; i < help.length; i++) {
            while (help[i]-- > 0) {
                array[index++] = i + min;
            }
        }

        return array;
    }

7.希尔排序

希尔排序的思想在于步长。先让元素从数组的一半作为步长,进行比较替换,再依次减小步长,当步长为0时,即完成排序。它主要的优势是避免冒泡排序每次交换步长为1的低效率。

public static void shellSort(int[] arr) {
        //step:步长
        for (int step = arr.length / 2; step > 0; step /= 2) {
            //对一个步长区间进行比较 [step,arr.length)
            for (int i = step; i < arr.length; i++) {
                int value = arr[i];
                int j;

                //对步长区间中具体的元素进行比较
                for (j = i - step; j >= 0 && arr[j] > value; j -= step) {
                    //j为左区间的取值,j+step为右区间与左区间的对应值。
                    arr[j + step] = arr[j];
                }
                //此时step为一个负数,[j + step]为左区间上的初始交换值
                arr[j + step] = value;
            }
        }
}

笔者个人总结,如有错误之处望不吝指出。


以上所述就是小编给大家介绍的《常见算法总结 - 排序篇》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

软件随想录

软件随想录

Joel Spolsky / 阮一峰 / 人民邮电出版社 / 2009 / 49.00元

《软件随想录:程序员部落酋长Joel谈软件》是一部关于软件技术、人才、创业和企业管理的随想文集,作者以诙谐幽默的笔触将自己在软件行业的亲身感悟娓娓道来,观点新颖独特,内容简洁实用。全书分为 36讲,每一讲都是一个独立的专题。 《软件随想录:程序员部落酋长Joel谈软件》从不同侧面满足了软件开发人员、设计人员、管理人员及从事软件相关工作的人员的学习与工作需要。一起来看看 《软件随想录》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

MD5 加密
MD5 加密

MD5 加密工具

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具