首页 > 编程语言 >十大排序算法

十大排序算法

时间:2023-04-20 14:46:20浏览次数:42  
标签:arr right 十大 int 算法 length 排序 public left

一、冒泡排序
     
public class BubbleSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝,不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        for (int i = 1; i < arr.length; i++) {
            // 设定一个标记,若为true,则表示此次循环没有进行交换,也就是待排序列已经有序,排序已经完成。
            boolean flag = true;

            for (int j = 0; j < arr.length - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;

                    flag = false;
                }
            }

            if (flag) {
                break;
            }
        }
        return arr;
    }
}



   二、选择排序
 
    public void chooseSort(){
        for(int i=0; i<length-1; i++){
            int minIndex = i;
            for(int j=minIndex+1;j<length;j++){
                if(array[j]<array[minIndex]){
                    minIndex = j;
                }
            }
            int temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp; 
        }
    }
	
	三、插入排序

	
	public class InsertSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝,不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        // 从下标为1的元素开始选择合适的位置插入,因为下标为0的只有一个元素,默认是有序的
        for (int i = 1; i < arr.length; i++) {

            // 记录要插入的数据
            int tmp = arr[i];

            // 从已经排序的序列最右边的开始比较,找到比其小的数
            int j = i;
            while (j > 0 && tmp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }

            // 存在比其小的数,插入
            if (j != i) {
                arr[j] = tmp;
            }

        }
        return arr;
    }
}


四、快速排序

public class QuickSort {
	private void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	
	public void quickSort(int[] arr, int start, int end) {
		if (start >= end)
			return;
		int k = arr[start];
		int i = start, j = end;
		while (i != j) {
			while (i < j && arr[j] >= k)
				--j;
			swap(arr, i, j);
			while (i < j && arr[i] <= k)
				++i;
			swap(arr, i, j);
		}
		quickSort(arr, start, i - 1);
		quickSort(arr, i + 1, end);
	}
	
	public static void main(String[] args) {
		int[] arr = {5, 2, 6, 9, 1, 3, 4, 8, 7, 10};
		new QuickSort().quickSort(arr, 0, arr.length - 1);
		System.out.println(Arrays.toString(arr));
	}
}
	

五、希尔排序
public class ShellSort {
    private int[] array;
    public ShellSort(int[] array) {
        this.array = array;
    }
    public void sort() {
        int temp;
        for (int k = array.length / 2; k > 0; k /= 2) {
            for (int i = k; i < array.length; i++) {
                for (int j = i; j >= k; j -= k) {
                    if (array[j - k] > array[j]) {
                        temp = array[j - k];
                        array[j - k] = array[j];
                        array[j] = temp;
                    }
                }
            }
        }
    }
    public void print() {
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }
}


六、归并排序
public class MergeSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝,不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        if (arr.length < 2) {
            return arr;
        }
        int middle = (int) Math.floor(arr.length / 2);

        int[] left = Arrays.copyOfRange(arr, 0, middle);
        int[] right = Arrays.copyOfRange(arr, middle, arr.length);

        return merge(sort(left), sort(right));
    }

    protected int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0;
        while (left.length > 0 && right.length > 0) {
            if (left[0] <= right[0]) {
                result[i++] = left[0];
                left = Arrays.copyOfRange(left, 1, left.length);
            } else {
                result[i++] = right[0];
                right = Arrays.copyOfRange(right, 1, right.length);
            }
        }

        while (left.length > 0) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }

        while (right.length > 0) {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }

        return result;
    }

}	

七、堆排序
public class HeapSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝,不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int len = arr.length;

        buildMaxHeap(arr, len);

        for (int i = len - 1; i > 0; i--) {
            swap(arr, 0, i);
            len--;
            heapify(arr, 0, len);
        }
        return arr;
    }

    private void buildMaxHeap(int[] arr, int len) {
        for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
            heapify(arr, i, len);
        }
    }

    private void heapify(int[] arr, int i, int len) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;

        if (left < len && arr[left] > arr[largest]) {
            largest = left;
        }

        if (right < len && arr[right] > arr[largest]) {
            largest = right;
        }

        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, largest, len);
        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}


