排序算法原理以及实现

﹏ヽ暗。殇╰゛Y 2022-05-09 05:18 200阅读 0赞

# 1.冒泡排序算法 #

# 2.插入排序算法 #

/*
     * 1.第一个元素开始，假设第一个元素已排序
     * 2.取下一个元素temp_val，在已排序的区间从后往前扫描，如果大于temp_val，则往后移
     * 3.直到小于的时候，将其后一位置为temp_val即可
     * 4.重复n-1次2、3步骤
     */
    //三个参数目的是为了，排序某个区间
    void insertion_sort(vector<int> array, int first,int last)
    {
        int j; 
        int temp_val;    //取出来的未排序排序数
        for(int i = first+1; i<=last; i++)    //未排序数遍历
        {
            temp_val = array[i];        
            j = i-1;                          //已排序数的最后一个
            while(j>=0 && array[j]>temp_val)  //已排序未越界且未排序数大于temp_val
            {
                array[j+1] = array[i];        //后移
                j--;                          //往前扫描
            }
            array[j+1] = temp_val;            //到已排序小于temp_val，则下一位为tem_val的位置
        }
    }

**二分插入排序**

/*
     * 1.第一个元素开始，假设第一个元素已排序
     * 2.取下一个元素temp_val，在已排序的区间二分查找，如果mid的值大于等于temp_val，则right=mid，反之left = mid
     * 3.直到right<left的时候，确定mid位置，插入mid，之后后移并插入
     */
    //三个参数目的是为了，排序某个区间
    void insertion_sort(vector<int> array, int first,int last)
    {
        int left,mid,right; 
        int temp_val;    //取出来的未排序排序数
        for(int i = first+1; i<=last; i++)    //未排序数遍历
        {
            temp_val = array[i];        
            left = 0;                          //已排序数的二分左端
            right = 0;                          //已排序数的二分右端
    
            //二分查找精髓，确定要插入位置,最后位置在left(mid)上
            while(left<=right)  //已排序未越界且未排序数大于temp_val
            {
                mid = (left + right)/2;
                if(array[mid]>=temp_val)
                    right = mid-1;
                else
                    left = mid+1;
            }
            
    
            //后移,为temp_val腾出空间
            for(int j = i-1; j>left; j--)
                array[j+1] = array[j];
            array[left] = temp_val;            //到已排序小于temp_val，则下一位为tem_val的位置
        }
    }

# 3.希尔排序 #

# 4.选择排序 #

# 5.冒泡排序 #

# 6.鸡尾酒排序/双向冒泡 #

# 7.快速排序 #

void quick_sort(vector<int> array, int left, int right)  
    {
        int i,j,temp_val;
        if(left > right)
            return ;
        
        temp_val = array[0];    //选取基准
        i = left;    //左向右扫描
        j = right;    //右向左扫描
        while(i!=j)
        {    
            //最开始从右向左扫描，必须先从右开始
            while((array[j] >= temp_val) && i <j)    //找到第一个大于temp_val的值
                j--;
            while((array[i] <= temp_val) && i<j)    //找到第一个小于temp_val的值
                i++;
            if(i<j)    //交换位置
            {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
                
        }
        array[left] = a[i];    //将最中间的数值与基准交换位置
        array[i] = temp;
    
    
        quick_sort(array, left, i-1);     //对标准值左半部递归调用本函数  
        quick_sort(array, i+1, right);    //对标准值右半部递归调用本函数  
      }  
    }

# 8.堆排序 #