排序算法

排序算法

复杂度为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();
    }

TAG:数据结构, 排序算法

发表新评论