七大排序算法

简介: 1. 冒泡排序2. 插入排序3. 希尔排序4. 选择排序5. 堆排序6. 快速排序7. 归并排序

1. 冒泡排序

从 0 号下标开始遍历,相邻两个数相互比较,如果左边的数大于右边的数,执行交换操作,最终每一趟冒泡都会将一个最大的数移到最右边


public class Main {
    public static void sort(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        // 外层循环记录比较次数,n 个数只需要比较 n - 1 此即可
        for (int i = 0; i < nums.length - 1; i++) {
            // 每次冒泡都会将一个最大的数移到最后,下一次冒泡不需要再遍历它,所以 -i
            for (int j = 0; j < nums.length - 1 - i; j++) {
                if (nums[j] > nums[j + 1]) {
                    // 如果左边的大于右边的,进行交换
                    swap(nums, j, j + 1);
                }
            }
        }
    }
    public static void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}

2. 插入排序

一次插入排序的过程大致如下:


将整个区间分成一个无序区间和一个有序区间,有序区间为 [0, i],无序区间为 [i + 1, n)


取出无序区间的第一个元素记为 k,反向遍历有序区间,将遍历到的每个元素跟 k 进行比较,当遍历到的元素大于 k 时,就将此元素后移一位


当遍历到有序区间的某个元素小于 k 时,说明前面的所有数小于 k,将 k 放入此元素的后一个位置即可,至此一次插排结束

public void insertSort(int[] nums) {
    for (int i = 0; i < nums.length - 1; i++) {
        // 外层循环记录插排的次数
        // 取出无序区间的第一个元素
        int k = nums[i + 1];
        int j;
        for (j = i; j >= 0; j--) {
            // 内层循环反向遍历无序区间,跟 k 进行比较
            if (nums[j] <= k) {
                // 遍历到的元素 <= k,说明前面的元素都 <= k,直接跳出循环
                break;
            }
            // 遍历到的元素 > k,将此元素位置后移一位
            nums[j + 1] = nums[j];
        }
        // 将 k 值放在比它大的元素后一个位置
        nums[j + 1] = k;
    }
}

3. 希尔排序

希尔排序可以认为是一种特殊的插入排序,一种在逻辑上设置间隔分组的插入排序


将序列内每相隔 gap 各单位的数认为是一组,然后在组内进行插入排序


gap 的初始值设置为数组长度的一半,每进行一次希尔排序,gap 变为原来的一半


当 gap 等于 1 时,就可以认为本次希尔排序是插入排序


46.png


public void shellSort(int[] nums) {
    // 定义间隔 gap
    int gap = nums.length / 2;
    // 循环开始进行排序
    while (gap >= 1) {
        for (int i = 0; i < nums.length - gap; i++) {
            // 取出无序数组第一个元素
            // 组内元素之间是有间隔存在的,所以取无序区间的第一个元素时需要加上间隔值 gap
            int k = nums[i + gap];
            int j;
            // 循环遍历本组的有序区间,并且将遍历到的元素跟 k 比较
            for (j = i; j >= 0; j -= gap) {
                if (nums[j] <= k) {
                    break;
                }
                // 当遍历到的元素大于 k,就将此元素位置后移 gap 位
                nums[j + gap] = nums[j];
            }
            // 将 k 值放在比它大的元素后 gap 位
            nums[j + gap] = k;
        }
        // 每进行完一次希尔排序,就将 gap 变为原来的一半
        gap /= 2;
    }
}

4. 选择排序

将整个序列在逻辑上分成有序区间和无序区间,有序区间在前,无序区间在后


每一次选择排序都会将无序区间中最大的元素放到无需区间的最后一位,然后在逻辑上将无序区间的最后一位规划给有序区间


因为每次在无序区间中选出的都是最大的元素,所以可以保证后面有序区间必然有序


在第一次选择排序之前,有序区间是不存在的,整个序列都是无序序列