八、计数排序
public static void sort(Integer[] sequenceForArray){
		int maxValue = sequenceForArray[0], minValue = sequenceForArray[0];
		// 1. 获取最大和最小值, 用于创建临时的计数数组
		for (int i = 1; i < sequenceForArray.length; i++) {
			if (sequenceForArray[i] < minValue) {
				minValue = sequenceForArray[i];
			}
			if (sequenceForArray[i] > maxValue) {
				maxValue = sequenceForArray[i];
			}
		}
		// 2. 创建计数数组
		int[] countArray = new int[maxValue-minValue+1];
		// 3. 迭代待排序数组,做计数操作,这个时候表示的是每一个距离最小值的数在待排序序列中有几次
		for (int i = 0; i < sequenceForArray.length; i++) {
			int value = sequenceForArray[i];
			countArray[value- minValue] += 1;
		}
		// 4. 依次迭代,计算每个值应当所在位置
		Integer[] tempArray = new Integer[sequenceForArray.length];
		for (int i = 0; i < tempArray.length; i++) {
			tempArray[i] = sequenceForArray[i];
		}
		// 5. 做叠加操作
		for (int i = 1; i < countArray.length; i++) {
			countArray[i] += countArray[i-1];
		}
		// 整理设置
		for (int i = tempArray.length-1; i >=0 ; i--) {
			int value = tempArray[i];
			sequenceForArray[countArray[value-minValue]-1] = value;
			countArray[value-minValue] -= 1;
		}
	}


九、桶排序
public class BucketSort implements IArraySort {

    private static final InsertSort insertSort = new InsertSort();

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝,不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        return bucketSort(arr, 5);
    }

    private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
        if (arr.length == 0) {
            return arr;
        }

        int minValue = arr[0];
        int maxValue = arr[0];
        for (int value : arr) {
            if (value < minValue) {
                minValue = value;
            } else if (value > maxValue) {
                maxValue = value;
            }
        }

        int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
        int[][] buckets = new int[bucketCount][0];

        // 利用映射函数将数据分配到各个桶中
        for (int i = 0; i < arr.length; i++) {
            int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
            buckets[index] = arrAppend(buckets[index], arr[i]);
        }

        int arrIndex = 0;
        for (int[] bucket : buckets) {
            if (bucket.length <= 0) {
                continue;
            }
            // 对每个桶进行排序,这里使用了插入排序
            bucket = insertSort.sort(bucket);
            for (int value : bucket) {
                arr[arrIndex++] = value;
            }
        }

        return arr;
    }

    /**
     * 自动扩容,并保存数据
     *
     * @param arr
     * @param value
     */
    private int[] arrAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }

}



十、基数排序
/**
 * 基数排序
 * 考虑负数的情况还可以参考: https://code.i-harness.com/zh-CN/q/e98fa9
 */
public class RadixSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝,不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int maxDigit = getMaxDigit(arr);
        return radixSort(arr, maxDigit);
    }

    /**
     * 获取最高位数
     */
    private int getMaxDigit(int[] arr) {
        int maxValue = getMaxValue(arr);
        return getNumLenght(maxValue);
    }

    private int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }

    protected int getNumLenght(long num) {
        if (num == 0) {
            return 1;
        }
        int lenght = 0;
        for (long temp = num; temp != 0; temp /= 10) {
            lenght++;
        }
        return lenght;
    }

    private int[] radixSort(int[] arr, int maxDigit) {
        int mod = 10;
        int dev = 1;

        for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
            // 考虑负数的情况,这里扩展一倍队列数,其中 [0-9]对应负数,[10-19]对应正数 (bucket + 10)
            int[][] counter = new int[mod * 2][0];

            for (int j = 0; j < arr.length; j++) {
                int bucket = ((arr[j] % mod) / dev) + mod;
                counter[bucket] = arrayAppend(counter[bucket], arr[j]);
            }

            int pos = 0;
            for (int[] bucket : counter) {
                for (int value : bucket) {
                    arr[pos++] = value;
                }
            }
        }

        return arr;
    }

    /**
     * 自动扩容,并保存数据
     *
     * @param arr
     * @param value
     */
    private int[] arrayAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }
}



