leetcode刷题笔记_排序1

2021/7/27 23:06:06

本文主要是介绍leetcode刷题笔记_排序1,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

排序

冒泡排序

  • 两两交换,依次把最大值移到最后面

    #include <iostream>
    #include <cstring>
    #include <vector>
    #include <map>
    #include <cmath>
    #include <set>
    using namespace std;
    void busort(vector<int>& arr)
    {
        for (int i = 0; i < arr.size(); i++)
        {
            for (int j = 1; j < arr.size() - i - 1; j++)
            {
                if (arr[j - 1] > arr[j])
                {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                }
    
            }
        }
    }
        
    int main()
    {
        vector<int> arr = {1,4,2,3,7,5,9,6,8};
        busort(arr);
        for (int i = 0; i < arr.size(); i++)
            cout << arr[i] << endl;
        return 0;
    }
    
    

把数组排成最小的数

题目:输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。

测试用例:

输入: [10,2]
输出: "102"

思路:其实就是对数组中的每个数的每一位进行排序,取最小的值

代码

class Solution {
public:
     string minNumber(vector<int>& nums) {
        if (nums.size() == 0)
            return "";
        string res;

        //对数组进行排序,如果两个数交换顺序之后组成的字符串更小,就交换两个数
        for (int k = 0; k < nums.size(); k++)
        {
            for (int x = 1; x < nums.size(); x++)
            {
                if (to_string(nums[x])+to_string(nums[x-1])< to_string(nums[x-1]) + to_string(nums[x]))
                {
                        int temp = nums[x];
                        nums[x] = nums[x - 1];
                        nums[x - 1] = temp;
                }
            }
        }
    //对每一位数把整形转化为字符串
        for (int k = 0; k < nums.size(); k++)
        {
            res = res + to_string(nums[k]);
        }
        return res;
    }
};

移动零

  • 题目:给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

  • 测试样例

  • 输入: [0,1,0,3,12]
    输出: [1,3,12,0,0]
    
  • 代码

    class Solution {
    public:
        void moveZeroes(vector<int>& nums) {
            //采用冒泡排序思想,遇到零就把它移到末尾
            for(int i=0;i<nums.size();i++)
            {
                for(int j=1;j<nums.size()-i;j++)
                {
                    if(nums[j-1]==0)
                    {
                        int temp=nums[j];
                        nums[j]=nums[j-1];
                        nums[j-1]=temp;
                    }
                }
            }
        }
    };
    

选择排序

双重循环遍历数组,每经过一轮比较,找到最小元素的下标,将其交换至首位

#include <iostream>
#include <cstring>
#include <vector>
#include <map>
#include <cmath>
#include <set>
#include <string>
using namespace std;
class Solution {
public:
    void SelectSort(vector<int>& arr)
    {
        for (int i = 0; i < arr.size(); i++)
        {
            //存储最小的下标
            int indexMin = i;
            for (int j = i+1; j < arr.size(); j++)
            {
                if (arr[j] < arr[indexMin])
                    indexMin = j;
            }
            //找到最小元素的下标,将其交换至首位,也就是交换i下标对应的值和indexmin对应的值
            int temp = arr[i];
            arr[i] = arr[indexMin];
            arr[indexMin] = temp;
        }
   }
};
    
int main()
{
    Solution* solution = new Solution();
    vector<int> arr = { 7,2,4,5,1,6,9 };
    solution->SelectSort(arr);
    for (int i = 0; i < arr.size(); i++)
        cout << arr[i];    
    return 0;
}

数组中的第K个最大元素

给定整数数组 nums 和整数 k,请返回数组中第 **k** 个最大的元素。

请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
  • 思路:从0到k选择排序,找到第k大的数就停止

    class Solution {
    public:
        int findKthLargest(vector<int>& nums, int k) {
            for(int i=0;i<k;i++)
            {
            	//记录这一轮最大的数
                int maxIndex=i;
                for(int j=i+1;j<nums.size();j++)
                {
                    if(nums[j]>nums[maxIndex])
                        maxIndex=j;
                }
                //把这一轮最大的数和第i个数交换
                int temp=nums[i];
                nums[i]=nums[maxIndex];
                nums[maxIndex]=temp;
            }
            //返回k-1坐标的数也就是第k大的数
            return nums[k-1];
    
        }
    };
    

排序数组