public void selectSort(int[] nums) {
        // 外层循环控制进行选择排序的次数
        for (int i = 0; i < nums.length - 1; i++) {
            int maxIndex = 0;   // 假设无需区间的最大元素在第一位
            // 遍历无序区间,找到最大的元素,将最大元素的下标赋给 maxIndex
            for (int j = 1; j < nums.length - i; j++) {
                if (nums[j] > nums[maxIndex]) {
                    maxIndex = j;
                }
            }
            // 交换最大元素和无序区间的最后一个元素
            swap(nums, maxIndex, nums.length - 1 - i);
        }
    }
    private void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}

5. 堆排序

堆排序可以说是一种特殊的选择排序


同选择排序一样,将整个序列分为有序区间和无序区间,再将无序区间的最大值(或最小值)放到无序区间的最后,再在逻辑上把这个元素规划给有序区间


不同的是,堆排序中以堆的性质来要求无序区间,使得无序区间的第一个元素永远是最大(或最小)的


也就是把在选择排序中循环寻找最大值的操作替换成了堆中的向下调整的操作,向下调整可以使得堆顶元素保持最大(或最小)


向下调整的步骤:


判断当前节点是不是叶子节点,如果是叶子节点,直接退出,如果不是,继续下面步骤

找到当前节点左右孩子的最大值

如果小于,说明符合大根堆的性质,退出即可

如果最大值大于当前节点就交换当前节点的值和最大值

如果发生了交换,很有可能破坏了下面节点的大根堆性质,则继续对下面节点进行向下调整


public void heapSort(long[] nums) {
    // 建立大根堆
    // 当前例子进行递增排序,如果需要进行递减排序,则需要建立小根堆
    createBigHeap(nums);
    // 控制交换次数
    for (int i = 0; i < nums.length - 1; i++) {
        // 交换无序区间第一个元素和最后一个元素
        swap(nums, 0, nums.length - 1 - i);
        // 交换完成之后进行向下调整,使得数组符合大根堆的性质
        // 逻辑上交换完成之后无序区间的最后一个元素已经属于有序区间,所以进行向下调整的堆的 size 应该减去已经进入有序区间的元素的个数
        shiftDown(nums, nums.length - 1 - i, 0);
    }
}
// 建堆就是对数组从最后一个非叶子节点下标处开始向前循环进行向下调整的操作
private void createBigHeap(long[] nums) {
    for (int i = (nums.length - 2) / 2; i >= 0; i--) {
        shiftDown(nums, nums.length, i);
    }
}
private void shiftDown(long[] nums, int size, int index) {
    // 当当前节点的下标大于或等于 size 时,说明当前节点是叶子节点
    while (2 * index + 1 < size) {
        int maxIndex = 2 * index + 1;   // 假设当前节点左孩子为最大值
        int right = maxIndex + 1;
        // 如果右孩子存在且右孩子的值大于左孩子的值,将右孩子的值赋给最大值
        if (right < size && nums[right] > nums[maxIndex]) {
            maxIndex = right;
        }
        // 如果当前节点的值大于等于最大值,说明符合大根堆,直接 return
        if (nums[index] >= nums[maxIndex]) {
            return;
        }
        // 如果不满足大根堆,就交换当前节点的值和最大值
        swap(nums, index, maxIndex);
        // 将最大值下标赋给 index,继续循环进行向下调整
        index = maxIndex;
    }
}
private void swap(long[] nums, int a, int b) {
    long tmp = nums[a];
    nums[a] = nums[b];
    nums[b] = tmp;
}

6. 快速排序

大致流程:


选择一个元素作为基准值(pivot),一般选择最右边或最左边的元素,通过遍历的方式,比较 pivot 和区间内其他元素的大小关系

在遍历期间,通过算法的设计,保证如下图所示的区间内位置关系,此时 pivot 就位于当区间有序时它该处于的位置

继续对左右两个小区间按照同样的方式进行处理


47.png


在元素遍历过程中,引入几个边界值,来保证下图所示的区间位置关系

