使用冒泡排序,時(shí)間復(fù)雜度為O(n^2),空間復(fù)雜度為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;
}
選擇排序使用選擇排序,時(shí)間復(fù)雜度為O(n^2),空間復(fù)雜度為O(1)。尋找關(guān)鍵字最小的坐標(biāo)
vectorselectSort(vectornums)
{int length=nums.size();
int minPos=INT_MIN;
for(int i=0;iminPos=i;
for(int j=i+1;jminPos=nums[j]
插入排序使用插入排序,時(shí)間復(fù)雜度為O(n^2),空間復(fù)雜度O(1)
vectorinsertSort(vectornums)
{int length=nums.size();
for(int i=0;i//當(dāng)找到滿足非遞增的數(shù)組時(shí),進(jìn)行處理
int temp=nums[i+1];
int preIndex=i;
while(preIndex>=0&&nums[preIndex]>temp)
{//數(shù)組往后挪,直到找到第一個(gè)小于該值的值
nums[preIndex+1]=nums[preIndex];
preIndex--;
}
nums[preIndex+1]=temp;
}
return nums;
}
希爾排序使用希爾排序進(jìn)行實(shí)現(xiàn),平均時(shí)間復(fù)雜度為O(nlogn),空間復(fù)雜度為O(1)
希爾排序是在插入排序的基礎(chǔ)上進(jìn)行改進(jìn)的算法
先將序列劃分成大區(qū)間,先對每一個(gè)區(qū)間進(jìn)行排序,使后一個(gè)區(qū)間里的所有對應(yīng)位置的值都大于前一個(gè)區(qū)間所有對應(yīng)位置的值
然后不斷循環(huán),直到最后大區(qū)間全部都變成了小區(qū)間,則此時(shí)代表已經(jīng)排號(hào)序了
vectorshellSort(vectornums)
{int length=nums.size();
int gap=length>>1;
int temp;
while(gap)
{//類似插入排序
//i從第二個(gè)區(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;
}
歸并排序歸并排序,平均時(shí)間復(fù)雜度O(nlogn),空間復(fù)雜度O(n)
//歸并排序,平均時(shí)間復(fù)雜度O(nlogn),空間復(fù)雜度O(n)
//使用遞歸實(shí)現(xiàn)歸并排序
vectormergeSort(vectornums)
{mSort(nums,0,nums.size()-1);
return nums;
}
//在[left,right]這個(gè)區(qū)間中進(jìn)行歸并排序,整個(gè)nums經(jīng)過整個(gè)函數(shù)后就是一個(gè)有序數(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)建一個(gè)臨時(shí)數(shù)組用以保存合并排序之后的數(shù)組,并把這個(gè)區(qū)間的值賦給其
vectortempArr(nums.begin()+left,nums.begin()+right+1);
//合并兩個(gè)區(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++;
}
}
}
快速排序平均時(shí)間復(fù)雜度為O(nlogn),最壞平均復(fù)雜度為O(n^2),空間復(fù)雜度O(logn)
vectorquickSort(vectornums)
{qSort(nums,0,nums.size()-1);
return nums;
}
void qSort(vector&nums,int left,int right)
{//定義遞歸終止條件
if(left>=right)
{return;
}
//設(shè)置樞軸
int pivot=partition(nums,left,right);
//遞歸實(shí)現(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;
}
堆排序堆排序,算法平均時(shí)間復(fù)雜度為O(nlogn),空間復(fù)雜度O(1)
vectorheapSort(vectornums)
{//首先構(gòu)建一個(gè)大堆
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é)點(diǎn)
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);
}
}
計(jì)數(shù)排序計(jì)數(shù)排序,時(shí)間復(fù)雜度O(n+k),空間復(fù)雜度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ù)值作為索引,個(gè)數(shù)作為值
vectorcount(maxVal,0);
vectortemp(nums);
//數(shù)字需要減去1才能實(shí)現(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ù)值作為索引,個(gè)數(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;
}
桶排序平均時(shí)間復(fù)雜度為O(n+k),空間復(fù)雜度為O(n+k)
//桶排序 平均時(shí)間復(fù)雜度為O(n+k),空間復(fù)雜度為O(n+k)
//設(shè)置總共有5個(gè)桶
vectorbucketSort(vectornums)
{int maxVal=nums[max_element(nums.begin(),nums.end())-nums.begin()];
int minVal=nums[min_element(nums.begin(),nums.end())-nums.begin()];
//設(shè)置桶的大小
int bucketSize=5;
//設(shè)置桶的數(shù)目
int bucketCount=(maxVal-minVal)/bucketSize+1;
vector>buckets(bucketCount,vector());
//利用映射函數(shù)將數(shù)據(jù)分配到每個(gè)桶中
for(int i=0;ibuckets[(nums[i]-minVal)/bucketSize].push_back(nums[i]);
}
int index=0;
for(int i=0;i//對每個(gè)桶的內(nèi)部函數(shù)進(jìn)行排序
//調(diào)用之前寫的排序算法
buckets[i]=quickSort(buckets[i]);
//取出每個(gè)桶中的元素
for(int j=0;jnums[index++]=buckets[i][j];
}
}
return nums;
}
基數(shù)排序平均時(shí)間復(fù)雜度為O(n*k),空間復(fù)雜度為O(n+k)
//基數(shù)排序,平均時(shí)間復(fù)雜度為O(n*k),空間復(fù)雜度為O(n+k)
//按位對應(yīng)的數(shù),從高位開始依次比較,進(jìn)行排序
vectorradixSort(vectornums)
{int length=nums.size();
int bits=maxBit(nums);
//設(shè)置數(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]++;
}
//計(jì)算前綴和,判斷前面由于個(gè)位數(shù)不存在的值
for(int j=1;j<10;j++)
{count[j]+=count[j-1];
}
//指定更新陣列的新位置,count[temp]--則是用來判斷這個(gè)位置是否到位
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);
//使用冒泡排序,時(shí)間復(fù)雜度為O(n^2),空間復(fù)雜度為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;
}
//使用選擇排序,時(shí)間復(fù)雜度為O(n^2),空間復(fù)雜度為O(1)
//尋找到關(guān)鍵字最小的坐標(biāo)
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//當(dāng)找到滿足非遞增的數(shù)組時(shí),進(jìn)行處理
int temp=nums[i+1];
int preIndex=i;
while(preIndex>=0&&nums[preIndex]>temp)
{//數(shù)組往后挪,直到找到第一個(gè)小于該值的值
nums[preIndex+1]=nums[preIndex];
preIndex--;
}
nums[preIndex+1]=temp;
}
return nums;
}
//使用希爾排序進(jìn)行實(shí)現(xiàn),平均時(shí)間復(fù)雜度為O(nlogn),空間復(fù)雜度為O(1)
//希爾排序是在插入排序的基礎(chǔ)上進(jìn)行改進(jìn)的算法
//先將序列劃分成大區(qū)間,先對每一個(gè)區(qū)間進(jìn)行排序,使后一個(gè)區(qū)間里的所有對應(yīng)位置的值都大于前一個(gè)區(qū)間所有對應(yīng)位置的值‘
//然后不斷循環(huán),直到最后大區(qū)間全部都變成了小區(qū)間,則此時(shí)代表已經(jīng)排號(hào)序了
vectorshellSort(vectornums)
{int length=nums.size();
int gap=length>>1;
int temp;
while(gap)
{//類似插入排序
//i從第二個(gè)區(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;
}
//歸并排序,平均時(shí)間復(fù)雜度O(nlogn),空間復(fù)雜度O(n)
//使用遞歸實(shí)現(xiàn)歸并排序
vectormergeSort(vectornums)
{mSort(nums,0,nums.size()-1);
return nums;
}
//在[left,right]這個(gè)區(qū)間中進(jìn)行歸并排序,整個(gè)nums經(jīng)過整個(gè)函數(shù)后就是一個(gè)有序數(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)建一個(gè)臨時(shí)數(shù)組用以保存合并排序之后的數(shù)組,并把這個(gè)區(qū)間的值賦給其
vectortempArr(nums.begin()+left,nums.begin()+right+1);
//合并兩個(gè)區(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++;
}
}
}
//快速排序:平均時(shí)間復(fù)雜度為O(nlogn),最壞平均復(fù)雜度為O(n^2),空間復(fù)雜度O(logn)
vectorquickSort(vectornums)
{qSort(nums,0,nums.size()-1);
return nums;
}
void qSort(vector&nums,int left,int right)
{//定義遞歸終止條件
if(left>=right)
{return;
}
//設(shè)置樞軸
int pivot=partition(nums,left,right);
//遞歸實(shí)現(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;
}
//堆排序,算法平均時(shí)間復(fù)雜度為O(nlogn),空間復(fù)雜度O(1)
vectorheapSort(vectornums)
{//首先構(gòu)建一個(gè)大堆
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é)點(diǎn)
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);
}
}
//計(jì)數(shù)排序,時(shí)間復(fù)雜度O(n+k),空間復(fù)雜度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ù)值作為索引,個(gè)數(shù)作為值
vectorcount(maxVal,0);
vectortemp(nums);
//數(shù)字需要減去1才能實(shí)現(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;
}
//計(jì)數(shù)排序,時(shí)間復(fù)雜度O(n+k),空間復(fù)雜度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ù)值作為索引,個(gè)數(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;
}
//桶排序 平均時(shí)間復(fù)雜度為O(n+k),空間復(fù)雜度為O(n+k)
//設(shè)置總共有5個(gè)桶
vectorbucketSort(vectornums)
{int maxVal=nums[max_element(nums.begin(),nums.end())-nums.begin()];
int minVal=nums[min_element(nums.begin(),nums.end())-nums.begin()];
//設(shè)置桶的大小
int bucketSize=5;
//設(shè)置桶的數(shù)目
int bucketCount=(maxVal-minVal)/bucketSize+1;
vector>buckets(bucketCount,vector());
//利用映射函數(shù)將數(shù)據(jù)分配到每個(gè)桶中
for(int i=0;ibuckets[(nums[i]-minVal)/bucketSize].push_back(nums[i]);
}
int index=0;
for(int i=0;i//對每個(gè)桶的內(nèi)部函數(shù)進(jìn)行排序
//調(diào)用之前寫的排序算法
buckets[i]=quickSort(buckets[i]);
//取出每個(gè)桶中的元素
for(int j=0;jnums[index++]=buckets[i][j];
}
}
return nums;
}
//基數(shù)排序,平均時(shí)間復(fù)雜度為O(n*k),空間復(fù)雜度為O(n+k)
//按位對應(yīng)的數(shù),從高位開始依次比較,進(jìn)行排序
vectorradixSort(vectornums)
{int length=nums.size();
int bits=maxBit(nums);
//設(shè)置數(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]++;
}
//計(jì)算前綴和,判斷前面由于個(gè)位數(shù)不存在的值
for(int j=1;j<10;j++)
{count[j]+=count[j-1];
}
//指定更新陣列的新位置,count[temp]--則是用來判斷這個(gè)位置是否到位
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)定的海外服務(wù)器提供商?創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源,準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性,企業(yè)級服務(wù)器適合批量采購,新人活動(dòng)首月15元起,快前往官網(wǎng)查看詳情吧
網(wǎng)站欄目:十大排序(總結(jié)+算法實(shí)現(xiàn))-創(chuàng)新互聯(lián)
文章轉(zhuǎn)載:http://aaarwkj.com/article14/cojege.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供網(wǎng)頁設(shè)計(jì)公司、品牌網(wǎng)站建設(shè)、虛擬主機(jī)、自適應(yīng)網(wǎng)站、網(wǎng)站收錄、ChatGPT
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請盡快告知,我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來源: 創(chuàng)新互聯(lián)
猜你還喜歡下面的內(nèi)容