【Java基础】 几种简单的算法排序_java简单的排序算法

学习Java中的排序算法不仅有助于理解数据结构与算法的基本原理，还能提升解决实际问题的能力。排序算法是计算机科学中的重要组成部分，它们在数据处理、数据库管理、机器学习等多个领域都有着广泛的应用。通过学习不同的排序算法，可以加深对算法复杂度、稳定性等概念的理解，并能够根据具体问题选择或设计最合适的排序方法。

下面介绍几种JAVA中简单的算法排序

1.冒泡排序

冒泡排序思路易于理解，是学习排序算法时的一个很好的入门点。这种排序算法的基本思想是每次比较相邻的两个元素，如果前一个元素大于后一个元素，则交换它们的位置。这样一轮比较下来，最大的元素就会被交换到数组的末尾。然后再进行下一轮比较，直到整个数组有序。

public class Main {
    public static void main(String[] args) {
       int [] arr={-3,3,55,12,32,65,78};
       //冒泡排序
        bubbleSort(arr);
        for (int nNum:arr){
            System.out.println(nNum);
        }
    }
    public static void bubbleSort(int []arr){
        //临时变量，用于交换元素
        int temp;
        //标志位，用来判断有没有交换
        boolean flag;
        //外层循环，限制循环次数
        for (int i = 0;i < arr.length - 1;i++){
            flag = false;
            //内层控制元素相邻变换
            for(int j = 0;j< arr.length -1 -i;j++){
                if(arr[j] > arr[j + 1]){
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = true;
                }
            }
            if (!flag){
                break;
            }
        }
    }
}

上述代码中，调用bubbleSort方法，首先定义了一个临时变量temp和一个标志位flag。外层循环控制排序的轮数，每轮比较相邻的元素，如果前一个元素大于后一个元素，则交换它们的位置。一轮比较下来，最大的元素就会被交换到数组的末尾。内层循环控制每轮比较的次数，每次比较相邻的两个元素，如果前一个元素大于后一个元素，则交换它们的位置。如果一轮比较中没有发生任何交换，说明数组已经有序，此时可以提前结束排序。 

2.选择排序

择排序是一种简单直观的排序算法，无论什么数据进去都是 O (n²) 的时间复杂度。 所以用到它的时候，数据规模越小越好。 唯一的好处可能就是不占用额外的内存空间了吧。

选择排序的基本思想是：首先在未排序序列中找到最小（或最大）元素，将其放到排序序列的起始位置，然后再从剩余的未排序元素中继续寻找最小（或最大）元素，并将其放到已排序序列的末尾。这一过程重复进行，直到所有元素均排序完毕。

public class Main {
    public static void main(String[] args) {
       int [] arr={50,89,0,-22,67};
       //选择排序
        selectionSort(arr);
        for (int nNum:arr){
            System.out.println(nNum);
        }
    }
 
    public static void selectionSort(int []arr){
        for (int i = 0;i< arr.length -1;i++)
        {
            int minIndex = i;
            for (int j = i  + 1;j < arr.length;j++){
                if (arr[j] < arr[minIndex]){
                    minIndex = j;
                }
            }
            if (minIndex != i){
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }
    }
}

上述代码中调用selectionSort方法，定义了变量minIndex，用于记录最小元素的下标。外层循环控制排序的轮数，每轮比较相邻的元素，找到最小元素的下标minIndex。

内层循环从i+1开始遍历未排序序列，找到最小元素的下标minIndex。如果minIndex不等于i，说明找到了更小的元素，需要交换位置。

3.快速排序

快速排序是一种高效的排序算法，其基本思想是采用分治法的思想，将待排序的序列分为两个子序列，其中一个子序列的所有元素都比另一个子序列的元素小，然后对这两个子序列分别进行排序，最终得到有序序列。

public class Main {
    public static void main(String[] args) {
       int [] arr={22,11,-12,100,89};
       //快速排序
        quickSort(arr,0,arr.length-1);
        for (int nNum:arr){
            System.out.println(nNum);
        }
    }
 
    public static void quickSort(int [] arr,int low,int high){
        if (low < high){
            int prvot =partition(arr,low,high);
            quickSort(arr,low,prvot - 1);
            quickSort(arr,prvot + 1,high);
        }
    }
 
    public static int partition(int [] arr,int low,int high){
        int prvot = arr[low];
        while (low < high){
            while (low < high && arr[high] >= prvot){
                high--;
            }
            arr[low] = arr[high];
            while (low < high && arr[high] <= prvot){
                low++;
            }
            arr[high] = arr[low];
            arr[low] = prvot;
        }
        return low;
    }
}

上述代码调用两个方法，在partition方法中，首先选取一个基准元素pivot，通常选择第一个元素或者最后一个元素。然后从左到右遍历序列，将小于pivot的元素放到左边，大于pivot的元素放到右边。最后返回基准元素的下标。在quickSort方法中，首先判断low是否小于high，如果是，则调用partition方法获取基准元素的下标prvot。然后对左右两个子序列分别递归调用quickSort方法。

4.插入排序

插入排序是一种简单直观的排序算法，其基本思想是将一个无序序列分为已排序和未排序两部分，每次从未排序部分取出一个元素，将其插入到已排序部分的正确位置上。

public class Main {
    public static void main(String[] args) {
       int [] arr={-6,12,89,22,-8};
       //插入排序
        insertionSort(arr);
        for (int nNum:arr){
            System.out.println(nNum);
        }
    }
 
