Java实现排序算法(暂时七个)

文章目录

- - 冒泡排序
  - 选择排序
  - 插入排序
  - 希尔排序
  - 快速排序
  - 归并排序
  - 基数排序

冒泡排序

【总结：就是比较相邻元素，逆序则交换，每一趟循环可以找出最大的元素放在数组末尾】

基本思想：通过对待排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前向后，就像水下的气泡一样逐渐向上冒

因为在排序的过程中，各元素不断的接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此在排序的过程中设置一个标志flag判断元素是否进行过交换，从而减少不必要的比较

思路分析：

每次都和相邻的元素进行比较
如果相邻的元素存在逆序的情况【升序排序】，则进行交换

/**
 * @author wjq
 * @create 2021-05-21 8:30
 * 思想：在每一次的循环排序中，相邻的两个元素比较，将最大的找出来，将其放在最后，即每次循环都可以找到一个最大的元素
 */
public class BubbleSort {
    public static void main(String[] args) {
        int arr[] = {3, 9, -1, 10, -2};
        System.out.println("排序前:" + Arrays.toString(arr));
        int temp;
        for (int i = 0; i < arr.length - 1; i++) {//一共是n-1次循环
            for (int j = 0; j < arr.length - i - 1; j++) {//每次排序的元素是n-1  n-1-1  n-1-1-1...
                if (arr[j] > arr[j + 1]) {//当出现逆序则交换
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        System.out.println("排序后:" + Arrays.toString(arr));
    }
}

小结

一共进行n-1次的循环
在每一次的循环中，元素都会减少
如果在某一次循环中，发先没有交换元素，此时可以结束冒泡排序（优化）

//优化
   @Test
    public void better() {
       int arr[] = {-1, 3, 9, 20, 10};
       System.out.println("排序前:" + Arrays.toString(arr));
       int temp;
       boolean flag = true;//用于判断是否进入了交换元素
       for (int i = 0; i < arr.length - 1; i++) {//一共是n-1次循环
           for (int j = 0; j < arr.length - i - 1; j++) {//每次排序的元素是n-1  n-1-1  n-1-1-1...
               if (arr[j] > arr[j + 1]) {//当出现逆序则交换
                   flag = false;
                   temp = arr[j];
                   arr[j] = arr[j + 1];
                   arr[j + 1] = temp;
               }
           }
           if (flag) {
               break;//没有进入交换，即此时有序，直接跳出循环
           }else {
               flag = true;//再将标志改为true，用于下一趟循环的判断
           }
           System.out.println("第" + (i + 1) + "次排序后:" + Arrays.toString(arr));
       }
//       System.out.println("排序后:" + Arrays.toString(arr));
    }

对80000个数据进行排序的耗时

//耗时
    @Test
    public void time() {
        int[] arr = new int[80000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int)(Math.random() * 80000);//[0,80000)
        }

//        long start = System.currentTimeMillis();
//        bubbleSort(arr);
//        long end = System.currentTimeMillis();
//        System.out.println("耗时为：" + (end - start));


        long start1 = System.currentTimeMillis();
        bubbleSort1(arr);
        long end1 = System.currentTimeMillis();
        System.out.println("优化后的耗时为：" + (end1 - start1));//因为随机性比较大，优化不明显，优化是对相对有序的数组来说比较明显
    }

Java实现排序算法(暂时七个)

选择排序

选择排序也属于内部排序，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的

思路分析：

先指定每一次排序的第一个元素为最小元素
与后面元素进行比较，如果有更小的则将更小的标记为最小元素
经过一轮，可知此轮的最小元素
将最小元素与a[0]进行交换
即可完成一轮的排序

@Test
    public static void selectSort(int arr[]) {
//        arr = new int[]{101, 34, 119, 1};
        for (int i = 0; i < arr.length - 1; i++) {//总共循环的次数
            int min = arr[i];//先默认将第一个元素看成最小的，进行比较
            int minIndex = i;
            for (int j = 1 + i; j < arr.length; j++) {//求出真正的最小值
                if (min > arr[j]) {//如果最小值较大，则交换
                    min = arr[j];
                    minIndex = j;
                }
            }
            if (minIndex != i) {//如果最小值与交换的值不在同一位置
                arr[minIndex] = arr[i];//实现交换，arr[minIndex]就相当于temp
                arr[i] = min;
            }
        }
//        System.out.println("排序后：" + Arrays.toString(arr));
    }

对80000个数据排序的耗时

@Test
public static void time() {
    int[] arr = new int[80000];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = (int)(Math.random() * 80000);//[0,80000)
    }

    long start = System.currentTimeMillis();
    selectSort(arr);
    long end = System.currentTimeMillis();
    System.out.println("耗时为：" + (end - start));
}

Java实现排序算法(暂时七个)

插入排序

属于内部排序，是对欲排序的元素以插入的方式找寻该元素的适当位置

思路分析：

第一个元素默认为有序的，从第二个元素开始
先定位待插入的元素以及要插入的位置
当下标越界以及待插入的元素比其前面的元素大等的时候跳出循环
1. 将大的元素后移
2. 待插入元素的下标前移
将之前保存的待插入的元素放入跳出循环后的位置+1的地方

public static void insertSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {//第一个元素是有序的
            int insetVal  = arr[i + 1];//待插入的元素，从第二个元素开始
            int insertIndex = i;//插入的位置，在其位置的前面
            while (insertIndex >= 0 && insetVal < arr[insertIndex]) {//当下标越界(-1)或者待插入的元素大于等于其之前的元素，跳出循环
                arr[insertIndex + 1] = arr[insertIndex];//将有序的元素后移
                insertIndex--;//代插入的元素的下标前移
            }
            if (insertIndex + 1 != (i + 1)) {//当要插入的位置与插入元素的位置不同时，才插入
                arr[insertIndex + 1] = insetVal;//将待插入的元素插入，并且实现跳出循环
            }
        }
//        System.out.println("排序后：" + Arrays.toString(arr));
    }

