介绍java中的常见排序算法

这篇具有很好参考价值的文章主要介绍了介绍java中的常见排序算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Java中的排序算法主要包括以下几种:

  1. 冒泡排序(Bubble Sort)
  2. 选择排序(Selection Sort)
  3. 插入排序(Insertion Sort)
  4. 快速排序(Quick Sort)
  5. 归并排序(Merge Sort)
  6. 堆排序(Heap Sort)

下面分别进行详细介绍。文章来源地址https://www.toymoban.com/news/detail-716371.html

1.冒泡排序(Bubble Sort) 冒泡排序是一种简单的排序算法,它通过不断交换相邻两个元素的位置,使得每次遍历结束后最大的元素被放在了最后面。时间复杂度为$O(n^2)$。

public static void bubbleSort(int[] arr){
    int n = arr.length;
    for(int i = 0; i < n - 1; i++){
        for(int j = 0; j < n - i - 1; j++){
            if(arr[j] > arr[j+1]){
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

2.选择排序(Selection Sort) 选择排序也是一种简单的排序算法,它每次找出未排序部分中最小的元素,然后将其放在已排序部分的末尾。时间复杂度为$O(n^2)$。

public static void selectionSort(int[] arr){
    int n = arr.length;
    for(int i = 0; i < n - 1; i++){
        int minIndex = i;
        for(int j = i + 1; j < n; j++){
            if(arr[j] < arr[minIndex]){
                minIndex = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

3.插入排序(Insertion Sort) 插入排序也是一种简单的排序算法,它将未排序部分的第一个元素插入到已排序的部分中的正确位置上。时间复杂度为$O(n^2)$。

public static void insertionSort(int[] arr){
    int n = arr.length;
    for(int i = 1; i < n; i++){
        int cur = arr[i];
        int j = i - 1;
        while(j >= 0 && arr[j] > cur){
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = cur;
    }
}

4.快速排序(Quick Sort) 快速排序是一种高效的排序算法,它基于分治思想,将问题分解为多个子问题。它每次选择一个基准元素将待排序的数组分为两个子数组,小于基准的放在左边,大于等于基准的放在右边,然后对两个子数组进行递归调用。时间复杂度为$O(nlogn)$。

public static void quickSort(int[] arr, int left, int right){
    if(left < right){
        int pivotPos = partition(arr, left, right);
        quickSort(arr, left, pivotPos - 1);
        quickSort(arr, pivotPos + 1, right);
    }
}

private static int partition(int[] arr, int left, int right){
    int pivot = arr[left];
    int i = left;
    int j = right;
    while(i < j){
        while(i < j && arr[j] >= pivot){
            j--;
        }
        arr[i] = arr[j];
        while(i < j && arr[i] < pivot){
            i++;
        }
        arr[j] = arr[i];
    }
    arr[i] = pivot;
    return i;
}

5.归并排序(Merge Sort) 归并排序也是一种高效的排序算法,它基于分治思想,将待排序的数组分成两个子数组,然后对子数组进行排序,最后将两个子数组进行归并。时间复杂度为$O(nlogn)$。

public static void mergeSort(int[] arr, int left, int right){
    if(left < right){
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

private static void merge(int[] arr, int left, int mid, int right){
    int[] temp = new int[right - left + 1];
    int i = left;
    int j = mid + 1;
    int k = 0;
    while(i <= mid && j <= right){
        if(arr[i] <= arr[j]){
            temp[k++] = arr[i++];
        }else{
            temp[k++] = arr[j++];
        }
    }
    while(i <= mid){
        temp[k++] = arr[i++];
    }
    while(j <= right){
        temp[k++] = arr[j++];
    }
    for(int x = 0; x < temp.length; x++){
        arr[left + x] = temp[x];
    }
}

6.堆排序(Heap Sort) 堆排序是一种高效的排序算法,它基于堆结构,将待排序的数组构建成大根堆或小根堆,然后将堆顶元素与末尾元素进行交换,并重新构建堆,重复以上步骤直到整个数组有序。时间复杂度为$O(nlogn)$。

public static void heapSort(int[] arr){
    int n = arr.length;
    for(int i = n/2-1; i >= 0; i--){
        adjustHeap(arr, i, n);
    }
    for(int i = n-1; i > 0; i--){
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        adjustHeap(arr, 0, i);
    }
}

private static void adjustHeap(int[] arr, int i, int n){
    int temp = arr[i];
    for(int j = 2*i+1; j < n; j = 2*j+1){
       if(j + 1 < n && arr[j] < arr[j+1]){
           j++;
       }
       if(arr[j] > temp){
           arr[i] = arr[j];
           i = j;
       }else{
           break;
       }
    }
    arr[i] = temp;
}

到了这里,关于介绍java中的常见排序算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构之常见排序算法

    排序:就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性:假设一组序列中,有两个相同的元素,在排序之后,两个相同元素的前后顺序颠倒了,说明这个排序算法是不稳定的,反之。 思路:把待排序的记录按其关键码值的大小

    2024年02月11日
    浏览(32)
  • 数据结构-常见的排序算法

    目录 排序的概念及其运用 排序的概念 常见的排序算法 常见排序算法的实现 插入排序 插入排序 希尔排序(缩小增量排序) 选择排序 直接选择排序 堆排序 交换排序 冒泡排序 快速排序 归并排序 非比较排序 排序算法复杂度及稳定性分析 排序 :所谓排序,就是按照某个或者某

    2024年03月12日
    浏览(47)
  • 【数据结构】常见的排序算法

    常见的七大排序算法: 最好的情况是O(n),数组为升序 最坏的情况是O(n 2 ),数组为降序 元素集合越接近有序,直接插入排序算法的时间效率越高 时间复杂度:O(N^2) 空间复杂度:O(1),它是一种稳定的排序算法 稳定性:稳定 针对直接插入排序中,当数组属于降序时,时间复杂

    2024年02月14日
    浏览(38)
  • 【数据结构】 常见的八大排序算法

    排序有 内部排序和外部排序 ,内部排序是数据记录在内存中进行排序,这里八大排序就是内部排序,指直接插入,希尔,选择,堆排,冒泡,快排,归并,计数。 下面让我们来共同学习这八大排序吧!🤗🤗🤗 什么是外部排序: 外排序是数据量较大,内存放不下,数据放到外

    2024年02月12日
    浏览(106)
  • 【数据结构】——常见排序算法(演示图+代码+算法分析)

    目录 1.  常见排序算法 1.2 稳定性 2.  常见排序算法的实现 2.1 插入排序 2.1.1基本思想 2.1.2代码 2.1.4算法分析  2.2 希尔排序 2.2.1基本思想 2.2.2代码 2.2.3演示图  2.2.4算法分析 2.3 选择排序 2.3.1基本思想 2.3.2代码 2.3.3演示图 2.3.4算法分析 2.4 堆排序 2.4.1基本思想  2.4.2代码 2.4.3演示

    2024年02月11日
    浏览(70)
  • 【数据结构---排序】庖丁解牛式剖析常见的排序算法

    排序在我们生活中处处可见,所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 常见的排序算法可以分为四大类:插入排序,选择排序,交换排序,归并排序;其中,插入排序分为直接插入排序和希尔排序;选择排序分为直接

    2024年02月16日
    浏览(60)
  • 【一起学数据结构与算法】几种常见的排序(插入排序、选择排序、交换排序、归并排序)

    排序是计算机内经常进行的一种操作,其目的是将一组 “无序” 的记录序列调整为 “有序” 的记录序列。分 内部排序 和 外部排序 ,若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序。反之,若参加排序的记录数量很大,整个序列的排序过程不可能

    2023年04月09日
    浏览(44)
  • 常见排序宝典:帮助快速上手常见基础排序算法(下)

    目录 五、归并排序 1、算法步骤  2、动图演示​编辑  3、代码实现 六、堆排序 1、算法步骤 2、动图演示  3、代码实现 七、快速排序 1、基本思想 2、动图演示 3、代码实现  八、计数排序 1、算法步骤  2、动图演示 ​编辑 3、代码实现  归并排序(MERGE-SORT)是建立在归并操

    2024年04月13日
    浏览(33)
  • 探索C语言中的常见排序算法

    排序算法是计算机科学中至关重要的基础知识之一,它们能够帮助我们对数据进行有序排列,从而更高效地进行搜索、插入和删除操作。在本篇博客中,我们将深入探讨C语言中的一些常见排序算法,包括它们的工作原理、实现代码以及性能比较。 冒泡排序是一种简单但低效

    2024年02月12日
    浏览(39)
  • 数据结构(C语言实现)——常见排序算法的基本思想及实现(快速排序的三种方法和优化及非递归实现快速排序)

    生活中几乎处处都会用到排序,比如:网购时的店铺顺序,学生成绩的排名等,今天我们就来学习数据结构中常见的几种排序算法。 排序 :所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性 :假定在待排序的记录序列

    2023年04月24日
    浏览(60)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包