    public static void insertionSort(int [] arr){
        for (int i = 1; i < arr.length; i++){
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key){
                arr[j +1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}

在这段代码中，insertionSort方法接收一个整型数组作为参数，使用for循环遍历数组中的每个元素。对于每个元素，将其与前面已排序的元素进行比较，如果前面的元素大于当前元素，则将前面的元素后移一位，直到找到合适的位置插入当前元素。最终得到的数组是按照升序排列的。

5.希尔排序

希尔排序是一种改进的插入排序算法，它的基本思想是将待排序的数组按照一定的间隔进行分组，对每组使用插入排序算法进行排序，然后缩小间隔，再对分组进行排序，直到间隔为1为止。

逐渐减小间隔大小的方法有助于提高排序过程的效率，可以减少比较和交换的次数。这是希尔排序算法的一个关键特点。

import java.util.Arrays;
 
public static void Main(String[] args) {
        int[] arr = {5, 2, 8, 3, 1, 6};
        int[] expectedArr = {1, 2, 3, 5, 6, 8};
        shellSort(arr);
        System.out.println("arr = " + Arrays.toString(arr));
        Assertions.assertArrayEquals(expectedArr, arr);
}
    public static void shellSort(int[] arr) {
        int n = arr.length;
        // 初始化间隔（gap）的值，它决定了每次迭代中子数组的大小
        // 从数组长度的一半开始作为初始间隔值，gap就是分割的子数组数量
        for (int gap = n / 2; gap > 0; gap /= 2) {
            // 循环从间隔值开始，遍历数组直到数组的末尾；代表循环所有的子数组
            for (int i = gap; i < n; i++) {
                int temp = arr[i];
                int j = i;
                // 将当前元素 arr[j] 的值替换为前一个元素 arr[j - gap] 的值。
                // 通过这个操作，将较大的元素向后移动，为当前元素腾出位置
                while (j >= gap && arr[j - gap] > temp) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
        }
    }

代码中的shellSort方法接收一个整数数组作为参数，对其进行希尔排序。在main方法中，定义了一个待排序的数组arr和一个预期排序后的数组expectedArr，然后调用shellSort方法对arr进行排序，并使用Assertions.assertArrayEquals方法检查排序后的结果是否与预期相符。

6.计数排序

计数排序是一种非基于比较的排序算法，它适用于当待排序的元素是确定的、可数的，并且元素的范围事先已知的情况下。计数排序的基本思想是对每一个输入元素确定小于它的元素个数，这样就可以直接把输入元素放到它在输出数组中的位置上。

计数排序是一种简单而有效的排序算法，特别适用于整数序列，其性能优于比较排序算法，但在应用上有一定的局限性。

import java.util.Arrays;
 
public static void Main(String[] args) {
        int[] arr = {5, 2, 6, 8, 3, 1, 6, 5, 12};
        int[] expectedArr = {1, 2, 3, 5, 5, 6, 6, 8, 12};
        countingSort(arr);
        System.out.println("arr = " + Arrays.toString(arr));
        Assertions.assertArrayEquals(expectedArr, arr);
}
    public static void countingSort(int[] arr) {
        int n = arr.length;
        // 取出数组中最大值
        int max = getMax(arr);
        int[] count = new int[max + 1];
        // 统计每个元素出现的次数
        for (int i = 0; i < n; i++) {
            count[arr[i]]++;
        }
        // 计算每个元素在有序序列中的位置
        for (int i = 1; i <= max; i++) {
            // 因为count包含了每个数据出现的次数，所以从小到大，
            // 逐个往前加得到就是原数组中每个元素在有序序列中应有的位置
            count[i] += count[i - 1];
        }
        // 输出有序序列
        int[] sortedArr = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            int item = arr[i];//元素
            int itemPos = count[item];// 元素在有序数组中的位置
            sortedArr[itemPos - 1] = item; // 将元素填入有序数组
            count[item]--;
        }
        // 将有序序列复制回原数组
        System.arraycopy(sortedArr, 0, arr, 0, n);
    }
 
    private static int getMax(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        return max;
    }

上述代码中的countingSort方法接受一个整数数组作为参数，并对其进行排序。首先，它找到数组中的最大值，然后创建一个长度为最大值加1的计数数组。接下来，它遍历输入数组，统计每个元素出现的次数，并将结果存储在计数数组中。然后，它计算每个元素在有序序列中的位置，并将结果存储回计数数组。最后，它使用计数数组中的位置信息将元素填入一个新的有序数组，并将有序数组复制回原数组。

getMax方法用于获取数组中的最大值。它遍历数组，找到最大的元素并返回。