8大Java排序方法(由简入繁),有代码详解和原理指导

本文涉及的产品
实时计算 Flink 版,5000CU*H 3个月
智能开放搜索 OpenSearch行业算法版,1GB 20LCU 1个月
实时数仓Hologres,5000CU*H 100GB 3个月
简介: 8大Java排序方法(由简入繁),有代码详解和原理指导

1. 插入排序

升序:

public static void main(String [] args) {
   
    int j;
    int[] array = {
   14,98,36,80,28,99,55,32};
    for(int i = 1 ; i < array.length ; i++) {
   
        int temp1 = array[i];
        for(j = i-1 ; j >= 0 && array[j] < temp1 ; j--) {
   
            array[j+1] = array[j];
        }
        array[j+1] = temp1;
    }
}
AI 代码解读

降序:

public static void main(String [] args) {
   
    int j;
    int[] array = {
   14,98,36,80,28,99,55,32};
    for(int i = 1 ; i < array.length ; i++) {
   
        int temp1 = array[i];
        for(j = i-1 ; j >= 0 && array[j] > temp1 ; j--) {
   
            array[j+1] = array[j];
        }
        array[j+1] = temp1;
    }
}
AI 代码解读

原理:

  • 初始化:从数组的第二个元素开始迭代,因为单个元素默认是已排序的。
  • 选择未排序的元素:array[i]是需要被插入到已排序子数组中的元素。
  • 寻找插入位置:内部循环用于对已排序的部分进行扫描,检查当前 array[j] 是否小于 temp1。如果是,这意味着 temp1 应该被插入到 array[j] 的后面。
  • 插入元素:当内部循环结束时,我们找到了 temp1 的正确位置,这个位置是 j + 1

2. 选择排序

升序:

public static void main(String[] args) throws ParseException {
   
    int[] array = {
   14, 98, 36, 80, 28, 99, 55, 32};
    for (int i = 0; i < array.length - 1; i++) {
   
        final int MAX_POS = array.length - 1 - i;
        int MAX_VAL_POS = 0;
        for (int j = 1; j <= MAX_POS; j++) {
   
            if (array[j] > array[MAX_VAL_POS]) {
   
                MAX_VAL_POS = j;
            }
        }
        if (MAX_VAL_POS != MAX_POS) {
   
            int temp = array[MAX_VAL_POS];
            array[MAX_VAL_POS] = array[MAX_POS];
            array[MAX_POS] = temp;
        }
    }
}
AI 代码解读

降序:

public static void main(String [] args) {
   
    int[] array = {
   14, 98, 36, 80, 28, 99, 55, 32};
    for (int i = 0; i < array.length - 1; i++) {
   
        final int MIN_POS = array.length - 1 - i;
        int MIN_VAL_POS = 0;
        for (int j = 1; j <= MIN_POS; j++) {
   
            if (array[j] < array[MIN_VAL_POS]) {
   
                MIN_VAL_POS = j;
            }
        }
        if (MIN_VAL_POS != MIN_POS) {
   
            int temp = array[MIN_VAL_POS];
            array[MIN_VAL_POS] = array[MIN_POS];
            array[MIN_POS] = temp;
        }
    }
}
AI 代码解读

原理:

  • 外部循环从数组的第一个元素开始,一直迭代到倒数第二个元素。
  • 初始化最小位置:在每一次外部迭代开始时,都定义一个常量 MIN_POS,表示当前未排序部分的最后一个位置。
  • 查找最小值位置:内部的for循环用于在未排序部分查找最小元素。
  • 一旦内部循环完成,我们检查 MIN_VAL_POS 是否等于 MIN_POS。如果它们不相等,说明找到了一个更小的元素,需要将这个元素与未排序部分的第一个元素进行交换,以确保最小元素放在已排序部分的末尾。

3. 冒泡排序

升序:

public static void main(String[] args) {
   
    int[] array = {
   14, 98, 36, 80, 28, 99, 55, 32};
    int n = array.length;
    for (int i = 0; i < n - 1; i++) {
   
        for (int j = 0; j < n - 1 - i; j++) {
   
            if (array[j] > array[j + 1]) {
   
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}
AI 代码解读

降序:

public static void main(String[] args)
{
    int[] array = {14,98,36,80,28,99,55,32};
    for(int i = 0 ; i < array.length-1 ; i++)
    {
        for(int j = 0 ; j < array.length-1-i  ; j++)
        {
            if(array[j] < array[j+1])
            {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}
AI 代码解读

原理:

  • 外部循环:控制了遍历的轮数
  • 内部循环:内部的for循环用于比较相邻的元素并且交换他们的位置,每一轮都会将未排序部分的最大元素移动到正确的位置。

4.桶排排序(此处介绍一种特殊的桶排排序——基数排序)

升序:

int max = array[0];
for (int i = 1; i < array.length; i++) {
   
    if(array[i] > max)
        max = array[i];
}
int size = 1;
while((max/=10)>=1)
    size++;
//记录某数位值的数量(一维)
int [] ixs = new int [10];
//统计对应数位值的元素(二维)
int [][] vals = new int [10][array.length];
//从低位到高位:
for (int i = 0; i < size; i++) {
   
    //1.按数位值提取 计算数位值数量并存放在一维数组中 并将元素存放在二维数组中
    for (int k = 0; k < array.length; k++) {
   
        int t = (array[k]/(int)Math.pow(10,i))%10;
        vals[t][ixs[t]++] = array[k];
    }
    //2.将二维数组中的元素按数位值放回array 两层循环(放回的循环方向决定了升降序)
    for (int m = 0 , n = 0; m < ixs.length; m++) {
   
        for (int j = 0; j < ixs[m]; j++) {
   
            array[n++] = vals[m][j];
        }
    }
    //3.ixs数组的清零
    for (int j = 0; j < ixs.length; j++) {
   
        ixs[j] = 0;
    }
}
AI 代码解读

降序:

int max = array[0];
for (int i = 1; i < array.length; i++) {
   
    if(array[i] > max)
        max = array[i];
}
int size = 1;
while((max/=10)>=1)
    size++;
//记录某数位值的数量(一维)
int [] ixs = new int [10];
//统计对应数位值的元素(二维)
int [][] vals = new int [10][array.length];
//从低位到高位:
for (int i = 0; i < size; i++) {
   
    //1.按数位值提取 计算数位值数量并存放在一维数组中 并将元素存放在二维数组中
    for (int k = 0; k < array.length; k++) {
   
        int t = (array[k]/(int)Math.pow(10,i))%10;
        vals[t][ixs[t]++] = array[k];
    }
    //2.将二维数组中的元素按数位值放回array 两层循环(放回的循环方向决定了升降序)
    for (int m = 0 , n = array.length; m < ixs.length; m++) {
   
        for (int j = 0; j < ixs[m]; j++) {
   
            array[--n] = vals[m][j];
        }
    }
    //3.ixs数组的清零
    for (int j = 0; j < ixs.length; j++) {
   
        ixs[j] = 0;
    }
}
AI 代码解读

原理:

1. 分布元素到桶中:根据元素的特定属性将它们分配到不同的桶中。
2. 单独排序每个桶
3. 合并桶:将每个桶中已排序的元素合并成一个单一的、有序的数组。
AI 代码解读

基数排序原理:
假设随机生成的数组 array 如下所示:
int[] array = {170, 45, 75, 90, 802, 24, 2, 66};

1.找出最大值,确定最大值的数位
最大值为`802`,因此,最大位数为`3`(802是一个三位数)
    int size=1;
    while((max/=10)>=1) size++;
2.从低位到高位进行排序(分桶并对桶单独排序)
第一轮排序 - 个位数
    分配:根据个位数,将每个元素分配到相应的桶中。例如,170(个位是 0)会去到桶 0,45(个位是 5)会去到桶 5。

    分配后的桶内容可能如下:

    桶 0:170, 90
    桶 1:无
    桶 2:802, 2
    桶 3:无
    桶 4:24
    桶 5:45, 75
    桶 6:66
    桶 7:无
    桶 8:无
    桶 9:无
    收集:按照桶的顺序收集元素,得到新的数组。新数组是:170, 90, 802, 2, 24, 45, 75, 66。

第二轮排序 - 十位数
    分配:现在基于十位数进行分配。例如,802(十位是 0)会去到桶 0,75(十位是 7)会去到桶 7。

    分配后的桶内容可能如下:

    桶 0:802, 2
    桶 1:无
    桶 2:24
    桶 3:无
    桶 4:45
    桶 5:无
    桶 6:66
    桶 7:75
    桶 8:无
    桶 9:90, 170
    收集:收集元素,新数组是:802, 2, 24, 45, 66, 75, 90, 170。

第三轮排序 - 百位数
    分配:最后,根据百位数分配。例如,802(百位是 8)会去到桶 8,24(没有百位,视为 0)会去到桶 0。

    分配后的桶内容可能如下:

    桶 0:2, 24, 45, 66, 75, 90, 170
    桶 1:无
    桶 2:无
    桶 3:无
    桶 4:无
    桶 5:无
    桶 6:无
    桶 7:无
    桶 8:802
    桶 9:无
    收集:最终收集元素,得到排序后的数组:2, 24, 45, 66, 75, 90, 170, 802。
AI 代码解读

5.计数排序

升序:

//找出最大值和最小值 并求出最大数组长度构建数组
for (int j = 1; j < num; j++) {
   
    if (array[j] > max)
        max = array[j];
    if (array[j] < min)
        min = array[j];
}
//找出数组元素与数组下标的关系并对应
int[] tempArr = new int[max - min + 1];
for (int v : array) {
   
    tempArr[v - min]++;
}
//通过下标 得出某数组元素的重复个数(循环1)并按序输出(循环2)
System.out.print("[");
for (int m = 0; m < tempArr.length; m++)//控制升降序的地方
{
   
    for (int n = 0; n < tempArr[m]; n++) {
   
        System.out.print(min + m);
        if(m== tempArr.length-1&&n==tempArr[tempArr.length-1]-1)
            System.out.println("]");
        else
            System.out.print(",");
    }
}
AI 代码解读

降序:

//找出最大值和最小值 并求出最大数组长度构建数组
for (int j = 1; j < num; j++) {
   
    if (array[j] > max)
        max = array[j];
    if (array[j] < min)
        min = array[j];
}
//找出数组元素与数组下标的关系并对应
int[] tempArr = new int[max - min + 1];
for (int v : array) {
   
    tempArr[v - min]++;
}
//通过下标 得出某数组元素的重复个数(循环1)并按序输出(循环2)
System.out.print("[");
for (int m = tempArr.length-1;m>=0;m--)//控制升降序的地方
{
   
    for (int n = 0; n < tempArr[m]; n++) {
   
        System.out.print(min + m);
        if(m==0&&n==tempArr[tempArr.length-1]-1)
            System.out.println("]");
        else
            System.out.print(",");
    }
}
AI 代码解读

原理:

  • 找到最大值和最小值
  • 创建计数数组tempArr[max-min+1],确保可以覆盖所有可能的值,每个索引对应输入数组中所有可能出现的整数值。
  • 计数:遍历原始数组,对每个元素出现的次数进行计数。
  • 输出排序结果:遍历tempArr数组,对于数组中的每个元素tempArr[m],输出min+m这个值tempArr[m]次。

6.希尔排序

升序:

int size = num;
while((size/=2)>=2)
{
   
    for (int j = 0; j < array.length-size; j++)
    {
   
        if(array[j] > array[j+size])//控制升降序的地方 1
        {
   
            int temp2 = array[j];
            array[j] = array[j + size];
            array[j + size] = temp2;
        }
    }
}
//再进行排序
for(int m,k = 1; k < array.length ;k++)
{
   
    int temp3 = array[k];
    for(m = k-1 ; m>=0&&array[m]>temp3 ; m--)//控制升降序的地方 2
    {
   
        array[m+1] = array[m];
    }
    array[m+1] = temp3;
}
AI 代码解读

降序:

int size = num;
while((size/=2)>=2)
{
   
    for (int j = 0; j < array.length-size; j++)
    {
   
        if(array[j] < array[j+size])//控制升降序的地方 1
        {
   
            int temp2 = array[j];
            array[j] = array[j + size];
            array[j + size] = temp2;
        }
    }
}
//再进行排序
for(int m,k = 1; k < array.length ;k++)
{
   
    int temp3 = array[k];
    for(m = k-1 ; m>=0&&array[m]<temp3 ; m--)//控制升降序的地方 2
    {
   
        array[m+1] = array[m];
    }
    array[m+1] = temp3;
}
AI 代码解读

原理:

  • 核心思想是使数组中任意间隔为h的元素都是有序的
  • 希尔排序的间隔序列,代码通过一个while循环来控制排序的间隔size,间隔size是通过不断将数组长度除以2来获取的,直至这个间隔变成2以下。
     对于`size`的每一个值,代码通过一个 for 循环遍历数组。如果找到两个间隔为 size 的元素是逆序|升序的,则交换这两个元素。
     随着`size`的减小,数组会越来越趋近于完全排序。
    
    AI 代码解读
  • 最终再进行一次插入排序。

7.快速排序

升序:

public class QuickSort {
   
    public Random rand;

    public void swap(int[] nums, int l, int r) {
   
        int temp = nums[l];
        nums[l] = nums[r];
        nums[r] = temp;
    }

    public void pivot(int[] nums, int l, int r) {
   
        /**
         * 归并终止条件
         */
        if (l >= r) {
   
            return;
        }
        /**
         * 下标范围[l,r]
         */
        int mid = rand.nextInt(r - l + 1) + l;
        swap(nums, l, mid);

        int
                x = nums[l],
                i = l + 1,
                j = r;
        /**
         * 左边找到比x大的数字,i不动;右边找到比x小的数字,j不动,作值交换
         */
        while (i < j) {
   
            while (i < j && nums[i] < x) {
   
                i++;
            }
            while (i < j && nums[j] > x) {
   
                j--;
            }
            swap(nums, i, j);
        }

        /**
         * i,j重合了,x应该与哪个下标的值作交换?
         */
        if (nums[i] <= x) {
   
            swap(nums, l, i);
        } else {
   
            swap(nums, l, i - 1);
            i--;
        }
        /**
         * 对pivot(下标为i)的两侧进行递归排序
         */
        pivot(nums, l, i - 1);
        pivot(nums, i + 1, r);
    }

    public int[] quickSortArr(int[] nums) {
   
        /**
         * 在对排序进行包装的同时实现Random类
         */
        rand = new Random(System.currentTimeMillis());
        pivot(nums, 0, nums.length - 1);
        return nums;
    }
}
AI 代码解读

降序:

public class QuickSort {
   
    public Random rand;

    public void swap(int[] nums, int l, int r) {
   
        int temp = nums[l];
        nums[l] = nums[r];
        nums[r] = temp;
    }

    public void pivot(int[] nums, int l, int r) {
   
        if (l >= r) {
   
            return;
        }

        int mid = rand.nextInt(r - l + 1) + l;
        swap(nums, l, mid);

        int x = nums[l],
            i = l + 1,
            j = r;

        while (i < j) {
   
            // 修改为找到比x小的数字停止,以便进行降序排列
            while (i < j && nums[i] > x) {
   
                i++;
            }
            // 修改为找到比x大的数字停止,以便进行降序排列
            while (i < j && nums[j] < x) {
   
                j--;
            }
            swap(nums, i, j);
        }

        if (nums[i] >= x) {
    // 修改条件以确保降序排列
            swap(nums, l, i);
        } else {
   
            swap(nums, l, i - 1);
            i--;
        }

        pivot(nums, l, i - 1);
        pivot(nums, i + 1, r);
    }

    public int[] quickSortArr(int[] nums) {
   
        rand = new Random(System.currentTimeMillis());
        pivot(nums, 0, nums.length - 1);
        return nums;
    }
}
AI 代码解读

原理:

  • 选择基准:可以随机选取一个元素作为基准
  • 分区:重新排列数组,使所有小于基准的元素都移动到基准的左边,而所有大于基准的元素都移动到基准的右边。
  • 递归排序子数组:递归地将上述过程应用于基准左侧和右侧地子数组

    8.归并排序

    升序:

    public static void mergeSort(int[] nums){
         
      mergeSort(nums,0,nums.length-1);
    }
    public static void mergeSort(int[] nums,int start,int end){
         
      if(start < end){
         
          int mid = start + (end-start)/2;
          mergeSort(nums,start,mid);
          mergeSort(nums,mid+1,end);
          merge(nums,start,mid,end);
      }
    }
    private static void merge(int[] nums,int start,int mid,int end){
         
      int
              p1 = start,
              p2 = mid+1,
              count = 0;
    
      int[] temp = new int[end-start+1];
      while(p1<=mid && p2<=end){
         
          if(nums[p1] < nums[p2]){
         
              temp[count] = nums[p1];
              p1++;
          }else{
         
              temp[count] = nums[p2];
              p2++;
          }
          count++;
      }
      while(p1<=mid){
         
          temp[count++] = nums[p1++];
      }
      while(p2<=end){
         
          temp[count++] = nums[p2++];
      }
      for (int i = 0; i < temp.length; i++) {
         
          nums[i+start] = temp[i];
      }
    }
    
    AI 代码解读

    降序:
    ```java
    public static void mergeSort(int[] nums){
    mergeSort(nums,0,nums.length-1);
    }
    public static void mergeSort(int[] nums, int start, int end) {
    if (start < end) {

      int mid = start + (end - start) / 2;
      mergeSort(nums, start, mid);
      mergeSort(nums, mid + 1, end);
      merge(nums, start, mid, end);
    
    AI 代码解读

    }
    }

private static void merge(int[] nums, int start, int mid, int end) {
int p1 = start, p2 = mid + 1, count = 0;
int[] temp = new int[end - start + 1];

while (p1 <= mid && p2 <= end) {
    if (nums[p1] > nums[p2]) { // 修改比较逻辑,以降序排列
        temp[count] = nums[p1];
        p1++;
    } else {
        temp[count] = nums[p2];
        p2++;
    }
    count++;
}

while (p1 <= mid) {
    temp[count++] = nums[p1++];
}

while (p2 <= end) {
    temp[count++] = nums[p2++];
}

for (int i = 0; i < temp.length; i++) {
    nums[i + start] = temp[i];
}
AI 代码解读

}
```
原理:

  • 将数组从中间分割成两个子数组,继续递归地将这些子数组分割,直至每个子数组只包含一个元素。
  • 逐步合并这些子数组。

排序算法的时间复杂度分析

  1. 插入排序(Insertion Sort)

    • 最好情况时间复杂度:O(n)
    • 平均情况时间复杂度:O(n²)
    • 最坏情况时间复杂度:O(n²)
    • 空间复杂度:O(1)
  2. 选择排序(Selection Sort)

    • 最好情况时间复杂度:O(n²)
    • 平均情况时间复杂度:O(n²)
    • 最坏情况时间复杂度:O(n²)
    • 空间复杂度:O(1)
  3. 冒泡排序(Bubble Sort)

    • 最好情况时间复杂度:O(n)
    • 平均情况时间复杂度:O(n²)
    • 最坏情况时间复杂度:O(n²)
    • 空间复杂度:O(1)
  4. 桶排序(Bucket Sort)

    • 最好情况时间复杂度:O(n+k)
    • 平均情况时间复杂度:O(n+k)
    • 最坏情况时间复杂度:O(n²)
    • 空间复杂度:O(n+k)
  5. 计数排序(Counting Sort)

    • 最好情况时间复杂度:O(n+k)
    • 平均情况时间复杂度:O(n+k)
    • 最坏情况时间复杂度:O(n+k)
    • 空间复杂度:O(k)
  6. 希尔排序(Shell Sort)

    • 最好情况时间复杂度:取决于间隔序列
    • 平均情况时间复杂度:取决于间隔序列,一般认为是O(nlogn)
    • 最坏情况时间复杂度:取决于间隔序列
    • 空间复杂度:O(1)
  7. 快速排序(Quick Sort)

    • 最好情况时间复杂度:O(nlogn)
    • 平均情况时间复杂度:O(nlogn)
    • 最坏情况时间复杂度:O(n²)
    • 空间复杂度:取决于实现方式,一般为O(logn)(递归实现时)
  8. 归并排序(Merge Sort)

    • 最好情况时间复杂度:O(nlogn)
    • 平均情况时间复杂度:O(nlogn)
    • 最坏情况时间复杂度:O(nlogn)
    • 空间复杂度:O(n)
目录
打赏
0
0
0
0
47
分享
相关文章
快手小红书抖音留痕工具,自动留痕插件工具,java代码开源
这个框架包含三个核心模块:主操作类处理点赞评论、配置管理类和代理管理类。使用时需要配合
tiktok群控脚本,养号关注私信点赞脚本插件,java代码分享
这个代码模拟了一个社交机器人的基本行为模式,包括登录、关注、点赞、私信等操作。请注意
|
9天前
|
Java ArrayList中的常见删除操作及方法详解。
通过这些方法,Java `ArrayList` 提供了灵活而强大的操作来处理元素的移除,这些方法能够满足不同场景下的需求。
69 30
Go与Java泛型原理简介
本文介绍了Go与Java泛型的实现原理。Go通过单态化为不同类型生成函数副本,提升运行效率;而Java则采用类型擦除,将泛型转为Object类型处理,保持兼容性但牺牲部分类型安全。两种机制各有优劣,适用于不同场景。
55 24
|
11天前
|
Java语言按文件创建日期排序及获取最新文件的技术
这段代码实现了文件创建时间的读取、文件列表的获取与排序以及获取最新文件的需求。它具备良好的效率和可读性,对于绝大多数处理文件属性相关的需求来说足够健壮。在实际应用中,根据具体情况,可能还需要进一步处理如访问权限不足、文件系统不支持某些属性等边界情况。
57 14
|
2天前
|
Java 17 及以上版本核心特性在现代开发实践中的深度应用与高效实践方法 Java 开发实践
本项目以“学生成绩管理系统”为例,深入实践Java 17+核心特性与现代开发技术。采用Spring Boot 3.1、WebFlux、R2DBC等构建响应式应用,结合Record类、模式匹配、Stream优化等新特性提升代码质量。涵盖容器化部署(Docker)、自动化测试、性能优化及安全加固,全面展示Java最新技术在实际项目中的应用,助力开发者掌握现代化Java开发方法。
19 1
Java 期末考试救急必备涵盖绝大多数核心考点及五大类经典代码助你过关
本文为Java期末考试复习指南,涵盖基础语法、面向对象编程、异常处理、文件操作、数据库连接五大核心考点,提供详细解析与实用代码示例,助力快速掌握重点,高效备考,轻松应对考试。
27 0
经典排序算法之-----选择排序(Java实现)
这篇文章通过Java代码示例详细解释了选择排序算法的实现过程,包括算法的基本思想、核心代码、辅助函数以及测试结果,展示了如何通过选择排序对数组进行升序排列。
经典排序算法之-----选择排序(Java实现)

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问