Java实现常见的排序算法的示例代码

目录
  • 一、优化后的冒泡排序
  • 二、选择排序
  • 三、插入排序
  • 四、希尔排序
  • 五、快速排序
  • 六、随机化快速排序
  • 七、归并排序
  • 八、可处理负数的基数排序

一、优化后的冒泡排序

package com.yzh.sort;
/*
冒泡排序
 */
@SuppressWarnings({"all"})
public class BubbleSort {

    public static void BubbleSort(int[]a){
        for (int i = 0; i <a.length-1 ; i++) {
            boolean flag=true;
            for (int j = 0; j <a.length-i-1 ; j++) {
                if(a[j]>a[j+1]){
                    int temp=a[j];
                    a[j]=a[j+1];
                    a[j+1]=temp;
                    flag=false;
                }
            }
            if(flag) break;
        }
    }

}

二、选择排序

package com.yzh.sort;
@SuppressWarnings({"all"})
public class SelectSort {

    public static void SelectSort(int[]a) {
        for (int i = 0; i < a.length - 1; i++) {
            int index = i;//标记为待比较的数
            for (int j = i + 1; j < a.length; j++) { //然后从后面遍历与第一个数比较
                if (a[j] < a[index]) {  //如果小,就交换最小值
                    index = j;//保存最小元素的下标
                }
            }
            //找到最小值后,将最小的值放到第一的位置,进行下一遍循环
            int temp = a[index];
            a[index] = a[i];
            a[i] = temp;
        }
    }
}

三、插入排序

package com.yzh.sort;
@SuppressWarnings({"all"})
/*
插入排序
 */
public class InsertSort {

    public static void InsertSort(int[]a){
        for (int i = 0; i < a.length; i++) {
            //定义待插入的数
            int insertValue=a[i];
            //找到待插入数的前一个数的下标
            int insertIndex=i-1;
            while (insertIndex>=0 && insertValue <a[insertIndex]) {//拿a[i]前面的数比较
                a[insertIndex+1]=a[insertIndex];
                insertIndex--;
            }
            a[insertIndex+1]=insertValue;
        }
    }
}

四、希尔排序

package com.yzh.sort;

/*
希尔排序
 */
@SuppressWarnings({"all"})
public class ShellSort {

    public static void ShellSort(int[] a){
        for (int gap=a.length / 2; gap > 0; gap = gap / 2) {
            //将整个数组分为若干个子数组
            for (int i = gap; i < a.length; i++) {
                //遍历各组的元素
                for (int j = i - gap; j>=0; j=j-gap) {
                    //交换元素
                    if (a[j]>a[j+gap]) {
                        int temp=a[j];
                        a[j]=a[j+gap];
                        a[j+gap]=temp;
                    }
                }
            }
        }
    }
}

五、快速排序

package com.yzh.sort;
@SuppressWarnings({"all"})
/*
随机化快速排序
 */
public class QuickSort {

    public static void QuickSort(int[] arr,int low,int high){
        int i,j,temp,t;
        if(low>=high){
            return;
        }
        i=low;
        j=high;
        //temp就是基准位
        temp = arr[low];
        while (i<j) {
            //先看右边,依次往左递减
            while (temp<=arr[j]&&i<j) {
                j--;
            }
            //再看左边,依次往右递增
            while (temp>=arr[i]&&i<j) {
                i++;
            }
            //如果满足条件则交换
            if (i<j) {
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }
        }
        //最后将基准为与i和j相等位置的数字交换
        arr[low] = arr[i];
        arr[i] = temp;
        //递归调用左半数组
        QuickSort(arr, low, j-1);
        //递归调用右半数组
        QuickSort(arr, j+1, high);
    }
}

六、随机化快速排序

package com.yzh.sort;

import java.util.Random;
import java.util.Scanner;

@SuppressWarnings({"all"})
public class RandQuickSort {

    public static void randsort(int[] arr, int left, int right) {
        if(left>=right)
            return;
        Random random = new Random();
        int randIndex = random.nextInt(right-left)+left;  //选取随机主元
        //把随机主元放到数组尾部
        int temp = arr[randIndex];
        arr[randIndex] = arr[right];
        arr[right] = temp;
        //数组中元素与主元比较
        int i = left-1;//注意
        for(int j = left;j<=right;j++) {
            if(arr[j]<arr[right]) {
                i++;
                int temp1 = arr[i];
                arr[i] = arr[j];
                arr[j] = temp1;
            }
        }
        //最后把主元放到适当位置
        int temp2 = arr[i+1];
        arr[i+1] = arr[right];
        arr[right] = temp2;

        randsort(arr,left,i);
        randsort(arr,i+2,right);
    }
}

