内射老阿姨1区2区3区4区_久久精品人人做人人爽电影蜜月_久久国产精品亚洲77777_99精品又大又爽又粗少妇毛片

十大排序（總結(jié)+算法實現(xiàn)）-創(chuàng)新互聯(lián)

十大排序（總結(jié)+算法實現(xiàn)） 十大排隊的性能分析

在這里插入圖片描述

為虎林等地區(qū)用戶提供了全套網(wǎng)頁設計制作服務，及虎林網(wǎng)站建設行業(yè)解決方案。主營業(yè)務為成都網(wǎng)站設計、成都做網(wǎng)站、虎林網(wǎng)站設計，以傳統(tǒng)方式定制建設網(wǎng)站，并提供域名空間備案等一條龍服務，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠的服務。我們深信只要達到每一位用戶的要求，就會得到認可，從而選擇與我們長期合作。這樣，我們也可以走得更遠！冒泡排序

使用冒泡排序，時間復雜度為O(n^2),空間復雜度為O(1)

像氣泡一樣從低往上浮現(xiàn)

vectorbubbleSort(vectornums)
{int length=nums.size();
    for(int i=0;ifor(int j=length-2;j>=i;j--)
        {if(nums[j]>nums[j+1])
            {int temp=nums[j+1];
                nums[j+1]=nums[j];
                nums[j]=temp;
            }
        }
    }
    return nums;
}
選擇排序

使用選擇排序，時間復雜度為O(n^2),空間復雜度為O(1)。尋找關鍵字最小的坐標

