本文主要是介绍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的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！