排序算法--Java实例/原理

IT利刃出鞘

已于 2023-06-29 22:59:04 修改

阅读量2.1k

点赞数 20

文章标签：算法

于 2021-11-23 18:51:34 首次发布

本文链接：https://blog.csdn.net/feiying0canglang/article/details/121432039

版权

Java面试真题专栏收录该内容

196 篇文章 126 订阅

订阅专栏

原文网址：排序算法--Java实例/原理_IT利刃出鞘的博客-CSDN博客

简介

本文用Java示例来介绍排序算法。

本内容也是Java后端面试常见的问题。

排序算法概述

复杂度

分类

十种常见排序算法可以分为两大类：

非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。
线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。

概念介绍

稳定：如果a原本在b前面且a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面且a=b，排序之后 a 可能会出现在 b 的后面。
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
In-Place：占用常数内存，不占用额外内存。比如：程序里没有创建新数组来保存数据，只用了临时变量。
Out-Place：占用额外内存。比如：创建了新的数组来保存或者处理数据。

排序算法应用场景及选择

1）若 n 较小（如n ≤ 50）时，可采用直接插入或简单选择排序。
2）若元素初始状态基本有序（正序），直接插入、冒泡或快速排序为宜。
3）若 n 较大，则应采用时间复杂度为O(nlogn)的排序方法：快速排序、堆排序或归并排序。

快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短。

堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。

若要求排序稳定，则可选用归并排序。但本文介绍的从单个记录起进行两两归并的归并排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序数列，然后再两两归并之。因为直接插入排序是稳定的，所以改进后的归并排序仍是稳定的。

当范围已知，且空间不是很重要的情况下可以考虑使用桶排序。

冒泡排序（Bubble Sort）

基本思想

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为每趟比较将当前数列未排序部分的最大的元素“沉”到数列末端，而小的元素会经由交换慢慢“浮”到数列的顶端。

算法描述

比较相邻的元素。如果前一个比后一个大，就交换它们两个；
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
针对所有的元素重复以上的步骤，除了最后一个；
重复步骤1~3，直到排序完成。为了优化算法，可以设立一个布尔标识，每趟排序开始前设为false，如果该趟排序发生了交换就置为true，如果一趟排序结束标识仍为false表示该趟排序没有发生交换，即数组已经有序，可以提前结束排序。

动图演示

代码实现

public static int[] bubbleSort(int[] array) {
    if (array.length == 0)
        return array;
    for (int i = 0; i < array.length; i++){  //外层循环一次为一趟排序
        /*设置标识，判断这趟排序是否发生了交换。
       如果未发生交换，则说明数组已经有序，不必再排序了*/
        boolean isSwap = false;
        //内层循环一次为一次相邻比较
        for (int j = 0; j < array.length - 1 - i; j++) {
            if (array[j + 1] < array[j]) {
                int temp = array[j + 1];
                array[j + 1] = array[j];
                array[j] = temp;
                isSwap = true;
            }
        }
        if (!isSwap)
            break;
    }
    return array;
}

时间复杂度

冒泡排序平均时间复杂度为O(n2)，最好时间复杂度为O(n)，最坏时间复杂度为O(n2)。

最好情况：如果待排序元素本来是正序的，那么一趟冒泡排序就可以完成排序工作，比较和移动元素的次数分别是 (n - 1) 和 0，因此最好情况的时间复杂度为O(n)。

最坏情况：如果待排序元素本来是逆序的，需要进行 (n - 1) 趟排序，所需比较和移动次数分别为 n * (n - 1) / 2和 3 * n * (n-1) / 2。因此最坏情况下的时间复杂度为O(n2)。

空间复杂度

冒泡排序使用了常数空间，空间复杂度为O(1)

稳定性

当 array[j] == array[j+1] 的时候，我们不交换 array[i] 和 array[j]，所以冒泡排序是稳定的。

算法拓展

鸡尾酒排序，又称定向冒泡排序、搅拌排序等，是对冒泡排序的改进。在把最大的数往后面冒泡的同时，把最小的数也往前面冒泡，同时收缩无序区的左右边界，有序区在序列左右逐渐累积。

动图如下：

代码如下：

public static void cocktailSort(int[] array) {
    int left = 0,right = array.length-1;
    while(left < right) {
        for(int i = left; i < right; i++) 
          if(array[i] > array[i+1]) 
                swap(array,i,i + 1);
        right--;
        for(int i = right; i > left; i--) 
          if(array[i] < array[i-1]) 
                swap(array,i,i-1);
        left++;
    }
}

鸡尾酒排序是稳定的。它的平均时间复杂度为O(n2)，最好情况是待排序列原先就是正序的，时间复杂度为O(n)，最坏情况是待排序列原先是逆序的，时间复杂度为O(n2)。空间复杂度为O(1)。