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

十大排序算法代码集锦(java)

程序员文章站 2022-06-03 23:37:53
...

SortAlgorithm.java

import java.util.*;

class SortAlgorithm {
//冒泡排序
    public int[] BubbleSort(int[] nums){
        int n=nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n-i-1; j++) {
                if(nums[j]>nums[j+1]){
                    int temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                }
            }
        }
        return nums;
}

//选择排序
    public int[] SelectSort(int[] nums){
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
             int min = i;
             for (int j = i + 1; j < n; j++) {
                if(nums[min] > nums[j]) min = j;
             }
             //交换
             int temp = nums[i];
             nums[i] = nums[min];
             nums[min] = temp;
        }
        return nums;
    }

//插入排序
    public int[] InsertSort(int[] nums){
        for(int i=1; i<nums.length; i++){
			for(int j=i; j>0; j--){
				if(nums[j]<nums[j-1]){
					int temp = nums[j-1];
					nums[j-1] = nums[j];
					nums[j] = temp;
				}
			}
		}
        return nums;
    }
//希尔排序
/* 希尔排序可以说是插入排序的一种变种。无论是插入排序还是冒泡排序,如果数组的最大值刚好是在第一位,
要将它挪到正确的位置就需要 n - 1 次移动。也就是说,原数组的一个元素如果距离它正确的位置很远的话,
则需要与相邻元素交换很多次才能到达正确的位置,这样是相对比较花时间了。
希尔排序就是为了加快速度简单地改进了插入排序,交换不相邻的元素以对数组的局部进行排序。
希尔排序的思想是采用插入排序的方法,先让数组中任意间隔为 h 的元素有序,刚开始 h 的大小可以是 h = n / 2,
接着让 h = n / 4,让 h 一直缩小,当 h = 1 时,也就是此时数组中任意间隔为1的元素有序,此时的数组就是有序的了。 */
    public int[] shellSort(int nums[]) {
        int n = nums.length;
        // 对每组间隔为 h的分组进行排序,刚开始 h = n / 2;
        for (int h = n / 2; h > 0; h /= 2) {
            //对各个局部分组进行插入排序
            for (int i = h; i < n; i++) {
                // nums[i] 插入到所在分组的正确位置上
                int k;
                int temp = nums[i];
                for (k = i - h; k > 0 && temp < nums[k]; k -= h) {
                    nums[k + h] = nums[k];
                }
                nums[k + h] = temp;
            }
        }
        return nums;
    }

//归并排序
public int[] mergeSort(int nums[],int left,int right) {
    if (left < right) {
        int mid=(left+right)/2;
        //左半部分排序
        mergeSort(nums, left, mid);
        //右半部分排序
        mergeSort(nums, mid+1, right);
        //进行合并
        merge(nums,left,mid,right);
    }
    return nums;
}
public void merge(int nums[],int left,int mid,int right){
    //辅助数组
    int[] a=new int[right-left+1];
    int i=left;
    int j=mid+1;
    int k=0;
    while(i<=mid&&j<=right){
        if(nums[i]<nums[j]){
            a[k++]=nums[i++];
        }else{
            a[k++]=nums[j++];
        }
    }
    //如果第一个序列未检测完,直接将后面所有元素加到合并的序列中
    while(i<=mid){
        a[k++]=nums[i++];
    }
    while(j<=right){
        a[k++]=nums[j++];
    }
    //复制回原数组
    for(i=0;i<k;i++){
        nums[left++]=a[i];
    }
}

//快速排序
    public int[] quickSort(int nums[],int left,int right) {
        if(left<right){
            int mid=partition(nums,left,right);
            nums=quickSort(nums, left, mid-1);
            nums=quickSort(nums, mid+1, right);
        }
        return nums;
    }
    private int partition(int[] nums,int left,int right){
        int pivot=nums[left];
        int i=left+1;
        int j=right;
        while(true){
            //向右找到第一个小于pivot的位置
            while(i<=j&&nums[i]<=pivot) i++;
            //向左找到第一个大于pivot的位置
            while(i<=j&&nums[j]>=pivot) j--;
            if(i>=j){
                break;
            }
            int temp=nums[i];
            nums[i]=nums[j];
            nums[j]=temp;
        }
        nums[left]=nums[j];
        nums[j]=pivot;
        return j;
    }

