欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

常见算法总结 - 排序篇

程序员文章站 2024-01-10 19:41:16
本文总结了常见高频的关于排序的算法考察。 1.冒泡排序 冒泡排序的思想是元素两两比较,将较大或者较小的元素往一端进行移动 2.快速排序 快速排序的思想是随机选取一个数字,并以这个数字为临界点,将数组分成小于临界点的的子数组和大于临界点的子数组,并递归这个过程,即可实现最终的排序。 3.选择排序 选择 ......

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

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;
            }
        }
}


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

本文转自我的个人博客:《coderv的进阶笔记
欢迎加入java后端架构技术讨论群:1398880
我的公众号:coderv的进阶笔记,记录技术心得
常见算法总结 - 排序篇