[1]# 堆排序

基本思路

1. 借助平衡二叉树性质
2. 元素排列顺序的特殊性 进而形成 大顶堆和小顶堆
3. 逻辑思路 参考数据结构：堆 - 知乎 (zhihu.com)

简单代码实现

• 迭代生成

  void maxHeap(vector<int>&arr,int start,int end){
      int dad=start;  //父节点从0 开始
      int son=dad*2+1;
      while(son<=end){
          if(son+1<=end&&arr[son]<arr[son+1])++son;
          if(arr[dad]>arr[son]) return;
          else{
              swap(arr[dad],arr[son]);
              dad=son;
              son=dad*2+1;
          }
      }
  }

• 递归生成

  def maxHeap01(self,start, end):
          dad=start
          son=dad*2+1
          while son<=end:
              if son+1 <=end and self.ls[son]<self.ls[son+1]:son+=1
              if self.ls[dad]>self.ls[son]:return
              else:
                  self.ls[dad],self.ls[son]=self.ls[son],self.ls[dad]
                  dad=son
                  son=dad*2+1#dad的数值是比较小的

完整代码地址

地址

排序算法

复杂度为n方排序

冒泡算法

1. 是因为越小或越大的元素，会经过两两比较交换像泡泡一样升序或降序。
2. 冒牌算法主要是体现在两两交换之上 简单的交换排序
3. 冒泡排序动画演示
4. 具有稳定性
5. 但如果修改为左边大于等于右边的话 稳定性就可能会被破坏

核心代码实现

• Python

  def BubbleSort(nums):
      flag=True
      for i in range(len(nums)):
          if not flag:break
          flag=False
          for j in range(len(nums)-i-1):
              if nums[j]>nums[j+1]:
                  nums[j],nums[j+1]=nums[j+1],nums[j]
                  flag=True
      return nums

• C++

  void BubbleSort(vector<int>&nums)
  {
      bool flag=true;
      for(int i=0;i<nums.size();++i)
      {
          if (not flag)break;
          flag=false;
          for(int j=0;j<nums.size()-i-1;++j)
          {
              if(nums[j]>nums[j+1]) 
              {
                  swap(nums[j],nums[j+1]);
                  flag=true;
              }
          }
      }
  }

选择排序

1. 选择排序的思想是：双重循环遍历数组，每经过一轮比较，找到最小元素的下标，将其交换至首位。

2. 不稳定性

   • 交换顺序过程之中 可能会破坏稳定性

核心代码实现

• Python

  def SelectionSort(nums):
      for i in range(len(nums)-1):
          k=i
          for j in range(i+1,len(nums)):
              if nums[k]>nums[j]:k=j
          nums[i],nums[k]=nums[k],nums[i]
      return nums

• C++

  void SelectionSort(vector<int>&nums)
  {
      for(int i=0;i<nums.size()-1;++i)
      {
          int k=i;
          for(int j=i+1;j<nums.size();++j)
          {
              if(nums[j]<nums[k])k=j;
          }
          swap(nums[i],nums[k]);
      }
  }

二元选择排序

1. 先画个大饼 具体实现 在下面

插入排序

1. 简单描述

核心代码实现

• Python

  def InsertSort(nums):
      for i in range(1,len(nums)):
          k=i
          while k>=1 and nums[k]<nums[k-1]:
              nums[k],nums[k-1]=nums[k-1],nums[k]
              k-=1
      return nums

• C++

  void InsertSort(vector<int>&nums)
  {
      for (int i=1;i<nums.size();++i)
      {
          int k=i;
          while(k>=1&&nums[k]<nums[k-1])
          {
              swap(nums[k],nums[k-1]);
              --k;
          }
      }
  }

代码简单汇总

