【数据结构】交换排序

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

⭐ 作者:小胡_不糊涂
🌱 作者主页:小胡_不糊涂的个人主页
📀 收录专栏:浅谈数据结构
💖 持续更文,关注博主少走弯路,谢谢大家支持 💖


【数据结构】交换排序,浅谈数据结构,数据结构

1. 冒泡排序

交换排序基本思想:所谓交换,就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。
【数据结构】交换排序,浅谈数据结构,数据结构

代码实现:

    /*
    *冒泡排序
    *1.时间复杂度:O(N^2)
    *2.空间复杂度:O(1)
    *3.稳定性:稳定
    * @param array
     */
    public static void bubbleSort(int[] array){
    //i:记录躺数
    //j<array.length-i-1: -1 为了防止越界
        for(int i=0;i<array.length;i++){
            for(int j=0;j<array.length-i-1;j++){
                if(array[j+1]<array[j]){
                    int tmp=array[j+1];
                    array[j+1]=array[j];
                    array[j]=tmp;
                }
            }
        }
    }

2. 快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其**基本思想为:**任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。【数据结构】交换排序,浅谈数据结构,数据结构

代码实现:

/**
     * 快速排序-》
     * 时间复杂度:
     *       最好的情况下:O(N*logN)
     *       最坏情况下:O(N^2) 逆序/有序
     * 空间复杂度:
     *       最好的情况下:O(logN)
     *       最坏情况下:O(N) 逆序/有序
     * 稳定性:不稳定
     * @param array
     */
// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int[] array, int left, int right)
{
	if(right - left <= 1)
	return;
	// 按照基准值对array数组的 [left, right)区间中的元素进行划分
	int div = partion(array, left, right);
	// 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
	// 递归排[left, div)
	QuickSort(array, left, div);
	// 递归排[div+1, right)
	QuickSort(array, div+1, right);
}
private static void swap(int[] array,int i,int j) {
    int tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
}

上述为快速排序递归实现的主框架,发现与二叉树前序遍历规则非常像,在写递归框架时可想想二叉树前序遍历规则即可快速写出来,后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。

将区间按照基准值划分为左右两半部分的常见方式有:
1. Hosre版

/**
     * @param array
     * @param left
     * @param right
     * @return
     */
    public static int partion(int[] array,int left,int right){
        int i=left;
        int privot=array[left];//基准元素
        while(left<right){
        //大于privot的放在右边,小于的放在左边
            while(left<right&&array[right]>=privot){
                right--;
            }
            while(left<right && array[left]<=privot){
                left++;
            }
            swap(array,right,left);//right<privot<left
        }
        swap(array,i,left);//将基准元素放回
        return left;
    }

2. 挖坑法

先将一个数据存放在临时变量key中,形成一个空缺位。一般选取第一个元素。

/**
     * 挖坑法
     * @param array
     * @param left
     * @param right
     * @return
     */
    public static int partion(int[] array,int left,int right){
        int privot=array[left];
        while(left<right){
            //从右边开始
            while(left<right&&array[right]>=privot){
                right--;
            }
            array[left]=array[right];
            while(left<right&&array[left]<=privot){
                left++;
            }
            array[right]=array[left];
        }
        array[left]=privot;//将基准元素填入空位
        return left;
    }

3. 前后指针法

初始时,设置两个指针。prev指向序列开头,cur指针指向prev的后一个位置

/**
     * 前后指针法:
     * @param array
     * @param left
     * @param right
     * @return
     */
    public static int partion(int[] array,int left,int right){
        int prev=left;
        int cur=left+1;
        while(cur<=right){
            while(array[cur]<array[left] &&array[cur]!=array[++prev]){
                swap(array,prev,cur);
            }
            cur++;
        }
        swap(array,prev,left);
        return prev;
    }

以上3种方式,每次划分之后的前后顺序有可能是不一样的文章来源地址https://www.toymoban.com/news/detail-717863.html

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

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

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

相关文章

  • 【数据结构】常见排序算法——常见排序介绍、选择排序(直接选择排序、堆排序)交换排序(冒泡排序)

      选择排序是一种简单但不高效的排序算法,其基本思想是从待排序的数据中选择最小(或最大)的元素放到已排序的数据末尾。具体操作步骤如下: (1)找到数据中最小的元素,并把它交换到第一个位置; (2)在剩下未排序的元素中找到最小的元素,并把它交换到已排

    2024年02月04日
    浏览(56)
  • 数据结构进阶篇 之 【交换排序】(冒泡排序,快速排序递归、非递归实现)详细讲解

    当你觉的自己不行时,你就走到斑马线上,这样你就会成为一个行人 1.1 基本思想 1.2 实现原理 1.3 代码实现 1.4 冒泡排序的特性总结 2.1 基本思想 2.2 递归实现 2.2.1 hoare版 2.2.2 前后指针版本 2.3 快速排序优化 2.3.1 随机数选key 2.3.2 三数取中选key 2.3.3 递归到小的子区间使用插入排

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

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

    2023年04月09日
    浏览(46)
  • 数据结构:排序- 插入排序(插入排序and希尔排序) , 选择排序(选择排序and堆排序) , 交换排序(冒泡排序and快速排序) , 归并排序

    目录 前言 复杂度总结 预备代码 插入排序 1.直接插入排序: 时间复杂度O(N^2) 空间复杂度O(1) 复杂度(空间/时间): 2.希尔排序: 时间复杂度 O(N^1.3~ N^2) 空间复杂度为O(1) 复杂度(空间/时间): 选择排序 1.直接选择排序 时间复杂度O(N^2)/空间复杂度O(1) 复杂度(空间/时间)

    2024年02月07日
    浏览(57)
  • 【数据结构】浅谈数据结构-链表【思路+例题学习】

    🏆今日学习目标: 🍀学习算法-数据结构-链表 ✅创作者:贤鱼 ⏰预计时间:30分钟 🎉个人主页:贤鱼的个人主页 🔥专栏系列:算法 🍁贤鱼的个人社区,欢迎你的加入 贤鱼摆烂团 链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中

    2024年01月21日
    浏览(45)
  • 【数据结构 — 排序 — 插入排序】

    1.1.1排序的概念 排序: 所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性: 假定在待排序的记录序列中,存在多个具有相同的的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且

    2024年02月05日
    浏览(40)
  • 【数据结构 — 排序 — 选择排序】

    每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完 。 2.1算法讲解 • 在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素 • 若它不是这组元素中的最后一个(第一个)元素,则将它与这组元素中的最

    2024年02月05日
    浏览(40)
  • 数据结构—排序—选择排序

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言 一、选择排序 1、基本思想 2、直接选择排序 3、选择排序的代码实现 二、堆排序 2.1算法讲解 2.2堆排序的代码实现 总结 世上有两种耀眼的光芒,一种是正在升起的太阳,一种是正在努力

    2024年02月01日
    浏览(36)
  • 【数据结构】排序之插入排序

    在生活中处处可见排序,当我们打开京东或者其它购物平台时,搜索物品,它会有一定的排序。 这次就来分享的博客与排序有关。 正文开始。 排序 :所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性 :假定在待排序

    2024年02月03日
    浏览(29)
  • 【数据结构】快速排序,归并排序

    1.hoare版本 根据动图的演示,整理的思路如下, 1.定义left,right,key。key默认是左边第一个元素,像两个指针,左边找比key大的,右边找比k小的,找到的话,交换二者,往返这个过程,当left与right相遇时,交换key和此时相遇的值. 单趟下来,6出现在正确的位置。 1.为什么大循环

    2024年01月20日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包