美文网首页Java学习笔记
几大排序算法的Java实现(原创)

几大排序算法的Java实现(原创)

作者: ReentrantSucc | 来源:发表于2018-04-23 17:30 被阅读71次

几大排序算法的Java实现

更新中...

注:

  1. 该类中附有随机生成[min, max)范围不重复整数的方法,如果各位看官对此方法有什么更好的建议,欢迎提出交流。
  2. 各个算法的思路都写在该类的注释中了,同时也方便各位进行本地环境验证。
  3. 目前已完成的排序算法有:冒泡排序、选择排序、插入排序。
  4. 暂时只提供这些排序算法的基本版,对算法的改进暂时不做考虑。
  5. 如果想看的更直观些,欢迎访问一个可视化的排序网站

import static org.junit.Assert.*;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import org.junit.Test;

public class SortTest {
    
    /**
     * 用来存储给定范围内所有的整数
     */
    private static List<Integer> numList = new ArrayList<>();
    
    /**
     * 返回随机生成的[min, max)之间的整数数组
     * @param min 最小值
     * @param max 最大值(不包含)
     * @return
     */
    public static Integer[] generateRandomNum(int min, int max) {
        return generateRandomNum(min, max, (max - min));
    }
    
    /**
     * 返回随机生成的[min, max)之间的整数数组,个数为num个
     * @param min
     * @param max
     * @param num 要生成的随机数个数
     * @return
     */
    public static Integer[] generateRandomNum(int min, int max, int num) {
        long start = System.currentTimeMillis();
        List<Integer> result = new ArrayList<>();
        for (int i = min; i < max; i++) {
            numList.add(i);
        }
        for (int i = 0; i < num; i++) {
            result.add(generateOneNum(min, max));
        }
        long end = System.currentTimeMillis();
        System.out.println("生成的随机数组范围是:[" + min + ", " + max + "), 个数: " + num + ", 耗时: " + (end - start) / 1000.0 + "s.\n待排序数组为: " + result);
    
        return result.toArray(new Integer[]{});
    }

    // 读取numList中的任意元素
    private static int generateOneNum(int min, int max) {
        return (int) numList.remove((int) (Math.random() * numList.size()));
    }

    /**
     * 冒泡排序算法, 时间复杂度是O(n^2)
     * @throws Exception
     */
    @Test
    public void testBubbleSort() throws Exception {
//      Integer nums[] = { 67, 1, 69, 43, 7, 56, 34, 111, 87, 62, 89, 90, 31, 99, 100 };
        Integer[] nums = generateRandomNum(1, 100, 10);
        // 第一层for循环控制排序趟数。Reason: 1个数字->0趟排序,2个数字->1趟排序,3个数字->2趟排序
        for (int i = 0; i < nums.length - 1; i++) {
            // 第二层for循环控制本趟排序的比较过程
            for (int j = 0; j < nums.length - 1 - i; j++) {
                // 进行两两比较,如果后面的比前面小,则交换位置,则每进行一趟排序,最后一个数字都是该趟排序中最大的数字
                if (nums[j] > nums[j + 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
            System.out.println("第" + (i + 1) + "趟排序结果为:" + Arrays.toString(nums));
        }
    }
    
    /**
     * 选择排序
     * @throws Exception
     */
    @Test
    public void testSelectionSort() throws Exception {
        Integer[] nums = generateRandomNum(1, 100, 10);
        for (int i = 0; i < nums.length - 1; i++) {// 仍旧是控制排序的趟数
            int minIndex = i;
            // 该层for循环就是为了找到最小的数字并和未排序的所有数字中的首位进行交换
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                // 交换该趟排序中最小的数和未排序的数中首位数字
                int tmp = nums[minIndex];
                nums[minIndex] = nums[i];
                nums[i] = tmp;
            }
            System.out.println("第" + (i + 1) + "趟排序结果为: " + Arrays.toString(nums));
        }
    }

    /**
     * 插入排序: 到要插入的数,跟已经排好序的数做比对,如果该数小于之前的数,则之前的数向后移动一位,如果出现
     * 大于某个数,则在该位置插入数
     * @throws Exception
     */
    @Test
    public void testInsertSort() throws Exception {
        Integer[] nums = generateRandomNum(1, 100, 10);
        for (int i = 1; i < nums.length; i++) {// 第一层for循环解决趟数
            int j = i;
            int target = nums[i];// 获取要插入的那个数
            // 因为当插入的数比原本已排好序列中的数大时停止比较,所以采用while
            while (j > 0 && target < nums[j - 1]) {
                nums[j] = nums[j - 1];// j位置放j-1处的值,相当于该值后移一位
                j--;
            }
            // 结束while循环时target > nums[j - 1]
            nums[j] = target;
            
            System.out.println("第" + (i + 1) + "趟排序结果为: " + Arrays.toString(nums));
        }
    }
    
    /**
     * 快速排序
     * @throws Exception
     */
    @Test
    public void testQuickSort() throws Exception {
        Integer[] nums = generateRandomNum(1, 100, 10);
    }
    /**
     * 关于位运算: 1 ^ 正奇数 = 正奇数 - 1
     * @throws Exception
     */
    @Test
    public void testName() throws Exception {
        for (int i = 0; i < 101; i++) {
             System.out.println(1 ^ (2*i + 1));
        }
    }
    
}


相关文章

  • 数据结构&算法(一)

    一、Java实现快速排序算法 二、Java实现折半插入排序算法 三、Java实现冒泡排序算法

  • 几大排序算法的Java实现(原创)

    几大排序算法的Java实现 更新中... 注: 该类中附有随机生成[min, max)范围不重复整数的方法,如果各...

  • java 实现排序算法之「插入排序」

    java 实现排序算法系列 这是 Java 实现排序算法的第三篇文章——插入排序算法。插入排序可以说成是「一类」简...

  • 排序

    八大排序算法 一、归并排序 递归及非递归的JAVA实现 二、快速排序 快排算法JAVA实现 三、堆排序 堆排序堆排...

  • 一文搞定十大经典排序算法(Java实现)

    本文总结十大经典排序算法及变形,并提供Java实现。参考文章:十大经典排序算法总结(Java语言实现)快速排序算法...

  • 快速排序

    手写java版快速排序算法实现

  • 排序算法最强总结及其代码实现(Python/Java)

    前言 本文总结了常用的全部排序算法,内容包括: 排序算法的定义和思路 排序算法的代码实现:Python和Java,...

  • 排序算法

    常见排序算法比较 参考资料:各种排序算法比较 参考资料:快速排序算法 必须知道的八大种排序算法【java实现】(一...

  • 【算法】排序(一)选择排序

    在排序算法中,最简单的莫过于选择排序了。 本文将介绍以下内容 排序思路算法实现(JAVA)测试阶段算法分析 排序思...

  • 7大经典的排序算法总结实现

    作者 : 专注J2EE来源 : 博客园 常见排序算法总结与实现 本文使用Java实现这几种排序。以下是对排序算法总...

网友评论

    本文标题:几大排序算法的Java实现(原创)

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