算法通关村第10关【青铜】| 快速排序各种写法

这篇具有很好参考价值的文章主要介绍了算法通关村第10关【青铜】| 快速排序各种写法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

算法通关村第10关【青铜】| 快速排序各种写法,算法,数据结构

思路:

指定一个数字,将数组比他小的放到左边,比他大的放到右边,实现归位

然后再指定一个数字递归,一直遍历完数组

最好的情况每次指定的都是中间位置的数字,划分完后两边长度相等,2T(n/2) + O(n),复杂度O(nlog(n))

可以证明,平均情况下的时间复杂度也是O(nlog(n))

最坏的情况,每次指定的都是最小的数字,n的复杂度归位,一共n次,T(n-1) + O(n),复杂度O(n^2)

方式一、对撞型指针+指定头元素

class Solution {
    public int[] sortArray(int[] nums) {
        trace(nums,0,nums.length - 1);
        return nums;
    }

    public void trace(int[] nums,int start,int end) {
        if(start>=end){
            return;
        }
        int p = nums[start];
        int l = start;
        int r = end;
        while(l<r){
            while(nums[r]>=p&&l<r){
                r--;
            }
            nums[l] = nums[r];
            while(nums[l]<=p&&l<r){
                l++;
            }
            nums[r] = nums[l];
        }
        nums[l] = p;
        trace(nums,l + 1,end);
        trace(nums,start,l-1);
    }


}

方式二、对撞型指针+指定中间

这里要注意的细节很多,判断条件的时候nums[l]>p不能等于,不然左指针会跑到右边去同理右边

同时l<=r,不能是小于

class Solution {
    public int[] sortArray(int[] nums) {
        trace(nums,0,nums.length - 1);
        return nums;
    }

    public void trace(int[] nums,int start,int end) {
        if(start>=end){
            return;
        }
        int p = nums[(start+end)/2];
        int l = start;
        int r = end;
        while(l<=r){
            while(nums[r]>p&&l<=r){
                r--;
            }
            while(nums[l]<p&&l<=r){
                l++;
            }
            if(l<=r){
                swap(nums,l,r);
                l++;
                r--;
            }
        }
        trace(nums,start,r);
        trace(nums,l,end);
    }

     private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}

方式三、快慢指针+指定尾元素文章来源地址https://www.toymoban.com/news/detail-691792.html

lass Solution {
    public int[] sortArray(int[] nums) {
        partition(nums, 0, nums.length - 1);
        return nums;
    }

    public void partition(int[] nums, int l, int r) {
        if(l<r){
            int pivot = nums[r];
            int i = l - 1;
            //快慢指针找到目标位置
            for (int j = l; j <= r - 1; ++j) {
                if (nums[j] <= pivot) {
                    i = i + 1;
                    swap(nums, i, j);
                }
            }
            //放置目标元素
            swap(nums, i + 1, r);
            int p = i+1;
            //递归
            partition(nums,l,p-1);
            partition(nums,p+1,r);
        }
    }
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

到了这里,关于算法通关村第10关【青铜】| 快速排序各种写法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 算法通关村第一关——链表青铜挑战笔记

    链表的基本单元就是 节点 ,也就是说链表是由一个一个节点构成的。 而对于节点来说,里面至少会包含一个 指针 和一个 数据元素 ,也就是如下图所示: 其中数据域用来存放数据元素,指针域用来存放指向下一个节点的指针,这样一个一个连接起来的就是链表。如下图所

    2024年02月16日
    浏览(43)
  • 《算法通关村第一关——链表青铜挑战笔记》

    链表中每个结点内部的“生态环境”。 数据域存储元素的值,指针域存放指针。 示例: c语言构造链表 可分为三步 1.创建头指针。 2.创建头结点,使头指针指向头结点。 3.循环创建结点,并使前一个结点指向当前结点。 1.)创建结点。 2.)使前一个结点指向当前结点。 3.)

    2024年02月15日
    浏览(40)
  • 算法通关村第一关———链表青铜挑战笔记

    通过类来构建节点,用next指针将节点连起来。 会有插入位置的范围问题,不能超出链表范围 会有删除位置的范围问题 构造双向链表 插入和删除都有三种情况,头中尾  

    2024年02月15日
    浏览(44)
  • 算法通关村第一关--链表青铜挑战笔记

    开始时间:2023年7月16日20:45:26 什么是链表,链表是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思)。 链表的入口节点称为链表的头结点也就是hea

    2024年02月17日
    浏览(44)
  • 算法通关村第一关 | 链表青铜挑战笔记

    一、 什么是链表? 链表是一种比较简单、很常见的数据结构,是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 二、链表的特点 链表是一种比较简单、很常见的数据结构,是线性表(List)的一种,是一种物理存

    2024年02月14日
    浏览(38)
  • 编程导航算法通关村第一关|青铜|链表基础

    JVM有栈区和堆区 栈区:存引用,就是指向实际对象的地址。。 堆区:存的是创建的对象。 定义 规范的链表定义 LeetCode算法题中常用 遍历 插入 删除 结点 结构遍历 插入 从头插入 从尾插入 从某个值为key的节点后面插入 删除 删除头结点 删除尾结点 按值删除

    2024年02月15日
    浏览(41)
  • 【无标题】算法通关村第一关——链表青铜挑战笔记

    算法通关村第一关——链表青铜挑战笔记 C语言是如何构造出链表的 0.定义节点结构 1.建立头指针 2.建立temp指针 3.将节点连起来 3.1 把p指向temp 3.2 设立循环节点a+temp指向a+temp变为a

    2024年02月15日
    浏览(37)
  • 算法通关村第一关——链表青铜挑战笔记(单链表)

    在LeeCode中一般这样创建链表 要注意创建一个变量来遍历,不要把head丢掉了 count position - 1可以方便操作,还能防止下标越界(cur为null)

    2024年02月15日
    浏览(39)
  • [Go版]算法通关村第一关——链表青铜挑战笔记

    单向链表图示: 双向链表图示: 环形单向链表图示: 环形双向链表图示: 源码地址: GitHub-golang版本 如果是单向的,需要将当前节点 定位到要插入节点的前一个节点 ,否则一旦过了将无法回头找到前一个节点 如果是双向的,将当前节点 定位到要插入节点的前一个节点、

    2024年02月15日
    浏览(47)
  • 算法通关村第十七关:青铜挑战-贪心其实很简单

    1. 难以解释的贪心算法 贪心学习法则:直接做题,不考虑贪不贪心 贪心(贪婪)算法 是指在问题尽心求解时,在每一步选择中都采取最好或者最优(最有利)的选择,从而希望能够导致结果最好或者最优的算法 贪心算法所得到的结果不一定是最优的结果,但是都是相对近似最

    2024年02月09日
    浏览(41)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包