对80000个数据排序的耗时

@Test
public static void time() {
    long start = System.currentTimeMillis();
    int[] arr = new int[80000];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = (int) (Math.random() * 80000);
    }
    insertSort(arr);
    long end = System.currentTimeMillis();
    System.out.println("消耗的时间：" + (end - start));
}

Java实现排序算法(暂时七个)

希尔排序

分为交换法（效率低）和移动法（效率高）

也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序

对每组使用直接插入排序算法排序，随着增量逐渐减少，每组包含的关键字越来越多，当增量减至1时，整个文件恰好被分成1组，算法终止

交换法

未优化的（交换法）

@Test    
public static void shellSort(int arr[]) {        
int temp = 0;        
for (int gap = arr.length / 2; gap > 0; gap /= 2) {//本质是增量缩减，gap表示步长，步长每次/2，            
    for (int i = gap; i < arr.length; i++) {//对每一次步长的循环次数                
	    for (int j = i - gap ; j >= 0; j -= gap) {//在gap长的情况下交换的元素                    
		    if (arr[j] > arr[j + gap]) {                        
			    temp = arr[j];                        
			    arr[j] = arr[j + gap];                        
			    arr[j + gap] = temp;                    
		    }                
	    }            
    }        
}
//        System.out.println("排序后：" + Arrays.toString(arr));   
 }

对80000个数据进行排序的时间

Java实现排序算法(暂时七个)

移动法

优化后

public static void shellSort1(int arr[]) {//移动法
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {//表示gap增量
            for (int i = gap; i < arr.length; i++) {//此时开始用插入排序
                int insertIndex = (i - gap);
                int insertVal = arr[i];
                while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                    arr[insertIndex + gap] = arr[insertIndex];
                    insertIndex -= gap;
                }
                arr[insertIndex + gap] = insertVal;//为什么要加gap，因为上面是由于多减了一个gap，越界跳出循环，这里应该加上
            }
        }
//        System.out.println("移动法排序后：" + Arrays.toString(arr));
    }

对80000个数据进行排序

@Test
    public static void time() {
        long start = System.currentTimeMillis();
        int[] arr = new int[80000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 80000);
        }
//        shellSort(arr);
        shellSort1(arr);

        long end = System.currentTimeMillis();
        System.out.println("消耗的时间：" + (end - start));
    }

Java实现排序算法(暂时七个)

对8000000

Java实现排序算法(暂时七个)

快速排序

是对冒泡排序的一种改进，将数字分成左右两部分，一部分比另一部分小，然后左右分别递归排序，以达到整个数组有序

public static void quickSort(int[] arr, int left, int right) {
    int l = left;//左下标
    int r = right;//右下biao
    int mid = arr[(left + right) / 2];//中间元素
    while (l < r) {
        while (arr[l] < mid) {
            l++;
        }
        while (arr[r] > mid) {
            r--;
        }
        //交换元素
        int temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
        //当出现相同元素时，需要此步骤，否则会是死循环
        if (arr[l] == mid) {
            r--;
        }
        if (arr[r] == mid) {
            l++;
        }
    }
    //此步骤也是避免死循环
    if (l == r) {
        l++;
        r--;
    }
    //左边递归
    if (left < r) {
        quickSort(arr, left, r);
    }
    //右边递归
    if (right > l) {
        quickSort(arr, l, right);
    }
}

对80000个数据排序

@Test
public static void time() {
    long start = System.currentTimeMillis();
    int[] arr = new int[80000];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = (int) (Math.random() * 80000);
    }
    quickSort(arr, 0, arr.length - 1);
    long end = System.currentTimeMillis();
    System.out.println("消耗的时间：" + (end - start));
}

Java实现排序算法(暂时七个)

对8000000

Java实现排序算法(暂时七个)

归并排序