七、归并排序

package com.yzh.sort;

@SuppressWarnings({"all"})
/*
归并排序
 */
public class MergeSort {

    private static void mergesort(int[] a, int left, int right, int[] temp) {
        //分解
        if (left<right) {
            int mid=((right-left)>>1)+left;
            //向左递归进行分解
            mergesort(a, left, mid, temp);
            //向右递归进行分解
            mergesort(a, mid+1, right, temp);
            //每分解一次便合并一次
            merge(a,left,right,mid,temp);
        }
    }

    private static void merge(int[] a, int left, int right, int mid, int[] temp) {
        int i=left; //初始i,左边有序序列的初始索引
        int j=mid+1;//初始化j,右边有序序列的初始索引(右边有序序列的初始位置即中间位置的后一位置)
        int t=0;//指向temp数组的当前索引,初始为0

        //先把左右两边的数据(已经有序)按规则填充到temp数组
        //直到左右两边的有序序列,有一边处理完成为止
        while (i<=mid && j<=right) {
            //如果左边有序序列的当前元素小于或等于右边的有序序列的当前元素,就将左边的元素填充到temp数组中
            if (a[i]<=a[j]) {
                temp[t++]=a[i++];
            }else {
                //反之,将右边有序序列的当前元素填充到temp数组中
                temp[t++]=a[j++];
            }
        }
        //把剩余数据的一边的元素填充到temp中
        while (i<=mid) {
            //此时说明左边序列还有剩余元素
            //全部填充到temp数组
            temp[t++]=a[i++];
        }
        while (j<=right) {
            //此时说明左边序列还有剩余元素
            //全部填充到temp数组
            temp[t++]=a[j++];
        }
        //将temp数组的元素复制到原数组
        t=0;
        int tempLeft=left;
        while (tempLeft<=right) {
            a[tempLeft++]=temp[t++];
        }
    }
}

八、可处理负数的基数排序

package com.yzh.sort;

public class RadixSort{

    public static void main(String[] args) {
        int[]a={-2,-1,-6,3,5,1,2,88,-1,99,100,21};
        RadixSort(a);
        for (int x : a) {
            System.out.print(x+" ");
        }
        System.out.println();
    }

    public static int[] RadixSort(int[] arr){
        //最大值,用来计算需要找多少次
        int max = Integer.MIN_VALUE;
        //用来判断是否是负数
        int min = Integer.MAX_VALUE;
        //从该数组中找到最大\最小值
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }
        //如果最小值小于0,那么把每个数都减去最小值,这样可以保证最小的数是0
        if (min<0) {
            for (int i = 0; i < arr.length; i++) {
                arr[i] -= min;
            }
            //max也要处理
            max -= min;
        }
        //计算最大值有几位数
        int maxLength = (max+"").length();
        //定义十个桶,每个桶就是一个一维数组
        int[][] bucket = new int[10][arr.length];
        //记录每个桶中实际存放了多少个数据
        int[] bucketElementCount = new int[10];
        //根据最大长度数,决定比较次数
        for (int i = 0 ,n = 1 ; i < maxLength ; i++,n*=10) {
            //每一个数字分别计算余数
            for (int j = 0; j < arr.length ; j++) {
                int value = arr[j]/n % 10;
                //把当前遍历的数放到指定的位置
                bucket[value][bucketElementCount[value]] = arr[j];
                //该位置加一,为下一个值进来做准备
                bucketElementCount[value]++;
            }
            //记录arr的位置
            int index = 0;
            //遍历取出第n次排序的值,等于0的不需要取
            for (int j = 0; j < bucketElementCount.length ; j++) {
                if (bucketElementCount[j]!=0){
                    //遍历取出数据并放到原来的arr中
                    for (int k = 0; k < bucketElementCount[j]; k++) {
                        arr[index] = bucket[j][k];
                        index++;
                    }
                }
                //把数量置为零,因为还有n轮
                bucketElementCount[j] = 0;
            }
        }
        //把排序好的arr重新加上减去的值
        if (min<0){
            for (int i = 0; i < arr.length ; i++) {
                arr[i] += min;
            }
        }
        return arr;
    }

}

以上就是Java实现常见的排序算法的示例代码的详细内容,更多关于Java排序算法的资料请关注我们其它相关文章!

(0)