48.png


public void quickSort(long[] nums) {
    quickSortRange(nums, 0, nums.length - 1);
}
private void quickSortRange(long[] nums, int from, int to) {
    // 当待比较区间中只有一个或没有元素时,说明比较结束
    if (to - from + 1 <= 1) {
        return;
    }
    // 对待比较区间中的元素做 partition
    // 将大于基准值(pivot)的元素放在 pivot 前面,小于 pivot 的元素放在 pivot 后面
    // 最终得到 pivot 有序时应该存在于区间中的下标
    int pi = partition(nums, from, to);
    // 对 pivot 左边的元素递归排序
    quickSortRange(nums, from, pi - 1);
    // 对 pivot 右边的元素递归排序
    quickSortRange(nums, pi + 1, to);
}
private int partition(long[] nums, int from, int to) {
    // 定义 left 和 right,确定待比较区间的左右边界下标
    int left = from;
    int right = to;
    // 定义 pivot 值,一般定义为区间最右边的值
    long pivot = nums[to];
    // 只要待比较区间中还有元素,就继续循环
    while (left < right) {
        // 循环比较,当左边的元素小于 pivot 时,left 下标就右移,大于时跳出循环
        // 加上 left < right 条件是因为,left 在循环 ++ 的时候,很有可能跳出边界值,所以在每次比较之前先保证 left 值合法
        while (left < right && nums[left] <= pivot) {
            left++;
        }
        // 循环比较,当右边的元素大于 pivot 时,right 下标就左移,小于时跳出循环
        // 加上 left < right 条件是因为,right 在循环 -- 的时候,很有可能跳出边界值,所以在每次比较之前先保证 right 值合法
        while (left < right && nums[right] >= pivot) {
            right--;
        }
        // 上面两次循环都跳出之后,说明当前 right 下标处元素小于 pivot,left 下标处元素大于 pivot,交换两元素位置
        swap(nums, left, right);
    }
    // 当待比较区间没有元素时,将 pivot 和当前 left 下标处的元素交换位置
    swap(nums, left, to);
    // 返回 pivot 下标
    return left;
}
private void swap(long[] nums, int a, int b) {
    long tmp = nums[a];
    nums[a] = nums[b];
    nums[b] = tmp;
}

7. 归并排序

基本思路: 归并排序就是将区间分成一个个小区间分别进行排序,在对小区间进行合并得到最终有序的大区间。基本步骤如下图:


49.png


public void mergeSort(long[] nums) {
    mergeSortRange(nums, 0, nums.length);
}
private void mergeSortRange(long[] nums, int from, int to) {
    // 计算当前区间元素数量
    int size = to - from;
    // 找到当前区间中间下标
    int mid = from + size / 2;
    // 当前区间中元素个数 <= 1 时,说明此区间排序完成
    if (size <= 1) {
        return;
    }
    // 对左边小区间进行递归排序
    mergeSortRange(nums, from, mid);
    // 对右边小区间进行递归排序
    mergeSortRange(nums, mid, to);
    // 合并有序数组
    merge(nums, from, mid, to);
}
private void merge(long[] nums, int from, int mid, int to) {
    // 计算合并后总共需要的数组大小
    int size = to - from;
    // 初始化一个数组,用来存放排好序的元素
    long[] array = new long[size];
    // 左边小区间的下标
    int left = from;
    // 右边小区间的下标
    int right = mid;
    // 存放有序序列的数组下标
    int dest = 0;
    // 左右两个区间中还有元素,就继续进行比较
    while (left < mid && right < to) {
        if (nums[left] <= nums[right]) {
            // 左边区间元素更小,放入临时数组
            array[dest++] = nums[left++];
        } else {
            // 右边区间元素更小,放入临时数组
            array[dest++] = nums[right++];
        }
    }
    // 当有一个区间的元素取完之后,另一个区间的元素还有可能没有取完,全部放入
    // 下面两个循环肯定只会执行一个
    while (left < mid) {
        array[dest++] = nums[left++];
    }
    while (right < to) {
        array[dest++] = nums[right++];
    }
    // 将临时数组的元素放入原始数组中
    for (int i = 0; i < size; i++) {
        nums[from + i] = array[i];
    }
}