利用归并思想实现的排序，该算法采用经典的分治策略（分：分成小模块递归求解；治：分段得到的各答案“修补”在一起，即分而治之）

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {9, 8, 3, 6, 5, 9, 1, 2, 3};
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void mergeSort(int[] arr){
        int[] temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);
    }

    //递归分解+合并
    private static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;
            //左边递归
            mergeSort(arr, left, mid, temp);
            //右边递归
            mergeSort(arr, mid + 1, right, temp);
            merge(arr, left, mid, right, temp);
        }
    }

    //合并
    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        //定义左边有序数组的第一个索引
        int i = left;
        //定义右边有序数组的第一个索引
        int j = mid + 1;
        //定义临时数组的索引
        int t = 0;
        //将左右数组进行比较，将较小的元素放入到临时数组中
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {//将左边较小的元素放入临时数组
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];//将右边较小的元素放入临时数组
            }
        }
        //将左边或者右边剩余的元素放入临时数组
        while (i <= mid) {//左边还有剩余元素
            temp[t++] = arr[i++];
        }
        while (j <= right) {//右边还有剩余元素
            temp[t++] = arr[j++];
        }
        //将temp数组的所有元素copy到arr
        t = 0;//因为每次copy的元素个数不一样
        while (left <= right) {
            arr[left++] = temp[t++];
        }
    }
}

对80000个数据排序

@Test
    public static void time() {
        long start = System.currentTimeMillis();
        int[] arr = new int[80000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 80000);
        }
//        shellSort(arr);
        mergeSort(arr);

        long end = System.currentTimeMillis();
        System.out.println("消耗的时间：" + (end - start));
    }

Java实现排序算法(暂时七个)

对8000000

Java实现排序算法(暂时七个)

基数排序

属于“分配式排序”，又称“桶子法”，通过键值的各个位的值，将要排序的元素分配到某些“桶”中，达到排序的作用

属于稳定排序

是桶排序的扩展

思路分析：

算出所有数组的个位值，放入对应的桶中，再按序存入数组中
再算出所有数组的十位值，放入对应的桶中，再按序存入数组中
再算出所有数组的百位值，放入对应的桶中，再按序存入数组中
…

//对于基数排序而言是通过一个二维数组展现的用空间换时间
    //一共有10个桶用来存放0-9，每个桶又有一个一维数组，用来存放对于的数据
    public static void radixSort(int[] arr) {
        //得到数组中最大的数
         int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        //循环的次数
        int maxLength = (max + "").length();

        //一维表示10个桶，每个桶的最多元素是数组的长度，极端情况下所有元素都在一个桶中
        int[][] bucket = new int[10][arr.length];
        //指具体的哪个桶，在二维数组中指元素放入具体个桶的哪个位置，默认从0开始
        int[] realEle = new int[10];
        for (int k = 0, n = 1; k < maxLength; k++, n *= 10) {
            //将数组中的元素计算完之后放入桶的过程
            for (int i = 0; i < arr.length; i++) {
                //计算每个元素的各十百千位的值
                int value = arr[i] / n % 10;
//            int value1 = arr[i] / 1 % 10;//各位
//            int value2 = arr[i] / 10 % 10;//十位
//            int value3 = arr[i] / 100 % 10;//百位
                bucket[value][realEle[value]++] = arr[i];
            }
            //定义每个桶中元素的数据，即指向每个元素的索引
            int index = 0;
            //从桶里面按序取出元素，放入数组中
            for (int i = 0; i < bucket.length; i++) {//循环每一个桶
                if (realEle[i] != 0) {//如果桶中有元素
                    for (int j = 0; j < realEle[i]; j++) {
                        arr[index++] = bucket[i][j];
                    }
                }
                realEle[i] = 0;
            }
        }
    }

对80000个数据排序

@Test
    public static void time() {
        long start = System.currentTimeMillis();
        int[] arr = new int[80000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 80000);
        }
        radixSort(arr);

        long end = System.currentTimeMillis();
        System.out.println("消耗的时间：" + (end - start));
    }

Java实现排序算法(暂时七个)

对8000000

Java实现排序算法(暂时七个)

Java实现排序算法(暂时七个)

文章目录

冒泡排序

选择排序

插入排序

希尔排序

快速排序

归并排序

基数排序

继续阅读

Codeforces 1417 D. Make Them Equal(思维+构造)

查找算法之二分查找查找算法之二分查找

查找算法学习之二分查找（Python版本）——BinarySearch

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

Command Network(POJ 3164)---定根最小树形图模板题题目描述输入格式输出格式输入样例输出样例分析源程序

开源低带宽语音编解码器

241 Different Ways to Add Parentheses（C代码版）

【趋高机器视觉】机器视觉技术原理解析及解决方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制规程及特点4． CSMA/CD协议5． CSMA/CD的优点6．结束语

极大似然法(ML)与最大期望法(EM)

C++ 第十五周报告1--《冒泡法排序》

笔试面试题目：滑动窗口(二)

数据结构与算法（27）——排序（二）

Dijkstra--简易版（最短路径）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

hdu7108哈希