十大排序算法与Java实现

本文参考资源:

https://github.com/iTimeTraveler/SortAlgorithms

十大经典排序算法 - 冰狼爱魔 - 博客园

十大经典排序算法总结(Java语言实现)_Java_wang的博客-CSDN博客

排序算法概述

十大排序算法与Java实现

可以看到时间复杂度低的算法空间复杂度通常较高,甚至最后三种算法已经没有原地算法了,这就是常说的“用空间换时间”,越往后越不接近人的自然思想,可能就会更难理解,毕竟人通常是不会在脑子里排序的时候为这个数组开辟出一块新区域用空间换时间的。

是否稳定的意思是指,一轮排序之后,是否会破坏尚未比较元素之间的相对顺序,若排序前数组本身有序性已经较为良好,使用稳定算法进行排序效率会高些。而非稳定的算法有的时候应用在数据有序性不太好的情况下偶尔有奇效。

插入排序

插入排序把数组分为已排序的部分和未排序的部分,这种算法通常采用原地策略,将每个元素与之前的元素交换,直到找到合适的位置。

十大排序算法与Java实现

Java代码:

public void insertionSort2(int[] arr){
    for(int i=0; i<arr.length-1; i++ ) {
        for( int j=i+1; j>0; j-- ) {
            if( arr[j-1] <= arr[j] )
                break;
            int temp = arr[j];      //交换操作
            arr[j] = arr[j-1];
            arr[j-1] = temp;
        }
    }
    System.out.println(Arrays.toString(arr));
}

选择排序

选择排序也是很接近人的自然思想的一种排序方法,也分为已排序的部分和未排序的部分,直接在未排序的序列中找到最小值,附加到已排序的序列末尾(和未排序序列的第一个元素交换)

十大排序算法与Java实现

Java代码:

public void insertionSort2(int[] arr){
    for(int i=0; i<arr.length-1; i++ ) {
        for( int j=i+1; j>0; j-- ) {
            if( arr[j-1] <= arr[j] )
                break;
            int temp = arr[j];      //交换操作
            arr[j] = arr[j-1];
            arr[j-1] = temp;
        }
    }
    System.out.println(Arrays.toString(arr));
}

冒泡排序

冒泡排序的思想也很容易理解,每次遍历比较相邻的两个元素,将它们的顺序排好,这样一直遍历直到所有元素被正确排序。

十大排序算法与Java实现

/**
 * 冒泡排序
 *
 * ①. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
 * ②. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
 * ③. 针对所有的元素重复以上的步骤,除了最后一个。
 * ④. 持续每次对越来越少的元素重复上面的步骤①~③,直到没有任何一对数字需要比较。
 * @param arr  待排序数组
 */
public static void bubbleSort(int[] arr){
    for (int i = arr.length - 1; i > 0; i--) {      //外层循环移动游标
        for(int j = 0; j < i; j++){    //内层循环遍历游标及之后(或之前)的元素
            if(arr[j] > arr[j+1]){
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                System.out.println("Sorting: " + Arrays.toString(arr));
            }
        }
    }
}

归并排序

十大排序算法与Java实现

这个的思想就是分治啦,先把数组拆分成一个一个元素的子序列,然后一直在合并两个子序列(双指针法),直到合并回一个完整的数组。

/**
* 归并排序,递归方法
*
* @param array
* @return
*/
public static int[] MergeSort(int[] array) {
    if (array.length < 2) return array;
    int mid = array.length / 2;
    int[] left = Arrays.copyOfRange(array, 0, mid);
    int[] right = Arrays.copyOfRange(array, mid, array.length);
    return merge(MergeSort(left), MergeSort(right));
}
/**
* 归并排序——将两段排序好的数组结合成一个排序数组
*
* @param left
* @param right
* @return
*/
public static int[] merge(int[] left, int[] right) {
    int[] result = new int[left.length + right.length];
    for (int index = 0, i = 0, j = 0; index < result.length; index++) {
        if (i >= left.length)
            result[index] = right[j++];
        else if (j >= right.length)
            result[index] = left[i++];
        else if (left[i] > right[j])
            result[index] = right[j++];
        else
            result[index] = left[i++];
    }
    return result;
}