给你一个整数数组 nums,请你将该数组升序排列。

  • 直接选择排序会超出时间限制

    class Solution {
    public:
        vector<int> sortArray(vector<int>& arr) {
            for (int i = 0; i < arr.size(); i++)
            {
                //存储最小的下标
                int indexMin = i;
                for (int j = i+1; j < arr.size(); j++)
                {
                    if (arr[j] < arr[indexMin])
                        indexMin = j;
                }
                //找到最小元素的下标,将其交换至首位,也就是交换i下标对应的值和indexmin对应的值
                int temp = arr[i];
                arr[i] = arr[indexMin];
                arr[indexMin] = temp;
            }
            return arr;
    
        }
    };
    
  • 快速排序

  • class Solution {
    public:
        vector<int> sortArray(vector<int>& arr) {
            
            sort(arr.begin(),arr.end());
            return arr;
    
        }
    };
    

插入排序

插入排序的思想非常简单,生活中有一个很常见的场景:在打扑克牌时,我们一边抓牌一边给扑克牌排序,每次摸一张牌,就将它插入手上已有的牌中合适的位置,逐渐完成整个排序。

插入排序有两种写法:

交换法:在新数字插入过程中,不断与前面的数字交换,直到找到自己合适的位置。
移动法:在新数字插入过程中,与前面的数字不断比较,前面的数字不断向后挪出位置,当新数字找到自己的位置后,插入一次即可。

作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/sort-algorithms/ev4tee/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

#include <iostream>
#include <cstring>
#include <vector>
#include <map>
#include <cmath>
#include <set>
#include <string>
using namespace std;
class Solution {
public:
    void InsertSort(vector<int>& arr)
    {
        //从第二个数组开始,依次插入到合适的位置上
        for (int i = 1; i < arr.size(); i++)
        {
            int insertIndex = 0;
            int num = arr[i];
            //找到插入的位置
            while (insertIndex<i&&  num> arr[insertIndex])
            {
                insertIndex++;
            }
            //从插入位置开始到i,整个数组往后移动
            for (int k = i; k > insertIndex; k--)
                arr[k] = arr[k-1];
            arr[insertIndex] = num;
        }
        
   }
};
    
int main()
{
    Solution* solution = new Solution();
    vector<int> arr = { 7,2,4,5,1,6,9 };
    solution->InsertSort(arr);
    for (int i = 0; i < arr.size(); i++)
        cout << arr[i];
    
    
    return 0;
}

对链表进行插入排序

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if(head==nullptr&&head->next==nullptr)
            return head;
        //定义一个新链表保存插入后的链表
        ListNode* res=new ListNode(0);
        res->next=new ListNode(head->val);
        //p1指向当前待插入的结点
        ListNode* p1=head->next;
        //p2指向插入的位置
        ListNode*p2=res->next; 
        //pre指向插入位置的前一个结点
        ListNode*pre=res;       
        while(p1)
        {
            int value=p1->val;
            p2=res->next;
            pre=res;
            while(p2&&(value>(p2->val)))
            {
                pre=p2;
                p2=p2->next;
            }
            //找到插入的位置之后,把val这个结点插到对应的位置上
            ListNode *newNode=new ListNode(p1->val);
            newNode->next=pre->next;
            pre->next=newNode;

            //指向下一个待插入的节点
            p1=p1->next;
        }
    
        return res->next;

    }
};

小结

本章我们介绍了三种基础排序算法:冒泡排序、选择排序、插入排序。

冒泡排序
冒泡排序有两种优化方式:

记录当前轮次是否发生过交换,没有发生过交换表示数组已经有序;
记录上次发生交换的位置,下一轮排序时只比较到此位置。
选择排序
选择排序可以演变为二元选择排序:

二元选择排序:一次遍历选出两个值——最大值和最小值;
二元选择排序剪枝优化:当某一轮遍历出现最大值和最小值相等,表示数组中剩余元素已经全部相等。
插入排序
插入排序有两种写法:

交换法:新数字通过不断交换找到自己合适的位置;
移动法:旧数字不断向后移动,直到新数字找到合适的位置。
相同点
时间复杂度都是 O(n^2) ,空间复杂度都是 O(1)。

都需要采用两重循环。

不同点
选择排序是不稳定的,冒泡排序、插入排序是稳定的;
在这三个排序算法中,选择排序交换的次数是最少的;
在数组几乎有序的情况下,插入排序的时间复杂度接近线性级别。

作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/sort-algorithms/oz4nzd/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