目录
相关文章
|
存储 负载均衡 监控
分布式定时任务,你了解多少?基于Quartz实现分布式定时任务解决方案!
定时任务系统在应用平台中的重要性不言而喻,特别是互联网电商、金融等行业更是离不开定时任务。在任务数量不多、执行频率不高时,单台服务器完全能够满足。但是随着业务逐渐增加,定时任务系统必须具备高可用和水平扩展的能力,单台服务器已经不能满足需求。因此需要把定时任务系统部署到集群中,实现分布式定时任务系统集群。
5409 1
分布式定时任务,你了解多少?基于Quartz实现分布式定时任务解决方案!
|
10月前
|
机器学习/深度学习
深入理解SVM中的核函数及其应用
深入理解SVM中的核函数及其应用
454 91
|
11月前
|
设计模式 安全 Java
Java编程中的单例模式深入剖析
【10月更文挑战第21天】在Java的世界里,单例模式是设计模式中一个常见而又强大的存在。它确保了一个类只有一个实例,并提供一个全局访问点。本文将深入探讨如何正确实现单例模式,包括常见的实现方式、优缺点分析以及最佳实践,同时也会通过实际代码示例来加深理解。无论你是Java新手还是资深开发者,这篇文章都将为你提供宝贵的见解和技巧。
177 65
|
11月前
|
运维 Prometheus 监控
运维中的自动化实践每月一次的系统维护曾经是许多企业的噩梦。不仅因为停机时间长,更因为手动操作容易出错。然而,随着自动化工具的引入,这一切正在悄然改变。本文将探讨自动化在IT运维中的重要性及其具体应用。
在当今信息技术飞速发展的时代,企业对系统的稳定性和效率要求越来越高。传统的手动运维方式已经无法满足现代企业的需求。自动化技术的引入不仅提高了运维效率,还显著降低了出错风险。本文通过几个实际案例,展示了自动化在IT运维中的具体应用,包括自动化部署、监控告警和故障排除等方面,旨在为读者提供一些实用的参考。
|
运维 网络协议 搜索推荐
内核网络小白之故障寻踪记
本文记述了一次由 skb(socket buffer)异常导致的内核故障排查过程。
291 12
|
运维 Kubernetes Cloud Native
主流定时任务解决方案全横评
定时任务作为一种按照约定时间执行预期逻辑的通用模式,在企业级开发中承载着丰富的业务场景,诸如后台定时同步数据生成报表,定时清理磁盘日志文件,定时扫描超时订单进行补偿回调等。
主流定时任务解决方案全横评
|
Python
python-logging全局日志配置-滚动删除,只保存最近7天的日志,按级别存入不同文件
最近有这样一个需求,需要记录一下用户行为,和记下一些错误日志,放入指定文件夹里不同的文件下,方便后续debug。我决定采用python logging模块。并且使用配置文件,并做一个全局的globalLog.py来使用logging。 (关键词:logging,TimedRotatingFileHandler)
989 0
python-logging全局日志配置-滚动删除,只保存最近7天的日志,按级别存入不同文件
|
存储 算法 C语言
c++游戏制作指南(二):制作一个炫酷的启动界面(c++绘图)
c++游戏制作指南(二):制作一个炫酷的启动界面(c++绘图)
694 0
|
缓存 NoSQL Java
Guava Cache 异步刷新技巧,你值得拥有!
Guava Cache是一款非常优秀的本地缓存框架,提供非常简洁易用的 API 供开发者使用。 这篇文章,我们聊聊如何使用 Guava Cache **异步刷新技巧**带飞系统性能 。
Guava Cache 异步刷新技巧,你值得拥有!