堆排序

这个之前已经写过啦,见带有优先级的完全二叉树-堆

快速排序

快速排序的思想也是分治,我们从数组中选择一个元素,我们把这个元素称之为中轴元素(基准)吧,然后把数组中所有小于中轴元素的元素放在其左边,所有大于或等于中轴元素的元素放在其右边,显然,此时中轴元素所处的位置的是有序的。也就是说,我们无需再移动中轴元素的位置。

从中轴元素那里开始把大的数组切割成两个小的数组(两个数组都不包含中轴元素),接着我们通过递归的方式,让中轴元素左边的数组和右边的数组也重复同样的操作,直到数组的大小为1,此时每个元素都处于有序的位置。

十大排序算法与Java实现

public class QuickSort {
    public static int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            //获取中轴元素所处的位置
            int mid = partition(arr, left, right);
            //进行分割
            arr = quickSort(arr, left, mid - 1);
            arr = quickSort(arr, mid + 1, right);
        }
        return arr;
    }

    //每次都假设第一个元素是中轴元素,但分成两个序列块之后要把中轴元素交换到中间
    private static int partition(int[] arr, int left, int right) {
        //选取中轴元素
        int pivot = arr[left];
        int i = left + 1;
        int j = right;
        while (true) {
            // 向右找到第一个小于等于 pivot 的元素位置
            while (i <= j && arr[i] <= pivot) i++;
            // 向左找到第一个大于等于 pivot 的元素位置
            while(i <= j && arr[j] >= pivot ) j--;
            if(i >= j)
                break;
            //交换两个元素的位置,使得左边的元素不大于pivot,右边的不小于pivot
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        arr[left] = arr[j];
        // 使中轴元素处于有序的位置
        arr[j] = pivot;
        return j;
    }
}

快速排序的最坏情况还是蛮恐怖的,如果每一次选取的中轴元素都是当前序列最大/最小的元素。

说一下为什么快速排序是原地算法,空间复杂度还是O(logN),是因为这个空间复杂度计算了递归调用栈空间的使用,栈的深度为logN

希尔排序

希尔排序是插入排序的改进算法,它按按一定的间隔为逻辑分组进行插入排序,这个间隔会慢慢缩小。

先让数组中任意间隔为 h 的元素有序,刚开始 h 的大小可以是 h = n / 2,接着让 h = n / 4,让 h 一直缩小,当 h = 1 时,也就是此时数组中任意间隔为1的元素有序,此时的数组就是有序的了。

希尔排序难得在时间复杂度为O(nlogn)的算法之中还维持着原地排序O(1)的时间复杂度,其思想值得学习。

十大排序算法与Java实现

public class ShellSort {
    public static int[] shellSort(int arr[]) {
        if (arr == null || arr.length < 2) return arr;
        int n = arr.length;
        // 对每组间隔为 h的分组进行排序,刚开始 h = n / 2;
        for (int h = n / 2; h > 0; h /= 2) {
        //对各个局部分组进行插入排序
            for (int i = h; i < n; i++) {
            // 将arr[i] 插入到所在分组的正确位置上
            insertI(arr, h, i);
        }
     }
     return arr;
    }

    /**
     * 将arr[i]插入到所在分组的正确位置上
     * arr[i]] 所在的分组为 ... arr[i-2*h],arr[i-h], arr[i+h] ...
     */
    private static void insertI(int[] arr, int h, int i) {
        int temp = arr[i];
        int k;
        for (k = i - h; k > 0 && temp < arr[k]; k -= h) {
            arr[k + h] = arr[k];
        }
        arr[k + h] = temp;
    }
}

计数排序