标签:arr,right,十大,int,算法,length,排序,public,left
From: https://www.cnblogs.com/chillymint/p/17336752.html

相关文章

  • MyBatis排序时施用orderby动态参数时需要注意,用$而不是#
    评:mybatis排序时使用orderby动态参数时需要注意,用$而不是#默认情况下,使用#{}格式的语法会导致mybatis创建预处理语句属性并以它为背景设置安全的值(比如?)。这样做很安全,很迅速也是首选做法,有时你只是想直接在sql语句中插入一个不改变的字符串。比如,像orderby,你可以这样来使用......
  • 贪心算法基础及leetcode例题
    理论本质:找到每个阶段的局部最优,然后去推导得到全局最优两个极端:常识&&很难:很多同学通过了贪心的题目,但都不知道自己用了贪心算法,因为贪心有时候就是常识性的推导,所以会认为本应该就这么做!套路:贪心没有套路,说白了就是常识性推导加上举反例做题的时候,只要想清楚局部最优......
  • 【ACM算法竞赛日常训练】DAY16【奇♂妙拆分】【区区区间间间】【小AA的数列】数学 |
    DAY16共3题:奇♂妙拆分(简单数学)区区区间间间(单调栈)小AA的数列(位运算dp)......
  • 微信小程序实现长按拖拽排序
    <viewclass="container"><movable-areaclass="item_box"style="width:{{boxWeight}}rpx;height:{{boxHeight}}rpx"><movable-viewclass="item{{selectId===item.id?'item_show':&#......
  • AES算法 前端JavaScript加密 后端Java解密
    CryptoJShttps://cdnjs.cloudflare.com/ajax/libs/crypto-js/4.1.1/crypto-js.min.js中文文档https://cryptojs.gitbook.io/docs/varAES=function(){ constuuid32="00010203-04050607-08090A0B-0C0D0E0F".toString();constparam=Array.from(uuid32......
  • 选择排序和二分查找
    选择排序 二分查找 ......
  • #yyds干货盘点# LeetCode面试题:搜索旋转排序数组 II
    1.简述:已知存在一个按非降序排列的整数数组nums,数组中的值不必互不相同。在传递给函数之前,nums在预先未知的某个下标k(0<=k<nums.length)上进行了旋转,使数组变为[nums[k],nums[k+1],...,nums[n-1],nums[0],nums[1],...,nums[k-1]](下标从0开始计数)。例如,[0,1,2......
  • 代码随想录算法训练营第一天| 704. 二分查找、27. 移除元素。
    目录一、基础知识-二分法解题思路-数组中删除的思路二、题目一:704.二分查找三、题目二:27.移除元素一、基础知识1.二分法解题思路要求数组必须是有序排列,仅需要根据题目的条件去确定搜索区间。第一个关键点:区间的取值。一般有左闭右闭,左闭右开,左开右闭三种,这个的选择......
  • w6-3 怪物的身高(快速排序)
    #include<iostream>usingnamespacestd;intN,m,A[5000005];//用scanf,printf卡常template<classT>voidQuickSort(Ta[],intfirst,intend){inti=first,j=end;while(i<j){while(i<j&&a[i]<a[j]){//寻找比a[i]大的第一个数......
  • P2661 [NOIP2015 提高组] 信息传递-拓扑排序+DFS深度优先遍历
    题目描述有 n 个同学(编号为 1 到 n )正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象,其中,编号为 i 的同学的信息传递对象是编号为 Ti​ 的同学。游戏开始时,每人都只知道自己的生日。之后每一轮中,所有人会同时将自己当前所知的生日信息告诉各自的信......