//堆排序
    public int[] headSort(int[] nums){
        int n= nums.length;
        //构建大顶堆
        for(int i=(n-2)/2;i>=0;i--){
            downAdjust(nums,i,n-1);
        }
        //进行堆排序
        for(int i=n-1;i>=1;i--){
            //把堆顶元素与最后一个元素交换
            int temp =nums[i];
            nums[i]=nums[0];
            nums[0]=temp;
            //把打乱的堆进行调整,恢复堆的特性
            downAdjust(nums, 0, i-1);
        }
        return nums;
    }
    public void downAdjust(int[] nums, int parent,int n){
        //临时保存要下沉的元素
        int temp =nums[parent];
        //定位左孩子节点的位置
        int child=2*parent+1;
        while(child<=n){
            //如果右孩子节点比左孩子大,则定位到右孩子
            if(child+1<=n&&nums[child]<nums[child+1]){
                child++;
            }
            //如果孩子节点小于或等于父节点,则下沉结束
            if(nums[child]<=temp) break;
            //父节点进行下沉
            nums[parent]=nums[child];
            parent=child;
            child=2*parent+1;
        }
        nums[parent]=temp;
    }

    //计数排序
    public int[] countSort(int[] nums) {
        if(nums == null || nums.length < 2) return nums;

        int n = nums.length;
        int min = nums[0];
        int max = nums[0];
        // 寻找数组的最大值与最小值
        for (int i = 1; i < n; i++) {
            if(max < nums[i])
                max = nums[i];
            if(min > nums[i])
                min = nums[i];
        }
        int d = max - min + 1;
        // 创建大小为max的临时数组
        int[] temp = new int[d];
        // 统计元素i出现的次数
        for (int i = 0; i < n; i++) {
            temp[nums[i] - min]++;
        }
        int k = 0;
        // 把临时数组统计好的数据汇总到原数组
        for (int i = 0; i < d; i++) {
            for (int j = temp[i]; j > 0; j--) {
                nums[k++] = i + min;
            }
        }
        return nums;
    }

    //桶排序
    public int[] BucketSort(int[] nums) {
        //1. 构造桶
        //1.1 确定桶的个数n
        int n = nums.length;
        //1.2 声明并初始化一个List,存放链表;
        List<ArrayList<Integer>> Blist = new ArrayList<>(n);
        //2.将数组中的元素放到桶中
        //2.1 确定元素的最值
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int a : nums){
            max = Math.max(max, a);
            min = Math.min(min, a);
        }
        //和优化版本的计数排序一样,弄一个大小为 min 的偏移值
        int d = max - min;
         //创建 d / 5 + 1 个桶,第 i 桶存放  5*i ~ 5*i+5-1范围的数
        int bucketNum = d / 5 + 1;
        for(int i = 0; i < n; i++)
            Blist.add(new ArrayList<Integer>(bucketNum));
        //确定每个元素放入桶的编号并放进去
        for(int i : nums){
            //确定桶的编号
            //加1是为了保证index< A.length,防止程序抛出IndexOutofBoundsEx;
            int index = (int)((i-min) / (max-min+1.0) * n); 
            //放入对应的桶中
            Blist.get(index).add(i);
        }
        //3.桶内排序
        for(int i = 0; i < Blist.size(); i++){
            Collections.sort(Blist.get(i));
        }
        //4.合并数据
        int j = 0;
        for(ArrayList<Integer> arr : Blist){
            for(int i : arr){
                nums[j++] = i;
            }
        }
        return nums;
    }

    //基数排序
    public  int[] radioSort(int[] nums) {
        // 基数排序简化
		// 1.得到最大的位数
		int max = nums[0];// 假设最大数是第一个
		for (int i = 1; i < nums.length; i++) {
			if (nums[i] > max) {
				max = nums[i];
			}
		}
		// 得到最大数是几位数
		int maxLength = (max + "").length();

		// 定义一个二维数组,表示10个桶,每个桶就是一个一维数组
		// 说明
		// 1.二维数组包含10个一维数组
		// 2.为了防止数据溢出,则每个一维数组的大小定义为arr.lenght
		// 3.很明确,基数排序是用空间换时间的经典算法
		int[][] bucket = new int[10][nums.length];

		// 为了记录每个桶中实际存放了多少个数据,我们定义一个以为数组来记录各个桶中的每次放入的数据个数
		// 比如:bucketElementCounts[0]记录的就是bbucket[0]桶的放入数据个数
		int[] bucketElementCounts = new int[10];

		// 使用循环将代码处理
		for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
			// 排序(针对每一个元素的对应位进行排序处理),第一次 个位,第二次 十位,第三次 百位。。。。。。
			for (int j = 0; j < nums.length; j++) {
				// 取出每个元素对应位的数据
				int digitOfElement = nums[j] / n % 10;
				// 放入到对应的桶中
				bucket[digitOfElement][bucketElementCounts[digitOfElement]] = nums[j];
				bucketElementCounts[digitOfElement]++;
			}
			// 按照这个桶的顺序(一维数组的下标依次取出数据,放入原来数组)
			int index = 0;
			// 遍历每一个桶,并将桶中的数据放入到原数组
			for (int k = 0; k < bucketElementCounts.length; k++) {
				// 如果桶中有数据我们才放入到原数组
				if (bucketElementCounts[k] != 0) {
					// 循环该桶,即第k个一维数组
					for (int l = 0; l < bucketElementCounts[k]; l++) {
						// 取出元素放到arr
						nums[index++] = bucket[k][l];
					}
				}
				// 每一轮处理后需要将每一个bucketElementCounts置0
				bucketElementCounts[k] = 0;
			}
        
        }
        return nums;
    }

    public static void main(String[] args) {
        SortAlgorithm sa=new SortAlgorithm();
        int[] nums={2,3,6,9,4,5};
        System.out.println(Arrays.toString(sa.BubbleSort(nums)));
        System.out.println(Arrays.toString(sa.SelectSort(nums)));
        System.out.println(Arrays.toString(sa.InsertSort(nums)));
        System.out.println(Arrays.toString(sa.shellSort(nums)));
        System.out.println(Arrays.toString(sa.mergeSort(nums,0,nums.length-1)));
        System.out.println(Arrays.toString(sa.quickSort(nums,0,nums.length-1)));
        System.out.println(Arrays.toString(sa.headSort(nums)));  
        System.out.println(Arrays.toString(sa.countSort(nums))); 
        System.out.println(Arrays.toString(sa.BubbleSort(nums)));  
        System.out.println(Arrays.toString(sa.radioSort(nums)));     
    }
}

总结

用一张图汇总了10大排序算法的性质

十大排序算法代码集锦(java)