堆排序

基本思路

  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();
}