vectorselectSort(vectornums)
{int length=nums.size();
    int minPos=INT_MIN;
    for(int i=0;iminPos=i;
        for(int j=i+1;jminPos=nums[j]
插入排序

使用插入排序，時間復雜度為O(n^2),空間復雜度O(1)

vectorinsertSort(vectornums)
{int length=nums.size();
    for(int i=0;i//當找到滿足非遞增的數(shù)組時，進行處理
        int temp=nums[i+1];
        int preIndex=i;
        while(preIndex>=0&&nums[preIndex]>temp)
        {//數(shù)組往后挪，直到找到第一個小于該值的值
            nums[preIndex+1]=nums[preIndex];
            preIndex--;
        }
        nums[preIndex+1]=temp;
        
    }
    return nums;
}
希爾排序

使用希爾排序進行實現(xiàn)，平均時間復雜度為O(nlogn)，空間復雜度為O(1)

希爾排序是在插入排序的基礎上進行改進的算法

先將序列劃分成大區(qū)間，先對每一個區(qū)間進行排序，使后一個區(qū)間里的所有對應位置的值都大于前一個區(qū)間所有對應位置的值

然后不斷循環(huán)，直到最后大區(qū)間全部都變成了小區(qū)間，則此時代表已經(jīng)排號序了

vectorshellSort(vectornums)
{int length=nums.size();
    int gap=length>>1;
    int temp;
    while(gap)
    {//類似插入排序
        //i從第二個區(qū)間開始的
        for(int i=gap;itemp=nums[i];
            int preIndex=i-gap;
             
            while(preIndex>=0&&nums[preIndex]>temp)
            {nums[preIndex+gap]=nums[preIndex];
                preIndex-=gap;
            }
            nums[preIndex+gap]=temp;
        }
        gap=gap>>1;
    }
    return nums;
}
歸并排序

歸并排序，平均時間復雜度O(nlogn)，空間復雜度O(n)

//歸并排序，平均時間復雜度O(nlogn)，空間復雜度O(n)
//使用遞歸實現(xiàn)歸并排序
vectormergeSort(vectornums)
{mSort(nums,0,nums.size()-1);
    return nums;
}

//在[left,right]這個區(qū)間中進行歸并排序，整個nums經(jīng)過整個函數(shù)后就是一個有序數(shù)組
//使用回溯的思想
void mSort(vector&nums,int left,int right)
{//定義遞歸終止條件
    if(left>=right)
    {return;
    }
    //防止位溢出
    int mid=left+((right-left)>>1);
    //回溯
    mSort(nums,left,mid);
    mSort(nums,mid+1,right);
    merge(nums,left,mid,right);
}


void merge(vector&nums,int left,int mid,int right)
{//創(chuàng)建一個臨時數(shù)組用以保存合并排序之后的數(shù)組,并把這個區(qū)間的值賦給其
    vectortempArr(nums.begin()+left,nums.begin()+right+1);
    
    //合并兩個區(qū)間，i代表左邊開始索引，j代表右邊開始索引
    int i=left;
    int j=mid+1;

    for(int k=left;k<=right;k++)
    {//代表左邊已經(jīng)處理完畢，將右邊的直接替代即可
        if(i>mid)
        {nums[k]=tempArr[j-left];
            j++;
        }
        //代表右邊已經(jīng)處理完畢，將左側(cè)區(qū)間的值直接拷貝到原數(shù)組即可
        else if(j>right)
        {nums[k]=tempArr[i-left];
            i++;
        }
        //兩邊都未處理完畢，則比較二者大小，將元素中較小的元素放在左邊
        else if(tempArr[i-left]<=tempArr[j-left]){nums[k]=tempArr[i-left];
            i++;
        }
        else
        {nums[k]=tempArr[j-left];
            j++;
        }
    }
}
快速排序

平均時間復雜度為O(nlogn)，最壞平均復雜度為O(n^2),空間復雜度O(logn)

vectorquickSort(vectornums)
{qSort(nums,0,nums.size()-1);
    return nums;
}


void qSort(vector&nums,int left,int right)
{//定義遞歸終止條件
    if(left>=right)
    {return;
    }

    //設置樞軸
    int pivot=partition(nums,left,right);
    //遞歸實現(xiàn)
    qSort(nums,left,pivot-1);
    qSort(nums,pivot+1,right);
}

int partition(vector&nums,int left,int right)
{int pivot=nums[left];
    int j=left;

    for(int i=left+1;i<=right;i++)
    {//大放過小交換
        if(nums[i]j++;
            swap(nums,i,j);
        }
    }
    swap(nums,left,j);
    return j;
}

void swap(vector&nums,int index1,int index2)
{int temp=nums[index1];
    nums[index1]=nums[index2];
    nums[index2]=temp;
}
堆排序

堆排序，算法平均時間復雜度為O(nlogn),空間復雜度O(1)

vectorheapSort(vectornums)
{//首先構(gòu)建一個大堆
    for(int i=nums.size()/2-1;i>=0;--i)
    {heapAdjust(nums,i,nums.size());
    }

//從大堆中逆序得到遞增序列
    for(int i=nums.size()-1;i>=0;--i)
    {swap(nums,0,i);
        heapAdjust(nums,0,i);
    }
    return nums;

}

void heapAdjust(vector&nums,int i,int length)
{int max=i;
    //構(gòu)建左右結(jié)點
    int lChild=i*2+1;
    int rChild=i*2+2;

    if(lChildnums[max])
    {max=lChild;
    }
    if(rChildnums[max])
    {max=rChild;
    }
    if(max!=i)
    {swap(nums,i,max);
        heapAdjust(nums,max,length);
    }
}
計數(shù)排序

計數(shù)排序，時間復雜度O(n+k),空間復雜度O(k)

vectorcountSort(vectornums)
{int maxVal=nums[max_element(nums.begin(),nums.end())-nums.begin()];
   int minVal=nums[min_element(nums.begin(),nums.end())-nums.begin()];
   //數(shù)值作為索引，個數(shù)作為值
   vectorcount(maxVal,0);

   vectortemp(nums);
//數(shù)字需要減去1才能實現(xiàn)
   for(int i=0;i++count[nums[i]-1];
   }

   nums.clear();

   for(int i=0;ifor(int j=0;jnums.push_back(i+1);
        }
   }
   return nums;
}

vectorcountSort2(vectornums)
{int maxVal=nums[max_element(nums.begin(),nums.end())-nums.begin()];
   int minVal=nums[min_element(nums.begin(),nums.end())-nums.begin()];
   //數(shù)值作為索引，個數(shù)作為值
   vectorcount(maxVal-minVal+1,0);
    int bias=0-minVal;
   for(int i=0;i++count[nums[i]+bias];
   }

    int index=0,i=0;
    while(indexif(count[i]!=0)
        {nums[index]=i-bias;
            count[i]--;
            index++;
        }
        else{i++;
        }
    }

   return nums;
}
桶排序

平均時間復雜度為O(n+k),空間復雜度為O(n+k)

//桶排序  平均時間復雜度為O(n+k),空間復雜度為O(n+k)
//設置總共有5個桶
vectorbucketSort(vectornums)
{int maxVal=nums[max_element(nums.begin(),nums.end())-nums.begin()];
   int minVal=nums[min_element(nums.begin(),nums.end())-nums.begin()];

   //設置桶的大小
   int bucketSize=5;
   //設置桶的數(shù)目
   int bucketCount=(maxVal-minVal)/bucketSize+1;

   vector>buckets(bucketCount,vector());

    //利用映射函數(shù)將數(shù)據(jù)分配到每個桶中
    for(int i=0;ibuckets[(nums[i]-minVal)/bucketSize].push_back(nums[i]);
    }

    int index=0;
    for(int i=0;i//對每個桶的內(nèi)部函數(shù)進行排序
        //調(diào)用之前寫的排序算法
        buckets[i]=quickSort(buckets[i]);
    //取出每個桶中的元素
        for(int j=0;jnums[index++]=buckets[i][j];
        }
    }
    return nums;
}
基數(shù)排序

平均時間復雜度為O(n*k),空間復雜度為O(n+k)

//基數(shù)排序，平均時間復雜度為O(n*k),空間復雜度為O(n+k)
//按位對應的數(shù)，從高位開始依次比較，進行排序

vectorradixSort(vectornums)
{int length=nums.size();
    int bits=maxBit(nums);

    //設置數(shù)組保存從0~9的數(shù)字
   
    int radix=1;
    for(int i=0;i<=bits;i++)
    {//獲取更新的數(shù)組
        vectornewArray(length);
        //根據(jù)最后一位數(shù)字的值保存排序數(shù)組
        vectorcount=vector(10,0);

        for(int j=0;jint temp=(nums[j]/radix)%10;
            count[temp]++;
        }

        //計算前綴和，判斷前面由于個位數(shù)不存在的值
        for(int j=1;j<10;j++)
        {count[j]+=count[j-1];
        }
//指定更新陣列的新位置，count[temp]--則是用來判斷這個位置是否到位
        for(int j=length-1;j>=0;j--)
        {int temp=(nums[j]/radix)%10;
            newArray[count[temp]-1]=nums[j];
            count[temp]--;
        }

        nums=newArray;
        radix*=10;
    }
    return nums;


}

//獲取數(shù)組中大值的位數(shù)
int maxBit(vectornums)
{int maxVal=nums[max_element(nums.begin(),nums.end())-nums.begin()];
    int d=0;
    // int p=10;
    while(maxVal>0)
    {maxVal/=10;
        ++d;
    }
    return d;
}
全部測試代碼
#include#include#include
#includeusing namespace std;

void mSort(vector&nums,int left,int right);
void merge(vector&nums,int left,int mid,int right);
void qSort(vector&nums,int left,int right);
int partition(vector&nums,int left,int right);
void swap(vector&nums,int index1,int index2);
void heapAdjust(vector&nums,int i,int length);
int maxBit(vectornums);

//使用冒泡排序，時間復雜度為O(n^2),空間復雜度為O(1)
//像氣泡一樣從低往上浮現(xiàn)
vectorbubbleSort(vectornums)
{int length=nums.size();
    for(int i=0;ifor(int j=length-2;j>=i;j--)
        {if(nums[j]>nums[j+1])
            {int temp=nums[j+1];
                nums[j+1]=nums[j];
                nums[j]=temp;
            }
        }
    }
    return nums;
}


//使用選擇排序，時間復雜度為O(n^2),空間復雜度為O(1)
//尋找到關鍵字最小的坐標
vectorselectSort(vectornums)
{int length=nums.size();
    int minPos=INT_MIN;
    for(int i=0;iminPos=i;
        for(int j=i+1;jminPos=nums[j]insertSort(vectornums)
{int length=nums.size();
    for(int i=0;i//當找到滿足非遞增的數(shù)組時，進行處理
        int temp=nums[i+1];
        int preIndex=i;
        while(preIndex>=0&&nums[preIndex]>temp)
        {//數(shù)組往后挪，直到找到第一個小于該值的值
            nums[preIndex+1]=nums[preIndex];
            preIndex--;
        }
        nums[preIndex+1]=temp;
        
    }
    return nums;
}

//使用希爾排序進行實現(xiàn)，平均時間復雜度為O(nlogn)，空間復雜度為O(1)
//希爾排序是在插入排序的基礎上進行改進的算法
//先將序列劃分成大區(qū)間，先對每一個區(qū)間進行排序，使后一個區(qū)間里的所有對應位置的值都大于前一個區(qū)間所有對應位置的值‘
//然后不斷循環(huán)，直到最后大區(qū)間全部都變成了小區(qū)間，則此時代表已經(jīng)排號序了
vectorshellSort(vectornums)
{int length=nums.size();
    int gap=length>>1;
    int temp;
    while(gap)
    {//類似插入排序
        //i從第二個區(qū)間開始的
        for(int i=gap;itemp=nums[i];
            int preIndex=i-gap;
             
            while(preIndex>=0&&nums[preIndex]>temp)
            {nums[preIndex+gap]=nums[preIndex];
                preIndex-=gap;
            }
            nums[preIndex+gap]=temp;
        }
        gap=gap>>1;
    }
    return nums;
}

//歸并排序，平均時間復雜度O(nlogn)，空間復雜度O(n)
//使用遞歸實現(xiàn)歸并排序
vectormergeSort(vectornums)
{mSort(nums,0,nums.size()-1);
    return nums;
}

//在[left,right]這個區(qū)間中進行歸并排序，整個nums經(jīng)過整個函數(shù)后就是一個有序數(shù)組
//使用回溯的思想
void mSort(vector&nums,int left,int right)
{//定義遞歸終止條件
    if(left>=right)
    {return;
    }
    //防止位溢出
    int mid=left+((right-left)>>1);
    //回溯
    mSort(nums,left,mid);
    mSort(nums,mid+1,right);
    merge(nums,left,mid,right);
}


void merge(vector&nums,int left,int mid,int right)
{//創(chuàng)建一個臨時數(shù)組用以保存合并排序之后的數(shù)組,并把這個區(qū)間的值賦給其
    vectortempArr(nums.begin()+left,nums.begin()+right+1);
    
    //合并兩個區(qū)間，i代表左邊開始索引，j代表右邊開始索引
    int i=left;
    int j=mid+1;

    for(int k=left;k<=right;k++)
    {//代表左邊已經(jīng)處理完畢，將右邊的直接替代即可
        if(i>mid)
        {nums[k]=tempArr[j-left];
            j++;
        }
        //代表右邊已經(jīng)處理完畢，將左側(cè)區(qū)間的值直接拷貝到原數(shù)組即可
        else if(j>right)
        {nums[k]=tempArr[i-left];
            i++;
        }
        //兩邊都未處理完畢，則比較二者大小，將元素中較小的元素放在左邊
        else if(tempArr[i-left]<=tempArr[j-left]){nums[k]=tempArr[i-left];
            i++;
        }
        else
        {nums[k]=tempArr[j-left];
            j++;
        }
    }
}



//快速排序：平均時間復雜度為O(nlogn)，最壞平均復雜度為O(n^2),空間復雜度O(logn)
vectorquickSort(vectornums)
{qSort(nums,0,nums.size()-1);
    return nums;
}


void qSort(vector&nums,int left,int right)
{//定義遞歸終止條件
    if(left>=right)
    {return;
    }

    //設置樞軸
    int pivot=partition(nums,left,right);
    //遞歸實現(xiàn)
    qSort(nums,left,pivot-1);
    qSort(nums,pivot+1,right);
}

int partition(vector&nums,int left,int right)
{int pivot=nums[left];
    int j=left;

    for(int i=left+1;i<=right;i++)
    {//大放過小交換
        if(nums[i]j++;
            swap(nums,i,j);
        }
    }
    swap(nums,left,j);
    return j;
}

void swap(vector&nums,int index1,int index2)
{int temp=nums[index1];
    nums[index1]=nums[index2];
    nums[index2]=temp;
}


//堆排序，算法平均時間復雜度為O(nlogn),空間復雜度O(1)
vectorheapSort(vectornums)
{//首先構(gòu)建一個大堆
    for(int i=nums.size()/2-1;i>=0;--i)
    {heapAdjust(nums,i,nums.size());
    }

//從大堆中逆序得到遞增序列
    for(int i=nums.size()-1;i>=0;--i)
    {swap(nums,0,i);
        heapAdjust(nums,0,i);
    }
    return nums;

}

void heapAdjust(vector&nums,int i,int length)
{int max=i;
    //構(gòu)建左右結(jié)點
    int lChild=i*2+1;
    int rChild=i*2+2;

    if(lChildnums[max])
    {max=lChild;
    }
    if(rChildnums[max])
    {max=rChild;
    }
    if(max!=i)
    {swap(nums,i,max);
        heapAdjust(nums,max,length);
    }
}


//計數(shù)排序，時間復雜度O(n+k),空間復雜度O(k)
vectorcountSort(vectornums)
{int maxVal=nums[max_element(nums.begin(),nums.end())-nums.begin()];
   int minVal=nums[min_element(nums.begin(),nums.end())-nums.begin()];
   //數(shù)值作為索引，個數(shù)作為值
   vectorcount(maxVal,0);

   vectortemp(nums);
//數(shù)字需要減去1才能實現(xiàn)
   for(int i=0;i++count[nums[i]-1];
   }

   nums.clear();

   for(int i=0;ifor(int j=0;jnums.push_back(i+1);
        }
   }
   return nums;
}


//計數(shù)排序，時間復雜度O(n+k),空間復雜度O(k)
//優(yōu)化空間
vectorcountSort2(vectornums)
{int maxVal=nums[max_element(nums.begin(),nums.end())-nums.begin()];
   int minVal=nums[min_element(nums.begin(),nums.end())-nums.begin()];
   //數(shù)值作為索引，個數(shù)作為值
   vectorcount(maxVal-minVal+1,0);
    int bias=0-minVal;
   for(int i=0;i++count[nums[i]+bias];
   }

    int index=0,i=0;
    while(indexif(count[i]!=0)
        {nums[index]=i-bias;
            count[i]--;
            index++;
        }
        else{i++;
        }
    }

   return nums;
}


//桶排序  平均時間復雜度為O(n+k),空間復雜度為O(n+k)
//設置總共有5個桶
vectorbucketSort(vectornums)
{int maxVal=nums[max_element(nums.begin(),nums.end())-nums.begin()];
   int minVal=nums[min_element(nums.begin(),nums.end())-nums.begin()];

   //設置桶的大小
   int bucketSize=5;
   //設置桶的數(shù)目
   int bucketCount=(maxVal-minVal)/bucketSize+1;

   vector>buckets(bucketCount,vector());

    //利用映射函數(shù)將數(shù)據(jù)分配到每個桶中
    for(int i=0;ibuckets[(nums[i]-minVal)/bucketSize].push_back(nums[i]);
    }

    int index=0;
    for(int i=0;i//對每個桶的內(nèi)部函數(shù)進行排序
        //調(diào)用之前寫的排序算法
        buckets[i]=quickSort(buckets[i]);
    //取出每個桶中的元素
        for(int j=0;jnums[index++]=buckets[i][j];
        }
    }
    return nums;
}


//基數(shù)排序，平均時間復雜度為O(n*k),空間復雜度為O(n+k)
//按位對應的數(shù)，從高位開始依次比較，進行排序

vectorradixSort(vectornums)
{int length=nums.size();
    int bits=maxBit(nums);

    //設置數(shù)組保存從0~9的數(shù)字
   
    int radix=1;
    for(int i=0;i<=bits;i++)
    {//獲取更新的數(shù)組
        vectornewArray(length);
        //根據(jù)最后一位數(shù)字的值保存排序數(shù)組
        vectorcount=vector(10,0);

        for(int j=0;jint temp=(nums[j]/radix)%10;
            count[temp]++;
        }

        //計算前綴和，判斷前面由于個位數(shù)不存在的值
        for(int j=1;j<10;j++)
        {count[j]+=count[j-1];
        }
//指定更新陣列的新位置，count[temp]--則是用來判斷這個位置是否到位
        for(int j=length-1;j>=0;j--)
        {int temp=(nums[j]/radix)%10;
            newArray[count[temp]-1]=nums[j];
            count[temp]--;
        }

        nums=newArray;
        radix*=10;
    }
    return nums;


}

//獲取數(shù)組中大值的位數(shù)
int maxBit(vectornums)
{int maxVal=nums[max_element(nums.begin(),nums.end())-nums.begin()];
    int d=0;
    // int p=10;
    while(maxVal>0)
    {maxVal/=10;
        ++d;
    }
    return d;
}




int main()
{vectornums={9,9,2,18,3,7,34,356,5};

    vectorres=bubbleSort(nums);
    cout<<"冒泡排序的結(jié)果為:";
    for(int i:res)
    {cout<cout<cout<cout<cout<cout<cout<cout<cout<cout<

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站欄目：十大排序（總結(jié)+算法實現(xiàn)）-創(chuàng)新互聯(lián)
文章轉(zhuǎn)載：http://www.rwnh.cn/article14/cojege.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)頁設計公司、品牌網(wǎng)站建設、虛擬主機、自適應網(wǎng)站、網(wǎng)站收錄、ChatGPT

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

千阳县| 进贤县| 吉首市| 海口市| 满城县| 醴陵市| 镇康县| 铁力市| 济南市| 香格里拉县| 镇坪县| 延津县| 宝鸡市| 都安| 寿宁县| 堆龙德庆县| 滨州市| 焦作市| 桑植县| 平陆县| 禄丰县| 河东区| 德安县| 富宁县| 山丹县| 长顺县| 曲周县| 板桥市| 宝丰县| 宜川县| 呈贡县| 平定县| 高淳县| 宣威市| 彭州市| 上林县| 红河县| 静宁县| 巩留县| 宝丰县| 稻城县|