常见算法总结 - 排序篇

栏目: 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;
            }
        }
}

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


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

查看所有标签

猜你喜欢:

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

ARM嵌入式系统开发

ARM嵌入式系统开发

斯洛斯 / 北京航大 / 2005-5 / 75.00元

《ARM嵌入式系统开发:软件设计与优化》从软件设计的角度,全面、系统地介绍了ARM处理器的基本体系结构和软件设计与优化方法。内容包括:ARM处理器基础;ARM/Thumb指令集;C语言与汇编语言程序的设计与优化;基本运算、操作的优化;基于ARM的DSP;异常与中断处理;固件与嵌入式OS;cache与存储器管理;ARMv6体系结构的特点等。全书内容完整,针对各种不同的ARM内核系统结构都有详尽论述,......一起来看看 《ARM嵌入式系统开发》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具