博客
关于我
十大排序算法总结+工具类
阅读量:498 次
发布时间:2019-03-07

本文共 8964 字,大约阅读时间需要 29 分钟。

十大排序算法总结+工具类

总结

算法重在思想,掌握其思想基本可以将看懂别人写的代码,或能够自己写出来。如果只是使用,每一门编程语言其内部都有其排序算法,在这些算法上进行了优化,效率比这些还要高,使用即可。

在这里插入图片描述

工具类

package com.tmin;import javax.xml.transform.Result;import java.util.*;/** * @author TM * @create 2020-07-16 12:25 */public class SortUtils {       /**     * 插入排序     * @param arr 数组数据     * @param len 数组长度     */    private static void selectionSort(int[] arr, int len) {           for (int i = 0; i < len - 1; i++) {               int min = i;            for (int j = i + 1; j < len; j++) {                   if (arr[j] < arr[min]) {                       min = j;                }            }            swap(arr, i, min);        }    }    /**     * 冒泡排序     * @param arr 数组数据     * @param len 数组长度     */    private static void bubbleSort(int[] arr, int len) {           for (int i = len - 1; i > 0; i--) {               for (int j = 0; j < i; j++) {                   if (arr[j] > arr[j + 1]) {                       swap(arr, j, j + 1);                }            }        }    }    /**     * 插入排序     * @param arr 数组数据     * @param len 数组长度     */    private static void insertionSort(int[] arr, int len) {           for (int i = 1; i < len; i++) {               for (int j = i; j > 0; j--) {                   if (arr[j] < arr[j - 1]) {                       swap(arr, j, j - 1);                }            }        }    }        /**     * 希尔排序     * @param arr     * @param len     */    private static void shellSort(int[] arr, int len) {           int h = 1;        while (h <= len / 3) {               h = h * 3 + 1;        }        for (int gap = h; gap > 0; gap = (gap - 1) / 3) {               for (int i = gap; i < len; i++) {                   for (int j = i; j > gap - 1; j -= gap) {                       if (arr[j] < arr[j - gap]) {                           swap(arr, j, j - gap);                    }                }            }        }    }    /**     * 堆排序     * @param arr 数组     * @param len 数组长度     */    private static void heapSort(int[] arr, int len) {           for (int i = len; i > 0; i--) {               //堆化            heapify(arr, i);            //交换位置            swap(arr, i - 1, 0);        }    }    /**     * 堆化     * @param arr 数组     * @param len 数组长度     */    private static void heapify(int[] arr, int len) {           //非叶子结点数len/2        for (int i = len / 2 - 1; i >= 0; i--) {               int max = i;            if (2 * i + 1 < len && arr[max] < arr[2 * i + 1]) {                   max = 2 * i + 1;            }            if (2 * i + 2 < len && arr[max] < arr[2 * i + 2]) {                   max = 2 * i + 2;            }            swap(arr, i, max);        }    }    /**     * 快速排序     * @param arr 数组数据     * @param left 数组最小索引     * @param right  数组最大索引     */    private static void quickSort(int[] arr, int left, int right) {           if (left >= right) {               return;        }        //获取基点        int mid = partition(arr, left, right);        //左排序        quickSort(arr, left, mid - 1);        //右排序        quickSort(arr, mid + 1, right);    }    /**     * 数组分区     * @param arr 数组数据     * @param left 数组最小索引     * @param right 数组最大索引     * @return      基点     */    private static int partition(int[] arr, int left, int right) {           //获取随机索引        int randIndex = new Random().nextInt(right - left + 1);        //交换减小获取最大最小值的机率        swap(arr, left + randIndex, right);        //获取基准值        int pivot = arr[right];        int leftPtr = left;        int rightPtr = right - 1;        while (leftPtr <= rightPtr) {               while (leftPtr <= rightPtr && arr[leftPtr] <= pivot) {                   ++leftPtr;            }            while (leftPtr <= rightPtr && arr[rightPtr] > pivot) {                   --rightPtr;            }            if (leftPtr < rightPtr) {                   swap(arr, leftPtr, rightPtr);            }        }        swap(arr, leftPtr, right);        return leftPtr;    }    /**     * 归并排序     * @param arr 数组数据     * @param left 数组最小索引     * @param right 数组最大索引     */    private static void mergeSort(int[] arr, int left, int right) {           if (left >= right) {               return;        }        //选取中间点        int mid = left + (right - left) / 2;        //左排序        mergeSort(arr, left, mid);        //右排序        mergeSort(arr, mid + 1, right);        //进行归并        merge(arr, left, mid + 1, right);    }    /**     * 数组大数组分成两个小数组进行归并     * @param arr 数组数据     * @param left 左数组最小索引     * @param right 右数组最小索引     * @param rightBound 右数组最大索引     */    private static void merge(int[] arr, int left, int right, int rightBound) {           //创建数组        int[] temp = new int[rightBound - left + 1];        int mid = right - 1;        int leftPtr = left;        int rightPtr = right;        int index = 0;        while (leftPtr <= mid && rightPtr <= rightBound) {               if (arr[leftPtr] <= arr[rightPtr]) {                   temp[index++] = arr[leftPtr++];            } else {                   temp[index++] = arr[rightPtr++];            }        }        while (leftPtr <= mid) {               temp[index++] = arr[leftPtr++];        }        while (rightPtr <= rightBound) {               temp[index++] = arr[rightPtr++];        }        System.arraycopy(temp, 0, arr, left, temp.length);    }    /**     * 计数排序     * @param arr 数组数据     * @param len 数组长度     */    private static void countSort(int[] arr, int len) {           int[] count = new int[10];        int[] result = new int[len];        for (int i = 0; i < len; i++) {               count[arr[i]]++;        }        for (int i = 1; i < count.length; i++) {               count[i] = count[i] + count[i - 1];        }        for (int i = len - 1; i >= 0; i--) {               result[--count[arr[i]]] = arr[i];        }        System.arraycopy(result, 0, arr, 0, len);    }    /**     * 基数排序     * @param arr 数组数据     * @param len  数组长度     */    private static void radixSort(int[] arr, int len) {           //获取最大、最小值        int max = arr[0];        int min = arr[0];        for (int i = 1; i < len; i++) {               if (max < arr[i]) {                   max = arr[i];            }            if (min > arr[i]) {                   min = arr[i];            }        }        //若存在负数  将所有所有值转换为>=0的数        if (min < 0) {               //所有值都加上最小值的绝对值            for (int i = 0; i < len; i++) {                   arr[i] -= min;            }            max -= min;        }        //获取最大值位数        int n = (max + "").length();        //桶数组        int[] count = new int[10];        //临时数组        int[] temp = new int[len];        //依次对数据的个、十、百...位进行排序        for (int i = 0; i < n; i++) {               int m = (int) Math.pow(10, i);            for (int j = 0; j < len; j++) {                   //获取数据的每一位                int div = arr[j] / m % 10;                //数据入桶                ++count[div];            }            //保证数组有序            for (int j = 1; j < count.length; j++) {                   count[j] += count[j - 1];            }            //将数据存入临时数组            for (int k = len - 1; k >= 0; k--) {                   //获取数据的每一位                int div = arr[k] / m % 10;                temp[--count[div]] = arr[k];            }            System.arraycopy(temp, 0, arr, 0, len);            //将桶中数据个数置零            Arrays.fill(count, 0);        }        //将数据还原        if (min < 0) {               for (int i = 0; i < len; i++) {                   arr[i] += min;            }        }    }    /**     * 桶排序     * @param arr        数组     * @param bucketLen 每个桶的长度     */    private static void bucketSort(int[] arr, int bucketLen) {           //获取数组中的最大最小值        int min = arr[0];        int max = arr[0];        for (int i = 1; i < arr.length; i++) {               if (min > arr[i]) {                   min = arr[i];            }            if (max < arr[i]) {                   max = arr[i];            }        }        //根据数据区间以及每个桶中数据的个数  获取需要桶的个数  边界问题 +1        int bucketCount = (max - min) / bucketLen + 1;        //对数据进行分桶        List
> lists = new ArrayList
>(bucketCount); //初始化 for (int i = 0; i < bucketCount; i++) { lists.add(new ArrayList
()); } //将数据分配到桶中 for (int k : arr) { lists.get((k - min) / bucketLen).add(k); } //对每个桶中的数据进行排序 for (int i = 0; i < bucketCount; i++) { Collections.sort(lists.get(i)); } //将桶中的数据复制到原数组 int index = 0; for (int i = 0; i < bucketCount; i++) { for (int j = 0; j < lists.get(i).size(); j++) { arr[index++] = lists.get(i).get(j); } } } private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } private static void printf(int[] arr) { for (int i : arr) { System.out.print(i + " "); } System.out.println(); }

最后

对于详细注解,可以看下我单独介绍每一种排序算法的文章。

转载地址:http://lobcz.baihongyu.com/

你可能感兴趣的文章
mysql 死锁(先delete 后insert)日志分析
查看>>
MySQL 死锁了,怎么办?
查看>>
MySQL 深度分页性能急剧下降,该如何优化?
查看>>
MySQL 深度分页性能急剧下降,该如何优化?
查看>>
MySQL 添加列,修改列,删除列
查看>>
mysql 添加索引
查看>>
MySQL 添加索引,删除索引及其用法
查看>>
mysql 状态检查,备份,修复
查看>>
MySQL 用 limit 为什么会影响性能?
查看>>
MySQL 用 limit 为什么会影响性能?有什么优化方案?
查看>>
MySQL 用户权限管理:授权、撤销、密码更新和用户删除(图文解析)
查看>>
mysql 用户管理和权限设置
查看>>
MySQL 的 varchar 水真的太深了!
查看>>
mysql 的GROUP_CONCAT函数的使用(group_by 如何显示分组之前的数据)
查看>>
MySQL 的instr函数
查看>>
MySQL 的mysql_secure_installation安全脚本执行过程介绍
查看>>
MySQL 的Rename Table语句
查看>>
MySQL 的全局锁、表锁和行锁
查看>>
mysql 的存储引擎介绍
查看>>
MySQL 的存储引擎有哪些?为什么常用InnoDB?
查看>>