希尔排序

  • 将待排序数组按照一定的间隔分为多个子数组,每组分别进行插入排序。这里按照间隔分组指的不是取连续的一段数组,而是每跳跃一定间隔取一个值组成一组

  • 逐渐缩小间隔进行下一轮排序

  • 最后一轮时,取间隔为 1,也就相当于直接使用插入排序。但这时经过前面的「宏观调控」,数组已经基本有序了,所以此时的插入排序只需进行少量交换便可完成

作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/sort-algorithms/eu039h/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

堆排序

堆:符合以下两个条件之一的完全二叉树:

根节点的值 ≥ 子节点的值,这样的堆被称之为最大堆,或大顶堆;
根节点的值 ≤ 子节点的值,这样的堆被称之为最小堆,或小顶堆。

堆排序过程如下:

用数列构建出一个大顶堆,取出堆顶的数字;
调整剩余的数字,构建出新的大顶堆,再次取出堆顶的数字;
循环往复,完成整个排序。
整体的思路就是这么简单,我们需要解决的问题有两个:

如何用数列构建出一个大顶堆;
取出堆顶的数字后,如何将剩余的数字调整成新的大顶堆。
构建大顶堆 & 调整堆
构建大顶堆有两种方式:

方案一:从 0 开始,将每个数字依次插入堆中,一边插入,一边调整堆的结构,使其满足大顶堆的要求;
方案二:将整个数列的初始状态视作一棵完全二叉树,自底向上调整树的结构,使其满足大顶堆的要求。

作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/sort-algorithms/eu7ux3/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

最小的k个数

输入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。

作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/sort-algorithms/os5lwi/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

  • 选择排序实现
class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        //选择排序取前k个数
        vector<int>res;
        for(int i=0;i<k;i++)
        {
            int minIndex=i;
            for(int j=i+1;j<arr.size();j++)
                if(arr[j]<arr[minIndex])
                    minIndex=j;
            int temp=arr[i];
            arr[i]=arr[minIndex];
            arr[minIndex]=temp;
            //结果数组中加入这一轮最小的数
            res.push_back(arr[i]);
        }
        return res;

    }
};

快速排序

  • 其实快速排序就是一个挖坑填数+分治的过程

  • 该方法的基本思想是:

    • 1.先从数列中取出一个数作为基准数。
    • 2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
    • 3.再对左右区间重复第二步,直到各区间只有一个数。
    #include <iostream>
    #include <cstring>
    #include <vector>
    #include <map>
    #include <cmath>
    #include <set>
    #include <string>
    using namespace std;
    class Solution {
    public:
        //返回调整之后的中间值的坐标
        int adjustIndex(vector<int>& arr, int start, int end)
        {
            //先选择一个基数,保存在flag里面,这个时候这个基数所在的位置arr[i]就可以看作是一个待填的坑,
            //因为他的值被保存了,arr[i]这个位置就可以放别的值
            //我们最后的结果是要把比flag大的数放在flag的右边,比flag小的数放在flag的左边
            int flag = arr[start];
            int i = start, j = end;
            
            while (i < j)
            {
                //从基数的右边找到一个比flag小的数
                while (i<j && arr[j]>=flag)
                    j--;
                //把这个数填进坑arr[i]里
                if (i < j)
                {
                    arr[i] = arr[j];
                    i++;
                }
                    
                //这个时候arr[j]被保存了 arr[j]又成了新的坑
                //在左边找一个数填进arr[j]这个坑里
                while (i < j && arr[i] < flag)
                    i++;
                if (i < j)
                {
                    arr[j] = arr[i];
                    j--;
                }
                //填完之后arr[i]的值又被保存了,所以arr[i]的位置成了新的坑,继续找数来填
                    
    
            }
            //退出的时候i=j,这个时候把flag的值填进这个位置即可
            arr[i] = flag;
            return i;
    
    
        }
    
        void QuickSort(vector<int>& arr,int start,int end)
        {
            //如果左边的坐标已经大于等于右边的坐标,退出递归
            if (start >= end)
                return;
            int mid =  adjustIndex( arr, start, end);
            //对左半部分进行快排
            QuickSort(arr, start, mid - 1);
            QuickSort(arr, mid+1, end);              
       }
    };
        
    int main()
    {
        Solution* solution = new Solution();
        vector<int> arr = { 7,2,4,5,1,6,9 };
        solution->QuickSort(arr,0,arr.size()-1);
        for (int i = 0; i < arr.size(); i++)
            cout << arr[i];
        
        
        return 0;
    }
    
    



这篇关于leetcode刷题笔记_排序1的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程