相关推荐

  • 排序算法图解之Java希尔排序

    目录 1.希尔排序简介 2.希尔排序算法图解 3.希尔排序代码实现 1.希尔排序简介 希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法,其也是一种特殊的插入排序,即将简单的插入排序进行改进后的一个更加高效的版本,也称缩小增量排序. 希尔排序是非稳定排序算法.把记录按下标的一定增量分组,对每组使用直接插入排序算法排序:随着增量逐渐减少,每组包含的关键词越来越多,当增量减至 1 时,整个文件恰被分成一组,算法便终止. 2.希尔排序算法图解 以序列: {8, 9, 1, 7,

  • 排序算法图解之Java插入排序

    目录 1.插入排序简介 2.插入排序思想及图解 3.插入排序代码实现 1.插入排序简介 插入排序,一般也被称为直接插入排序.对于少量元素的排序,它是一个有效的算法.插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而一个新的.记录数增1的有序表.在其实现过程使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对当前元素前面有序表进行待插入位置查找,并进行移动 2.插入排序思想及图解 插入排序的基本思想如下: 把n个待排序的元素看成为一个有序表和一个无

  • 排序算法图解之Java快速排序的分步刨析

    目录 1.快速排序简介 2.思路简介及图解 3.实现代码及运行结果 1.快速排序简介 快速排序是对冒泡排序的一种改进.基本思想为:通过一趟排序将要排序的数据分割为独立的两个部分,其中一部分的所有数据比另外一部分的所有数据要小,然后按照此方法对这两部分分别进行快速排序,整个过程可以递归进行,以此达到整个数据变成有序序列. 2.思路简介及图解 快速排序算法通过多次比较和交换来实现排序,其排序流程如下: (1)首先设定一个分界值,通过该分界值将数组分成左右两部分. (2)将大于或等于分界值的数据集中到

  • 排序算法图解之Java冒泡排序及优化

    目录 1.冒泡排序简介 2.图解算法 3.冒泡排序代码实现 4.冒泡排序算法的优化 1.冒泡排序简介 冒泡排序(Bubble Sorting)即:通过对待排序的序列从前往后,依次比较相邻元素的值,若发现逆序则交换位置,使较大的元素逐渐移动到后部,就像水底的气泡一样逐渐从水面冒出来,这就是冒泡名称的由来 2.图解算法 以将序列{3, 9, -1, 10, -20}从小到大排序为例! 基本思想就是,在每一趟排序实现将最大的数移到序列的最后端!这主要通过比较相邻两个元素实现,当相邻的两个元素逆序的时候

  • 排序算法图解之Java选择排序

    目录 1.选择排序简介 2.图解选择排序算法 3.选择排序代码实现 1.选择排序简介 选择排序(Selection sort)是一种简单直观的排序算法.它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾.以此类推,直到全部待排序的数据元素的个数为零.选择排序是不稳定的排序方法. 2.图解选择排序算法 选择排序的基本思想如下: 第一次:从arr[0]~arr[n-1]中选取最小值,

  • Java数据结构之常见排序算法(上)

    目录 认识排序 常见排序的分类 直接插入排序 希尔排序(缩小增量排序) 选择排序 堆排序 认识排序 在学校中,如果我们要参加运动会,或者军训的时候,会按照身高从矮到高进行站队,比如上课老师手上拿的考勤表,通常是按照学号从低到高进行排序的.再比如编程语言排行榜,也是在排序. 生活中有相当多的排序场景,由此可知,排序还是很重要的, 本章就会介绍常见的一些排序算法. 所谓排序呢,就拿我们上面的举例来说,会按照某个或某些关键字的大小,递增或者递减排列起来的操作,这就是排序,这里面也涉及到排序的稳定性,举

  • Java实现常见的排序算法的示例代码

    目录 一.优化后的冒泡排序 二.选择排序 三.插入排序 四.希尔排序 五.快速排序 六.随机化快速排序 七.归并排序 八.可处理负数的基数排序 一.优化后的冒泡排序 package com.yzh.sort; /* 冒泡排序 */ @SuppressWarnings({"all"}) public class BubbleSort { public static void BubbleSort(int[]a){ for (int i = 0; i <a.length-1 ; i+

  • Java实现8种排序算法的示例代码

    冒泡排序 O(n2) 两个数比较大小,较大的数下沉,较小的数冒起来. public static void bubbleSort(int[] a) { //临时变量 int temp; //i是循环次数,也是冒泡的结果位置下标,5个数组循环5次 for (int i = 0; i < a.length; i++) { //从最后向前面两两对比,j是比较中下标大的值 for (int j = a.length - 1; j > i; j--) { //让小的数字排在前面 if (a[j] <

  • GO语言中常见的排序算法使用示例

    目录 快排 冒泡 选择排序 插入排序 希尔排序 二分法查找 快排 package main import ( "fmt" "math/rand" "time" ) func main() { li:=[]int{1,3,5,2,4,6,9,7} left:=0 right:=len(li)-1 fmt.Println(quick_sort(li,left,right)) } func quick_sort(li []int, left,right

  • Golang实现常见排序算法的示例代码

    目录 前言 五种基础排序算法对比 1.冒泡排序 2.选择排序 3.插入排序 4.快速排序 前言 现在的面试真的是越来越卷了,算法已经成为了面试过程中必不可少的一个环节,你如果想进稍微好一点的公司,「算法是必不可少的一个环节」.那么如何学习算法呢?很多同学的第一反应肯定是去letcode上刷题,首先我并不反对刷题的方式,但是对于一个没有专门学习过算法的同学来说,刷题大部分是没什么思路的,花一个多小时暴力破解一道题意义也不大,事后看看别人比较好的解法大概率也记不住,所以我觉得「专门针对算法进行一些简

  • PHP实现常见排序算法的示例代码

    目录 1.冒泡排序 2.选择排序 3.快速排序 4.插入排序 补充 1.冒泡排序 两两相比,每循环一轮就不用再比较最后一个元素了,因为最后一个元素已经是最大或者最小. function maopaoSort ($list) { $len = count($list); for ($i = 0; $i < $len - 1; $i++) { for ($j = 0; $j < $len - $i - 1; $j++) { if ($list[$j] > $list[$j + 1]) { $

  • Java实现基本排序算法的示例代码

    目录 1. 概述 2. 插入排序 2.1 直接插入排序 2.2 希尔排序(缩小增量排序) 3. 选择排序 3.1 直接选择排序 3.2 堆排序 4. 交换排序 4.1 冒泡排序 4.2 快速排序 5. 归并排序 6. 计数排序(非比较类型的排序) 7. 排序算法总结 1. 概述 排序概念:就是将一串记录按照其中某个或某些关键字的大小,递增或递减的排列起来的操作. 稳定性:通俗的将就是数据元素不发生有间隔的交换,例如: 内部排序:数据元素全部放在内存中的排序 外部排序:数据元素太多不能一次加载到内

  • Java实现拓扑排序算法的示例代码

    目录 拓扑排序原理 1.点睛 2.拓扑排序 3.算法步骤 4.图解 拓扑排序算法实现 1.拓扑图 2.实现代码 3.测试 拓扑排序原理 1.点睛 一个无环的有向图被称为有向无环图.有向无环图是描述一个工程.计划.生产.系统等流程的有效工具.一个大工程可分为若干子工程(活动),活动之间通常有一定的约束,例如先做什么活动,有什么活动完成后才可以开始下一个活动. 用节点表示活动,用弧表示活动之间的优先关系的有向图,被称为 AOV 网. 在 AOV 网中,若从节点 i 到节点 j 存在一条有向路径,则称

  • Go语言实现常用排序算法的示例代码

    目录 冒泡排序 快速排序 选择排序 插入排序 排序算法是在生活中随处可见,也是算法基础,因为其实现代码较短,应用较常见.所以在面试中经常会问到排序算法及其相关的问题,可以说是每个程序员都必须得掌握的了.为了方便大家学习,花了一天的时间用Go语言实现一下常用的算法且整理了一下,如有需要可以参考. 冒泡排序 思路:从前往后对相邻的两个元素依次进行比较,让较大的数往下沉,较小的网上冒,即每当两个相邻的元素比较后发现他们的排序要求相反时,就将它们互换. 时间复杂度:O(N^2) 空间复杂度:O(1) f

  • JAVA用递归实现全排列算法的示例代码

    求一个n阶行列式,一个比较简单的方法就是使用全排列的方法,那么简述以下全排列算法的递归实现. 首先举一个简单的例子说明算法的原理,既然是递归,首先说明一下出口条件.以[1, 2]为例 首先展示一下主要代码(完整代码在后面),然后简述 //对数组array从索引为start到最后的元素进行全排列 public void perm(int[]array,int start) { if(start==array.length) { //出口条件 for(int i=0;i<array.length;i

  • python实现经典排序算法的示例代码

    以下排序算法最终结果都默认为升序排列,实现简单,没有考虑特殊情况,实现仅表达了算法的基本思想. 冒泡排序 内层循环中相邻的元素被依次比较,内层循环第一次结束后会将最大的元素移到序列最右边,第二次结束后会将次大的元素移到最大元素的左边,每次内层循环结束都会将一个元素排好序. def bubble_sort(arr): length = len(arr) for i in range(length): for j in range(length - i - 1): if arr[j] > arr[j

随机推荐