• Python

  
  class Sort():
      def __init__(self,nums) -> None:
          self.nums=nums
      #冒泡排序
      def BubbeSort(self):
          flag=True
          for i in range(len(self.nums)-1):
              if not flag:break
              flag=False
              for j in range(len(self.nums)-i-1):
                  if self.nums[j]>self.nums[j+1]:
                      self.nums[j],self.nums[j+1]=self.nums[j+1],self.nums[j]
                      flag=True
          return self.nums
      #选择排序
      def SelectionSort(self):
          for i in range(len(self.nums)-1):
              k=i
              for j in range(i+1,len(self.nums)):
                  if self.nums[j]<self.nums[k]:
                      k=j
              self.nums[k],self.nums[i]=self.nums[i],self.nums[k]
          return self.nums
      # 插入排序
      def InsertSort(self):
          for i in range(1,len(self.nums)):
              k=i
              while k>=1 and self.nums[k]<self.nums[k-1]:
                  self.nums[k],self.nums[k-1]=self.nums[k-1],self.nums[k]
                  k-=1
          return self.nums
  
      #希尔排序
      def ShellSort(self):
          dist=len(self.nums)
          while dist>0:
              for i in range(dist,len(self.nums)):
                  temp=self.nums[i]
                  k=i
                  while k>=dist and self.nums[k]<self.nums[k-dist]:
                      self.nums[k]=self.nums[k-dist]
                      k-=dist
                  self.nums[k]=temp
              dist//=2
          return nums
      # 快速排序
      def QuickSort(self):
          def quicksort(nums,i,j):
              if i>=j:return 
              low,high=i,j
              pivot=nums[low]
              while i<j:
                  while i<j and nums[j]>=pivot:j-=1
                  nums[i]=nums[j]
                  while i<j and nums[i]<=pivot:i+=1
                  nums[j]=nums[i]
              pivot=nums[j] 
              quicksort(nums,low,i-1)
              quicksort(nums,i+1,high)
          quicksort(self.nums,0,len(self.nums)-1)
          return nums
  
  if __name__=="__main__":
      nums = [6,8,3,2,9,1]
      s=Sort(nums)
      print(s.BubbeSort())
      print(s.SelectionSort())
      print(s.InsertSort())
      print(s.ShellSort())
      print(s.QuickSort())

• C++

  #include <iostream>
  #include <vector>
  using namespace std;
  
  class Sort
  {
  public:
      Sort(vector<int>&nums){
          this->nums=nums;
      }
      void BubbleSort();
      void InsertSort();
      void ShellSort();
      void QuickSort();
      void Print();
  public:
      vector<int>nums;
  };
  void quicksort(vector<int>&nums,int i,int j);
  void Sort::BubbleSort()
  {
      bool flag=true;
      for(int i=0;i<nums.size()-1;++i)
      {
          if(!flag) break;
          flag=false;
          for(int j=0;j<nums.size()-i-1;++j)
          {
              if(nums[j]>nums[j+1])
              {
                  swap(nums[j],nums[j+1]);
                  flag=true;
              }
          }
      }
  }
  void Sort::InsertSort()
  {
      for(int i=1;i<nums.size();++i)
      {
          int k=i;
          int temp=nums[i];
          while(k>=1&&nums[k]<nums[k-1])
          {
              swap(nums[k],nums[k-1]);
              --k;
          }
          nums[k]=temp;
      }
  }
  void Sort::ShellSort()
  {
      for(int gap=nums.size()/2;gap>0;gap/=2)
      {
          for(int i=gap;i<nums.size();++i)
          {
              int temp=nums[i];
              int j=i;
              while(j>=gap&&temp<nums[j-1])
              {
                  nums[j]=nums[j-1];
                  j-=gap;
              }
              nums[j]=temp;
          }
      }
  }
  void quicksort(vector<int>&nums,int i,int j)
  {
      if(i>=j) return ;
      int low=i,high=j;
      int pivot=nums[i];
      while(i<j)
      {
          while(i<j&&nums[j]>=pivot)--j;
          nums[i]=nums[j];
          while(i<j&&nums[i]<=pivot)++i;
          nums[j]=nums[i];
      }
      nums[j]=pivot;
      quicksort(nums,low,i-1);
      quicksort(nums,i+1,high);
  }
  void Sort::QuickSort()
  {
      quicksort(nums,0,nums.size()-1);
  }
  void Sort::Print()
  {
      for(auto&x:nums) cout<<x<<" ";
      cout<<endl;
  }
  int main()
  {
      vector<int>nums{6,8,3,2,9,1};
      Sort s(nums);
      s.BubbleSort();
      s.InsertSort();
      s.QuickSort();
      s.ShellSort();
      s.Print();
  }

如果您看到这篇文章,表示您的 blog 已经安装成功.