计数排序就很像bitmap了(见海量数据算法-BitMap介绍和实现),如果回想bitmap,它的排序效率是极高的,但元素不能重复,如果要解决元素不能重复的问题,就可以将bit(表示是否存在)转为int(表示出现了多少次)。

这种算法的问题就很明显了,首先得知道元素取值的范围,如果范围太大还得用int存储空间复杂度极高。所以它适用于取值范围不大的数组排序。然后元素只能是整数,否则无法和数组的下标关联起来。

桶排序

桶排序也得知道元素的取值范围,它是把所有元素按取值范围划分为若干个区间(桶),桶的个数通常就等于数组的大小,按(array[i] - min) * (bucketNum-1) / d将元素划分到桶中(即按取值范围均分)。然后在每个桶内按归并排序或快速排序算法排序,由于桶之间本来就是有序的,再把它们按桶的顺序连接起来即可。

基数排序

基数排序的排序思路是这样的:先以个位数的大小来对数据进行排序,接着以十位数的大小来多数进行排序,接着以百位数的大小……

排到最后,就是一组有序的元素了。不过,它在以某位数进行排序的时候,是用“桶”来排序的。

由于某位数(个位/十位….,不是一整个数)的大小范围为0-9,所以我们需要10个桶,然后把具有相同数值的数放进同一个桶里,之后再把桶里的数按照0号桶到9号桶的顺序取出来,这样一趟下来,按照某位数的排序就完成了

十大排序算法与Java实现

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e5%8d%81%e5%a4%a7%e6%8e%92%e5%ba%8f%e7%ae%97%e6%b3%95%e4%b8%8ejava%e5%ae%9e%e7%8e%b0/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年3月10日
下一篇 2020年3月11日

相关推荐

  • leetcode836-矩形重叠

    原题 矩形以列表 [x1, y1, x2, y2] 的形式表示,其中 (x1, y1) 为左下角的坐标,(x2, y2) 是右上角的坐标。 如果相交的面积为正,则称两矩形重叠。需要…

    算法 2020年3月18日
    0450
  • leetcode590-N叉树的后序遍历

    原题 给定一个 N 叉树,返回其节点值的后序遍历。 例如,给定一个 3叉树 : 返回其前序遍历: [5,6,3,2,4,1]. 说明: 递归法很简单,你可以使用迭代法完成此题吗? …

    2020年1月20日
    0100
  • leetcode66-加一

    原题 给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。 最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。 你可以假设除了整数 0 之外,这个整数不会以…

    算法 2019年11月14日
    0140
  • leetcode1111-有效括号的嵌套深度

    原题 有效括号字符串 仅由 "(" 和 ")" 构成,并符合下述几个条件之一: 空字符串 连接,可以记作 AB(A 与 B 连接),其中 A 和 B 都是有效括号字符串 嵌套,可以…

    算法 2020年4月1日
    0100
  • leetcode134-加油站

    原题 在一条环路上有 N 个加油站,其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[…

    算法 2020年2月16日
    080
  • leetcode236-二叉树的最近公共祖先

    原题 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 …

    2020年1月15日
    080
  • 剑指offer51-数组中的逆序对

    原题(来源Leetcode) 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。 示例 1: 输入: [7…

    算法 2020年4月24日
    0400
  • leetcode876-链表的中间结点

    原题 给定一个带有头结点 head 的非空单链表,返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。 示例 1: 输入: [1,2,3,4,5] 输出: 此列表中的结…

    算法 2020年3月23日
    090
  • 用一个栈实现另一个栈的排序

    原题(来源牛客网) 一个栈中元素的类型为整型,现在想将该栈从顶到底按从大到小的顺序排序,只许申请一个栈。除此之外,可以申请新的变量,但不能申请额外的数据结构。如何完成排序? 解法 …

    算法 2020年4月20日
    02110
  • leetcode74-搜索二维矩阵

    原题 编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性: 每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。   示例…

    算法 2020年4月29日
    0210

发表回复

登录后才能评论