溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
選擇排序
圖像化顯示： 
選擇排序的基本思想：從待排序序列中找到最?。ù螅┑脑兀娣诺叫蛄衅鹗嘉恢?，縮小排序范圍，再找當(dāng)前序列最?。ù螅┑脑兀旁谄鹗嘉恢弥?，直到所有數(shù)據(jù)都被排完。
時間復(fù)雜度=O(n^2)
空間復(fù)雜度=O(1)
最好情況：已經(jīng)有序 交換次數(shù)O(1)
最壞情況：逆序 交換次數(shù)O(n-1)
下面是c++版本的代碼實現(xiàn)
#include <iostream>
using namespace std;
//初始版本，每次找到最小的
void SelectSort(int *a,size_t size)
{
//比較次數(shù)：n*(n-1)/2
for(size_t i=0;i<size;i++)
{
int min=i;
for(size_t j=i+1;j<size;j++)
{
//交換次數(shù)：0~n-1之間
if(a[min]>a[j])
{
min=j;
}
}
//賦值次數(shù)：0~3(n-1)之間
if(min!=i)
{
swap(a[min],a[i]);
}
}
}
//改進版本，每次確定最大的和最小的
void SelectSort(int *a,size_t size)
{
//1/2數(shù)列的長度
for(size_t left=0,right=size-1;left<right;left++,right--)
{
int min=left;
int max=right;
for(size_t j=left+1;j<=right;j++)
{
if(a[min]>a[j])
{
min=j;
}
if(a[max]<a[j])
{
max=j;
}
}
if(min!=left)
{
//極端情況 左邊最大 右邊最小
if(min==right&&max==left)
{
swap(a[min],a[left]);
}
//左邊的最大 先將左邊的移過去
else if(min!=right&&max==left)
{
swap(a[max],a[right]);
swap(a[min],a[left]);
}
else
{
swap(a[min],a[left]);
}
}
if(max!=right)
{
swap(a[max],a[right]);
}
}
}堆排序
堆排序的基本思想：利用堆這種數(shù)據(jù)結(jié)構(gòu)進行選擇排序。
堆：堆是一個完全二叉樹，其任意一個非葉子結(jié)點滿足：
（最大堆）a[key]>a[key*2+1]&&a[key]>a[key*2+2];(非葉子結(jié)點大于任意一個孩子結(jié)點)
（最小堆）a[key]<a[key*2+1]&&a[key]<a[key*2+2]
升序：由最大堆（根結(jié)點是所有結(jié)點中的最大值，任意一個結(jié)點都比它的孩子結(jié)點的值要大）將頂部元素與末尾元素交換，減小堆中元素個數(shù)，每次都將當(dāng)前堆中最大的數(shù)排到正確的位置，直到只有一個根結(jié)點，這種通過二叉樹的結(jié)構(gòu)的排序，其n個數(shù)每次的找最大的數(shù)的執(zhí)行次數(shù)是O(logn)即一個n個數(shù)的二叉樹深度，共有n個數(shù)所以最終的時間復(fù)雜度是O(nlogn)
時間復(fù)雜度：O(nlogn)
空間復(fù)雜度：O(1)
降序：與之相反
圖形化表示：
下面是c++版本的代碼實現(xiàn)
#include <iostream>
using namespace std;
//建局部堆----向下調(diào)整
void AdjustDown(int *a,int size,int index)
{
parent=index;
int child=parent*2+1;
while(child<size)
{
//如果a[child+1]存在，找a[child+1]和a[child]中的最大值
if(child+1<size&&a[child+1]>a[child])
{
child++;
}
//如果孩子結(jié)點大于父結(jié)點，交換，并且看交換完之后，這個局部是否還滿足條件
if(a[child]>a[parent])
{
swap(a[child],a[parent]);
parent=child;
child=parent*2=1；
}
//如果孩子結(jié)點不大于父節(jié)點，可以直接跳出
else
{
break;
}
}
}
//堆排序
void HeapSort(int *a,int size)
{
//將數(shù)組轉(zhuǎn)化成堆----O(logn)
for(int i=(size-2)/2;i>=0;i--)
{
AdjustDown(a,size,i);
}
//O(nlogn)
for(int i=0;i<size;i++)
{
//交換堆頂和最后一個結(jié)點
swap(a[size-1-i],a[0]);
//堆得范圍減小，并且建堆
AdustDown(a,size-i-1,0);
}
}直接插入排序
大家都玩過撲克牌吧，直接插入排序，就是撲克牌抓牌調(diào)整的過程，一開始手上只有一張牌，不用調(diào)整，第二張牌來了，這個時候如果它比前面的那張小，且前面沒有牌或者是前面的比你要插入的牌小就插入到比它小的牌后面或者最前面，假如（2，6，7）是你手上的牌，現(xiàn)在你抽到一張4，它比7小，繼續(xù)比，直到找到比4小的的2，插在2后面
時間復(fù)雜度：O(n^2)
空間復(fù)雜度：O(1)
最好情況下：已經(jīng)是升序，需要比較n-1次
最壞情況下：逆序，需要比較n*(n-1)/2次
適用于：n比較小，n小于千次一下，插入排序較為有效
以下是c++代碼實現(xiàn)
#include <iostream>
using namespace std;
//直接插入排序
void InsertSort(int *a,size_t size)
{
for(size_t i=1;i<size;i++)
{
int end=i-1;
int temp=a[i];
while(end>=0&&a[end]>temp)
{
a[end+1]=a[end];
end--;
}
//當(dāng)end所在位置的數(shù)比temp小時，while跳出循環(huán)，end指向帶插入位置的前一個位置
//所以end+1，才是temp該放的位置
a[end+1]=temp;
}
}希爾排序
希爾排序是插入排序的優(yōu)化版本，可以盡快的讓小數(shù)往前走，大數(shù)往后走。
方法：把記錄按下標(biāo)的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至1時，整個文件恰被分成一組，算法便終止。
優(yōu)點：對已經(jīng)有序的序列，效率高，可以達到線性效率即O(n)
缺點：每次只能移動一位（一般情況下的低效）
時間復(fù)雜度：O(n^2)
空間復(fù)雜度：O(1)
圖形化顯示：
以下是c++代碼實現(xiàn)
#include <iostream>
using namespace std;
void ShellSort(int *a,int size)
{
//增量值得設(shè)定
int gap=size;
while (gap>1)
{
gap=gap/3+1;
for (size_t i=gap;i<size;i++)
{
int index=i;
int end=index-gap;
int temp=a[index];
while (end>=0&&temp<a[end])
{
a[end+gap]=a[end];
end-=gap;
}
a[end+gap]=temp;
}
}
}歸并排序
歸并排序應(yīng)用的是分治法的思想，將一個無序序列，分成兩部分，再將這兩部分，看成子問題，在進行劃分，一直到序列中只有一個數(shù)字的時候，當(dāng)前子序列就有序了，然后將這些個子序列進行有序合并，知道合并成整個序列。速度僅次于快速排序，為穩(wěn)定排序算法。
簡潔的說就是：無序序列-----劃分成不可再分子序列----子序列有序合并----有序序列
時間復(fù)雜度為O(nlogn) 這是該算法中最好、最壞和平均的時間性能。
空間復(fù)雜度為 O(n)
圖形化顯示：
以下是c++實現(xiàn)(遞歸和非遞歸版本)
//合并
void GetMerge(int *a,int begin1,int end1,int begin2,int end2,int *temp)
{
int i=0;
while(begin1<=end1&&begin2<=end2)
{
if (a[begin1]<a[begin2])
{
temp[i++]=a[begin1];
begin1++;
}
else
{
temp[i++]=a[begin2];
begin2++;
}
}
while(begin1<=end1)
{
temp[i++]=a[begin1++];
}
while(begin2<=end2)
{
temp[i++]=a[begin2++];
}
}
//分解
void _MergeSort(int *a,int left,int right)
{
if (right-left<1)
{
return;
}
int mid=left+(right-left)/2;
_MergeSort(a,left,mid);
_MergeSort(a,mid+1,right);
int *temp=new int[right-left+1];
GetMerge(a,left,mid,mid+1,right,temp);
memcpy(a+left,temp,(right-left+1)*sizeof(int));
}
//歸并排序
void MergeSort(int *a,size_t size)
{
_MergeSort(a,0,size-1);
}
void Print(int *a,size_t size)
{
for (size_t i=0;i<size;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
//歸并排序的非遞歸寫法
void MergeSortNor(int *a,size_t size)
{
//先分成一個一個的然后兩兩排序合并
int temp[10];
size_t begin=0;
size_t gap=0;
size_t end=begin+gap+1;
for (gap;gap<size;gap+=begin-end)
{
for(begin=0;begin<size;begin+=gap*2+2)//如果有個是單著的？？？
{
end=begin+gap+1;
if(begin+gap<size&&end<size&&end+gap<size)
{
GetMerge(a,begin,begin+gap,end,end+gap,temp+begin);
}
else
{
if(begin+gap<size)
{
if (end<size)
{
GetMerge(a,begin,begin+gap,end,size-1,temp+begin);
}
else
//[8，9][9，9]----數(shù)組越界
//[8，9][10，9]
GetMerge(a,begin,begin+gap,size,size-1,temp+begin);
}
else
{
//[8，9][9，9]
//[8，9][10，9]
GetMerge(a,begin,size-1,size,size-1,temp+begin);
}
}
}
memcpy(a,temp,sizeof(int)*size);
}
}冒泡排序
算法思想：
冒泡排序算法的運作如下：（從后往前）
比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。在這一點，最后的元素應(yīng)該會是最大的數(shù)。
針對所有的元素重復(fù)以上的步驟，除了最后一個。
持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。
優(yōu)點：穩(wěn)定性算法
缺點：時間復(fù)雜度高
時間復(fù)雜度：O(N^2)（平均時間復(fù)雜度）
空間復(fù)雜度：O(1)
以下是c++代碼
void BubbleSort(int *a1,size_t size)
{
for (size_t i=0;i<size;i++)
{
for (size_t j=0;j<size-i-1;j++)
{
if (a[j]>a[j+1])
{
swap(a[j],a[j+1]);
}
}
}
}快速排序
快速排序是對冒泡排序的一種改進。
它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。其中作為分隔數(shù)據(jù)的關(guān)鍵數(shù)據(jù)我們成為Key,當(dāng)key為當(dāng)前數(shù)列中的最大值時，快速排序就是冒泡排序.
最好情況：O(nlogn)
最壞情況：O(n^2)
時間復(fù)雜度:O(nlogn)
空間復(fù)雜度：O(1)
C++代碼實現(xiàn)
（1）基礎(chǔ)版---選擇數(shù)列的最后一個數(shù)作為key，遞歸快排
//單趟排序
int PartionSort(int *a1,int left,int right)
{
int begin=left;
int end=right-1;
int key=a[right];
while(begin<end)
{
while(begin<end&&a[begin]<key)
{
begin++;
}
while(end>begin&&a[end]>key)
{
end--;
}
if (end!=begin)
{
swap(a[end],a[begin]);
end--;
begin++;
}
}
if (a[begin]>key)
{
swap(a[begin],a[right]);
return begin;
}
else
{
return begin;
}
}
//快速排序--遞歸思想
void QuickSort(int *a1,int left,int right)
{
assert(a);
if (left<right)
{
int boundary=PartionSort(a,left,right);
QuickSort(a,left,boundary-1);
QuickSort(a,boundary+1,right);
}
}（2）改進版：選擇key值時，用三數(shù)取中，避免最壞情況的發(fā)生。
//單趟排序
int PartionSort(int *a1,int left,int right)
{
int begin=left;
int end=right-1;
int key=a[right];
while(begin<end)
{
while(begin<end&&a[begin]<key)
{
begin++;
}
while(end>begin&&a[end]>key)
{
end--;
}
if (end!=begin)
{
swap(a[end],a[begin]);
}
}
if (a[begin]>key)
{
swap(a[begin],a[right]);
return begin;
}
else
{
return right;
}
}
//快速排序---三數(shù)取中
void QuickSort(int *a1,int left,int right)
{
assert(a);
int mid=left+(right-left)/2;
if (left<right)
{
if (a[left]<a[right])
{
if (a[right]<a[mid])
{
swap(a[mid],a[right]);
}
if (a[left]>a[mid])
{
swap(a[mid],a[left]);
}
}
else
{
if (a[left]<a[mid])
{
swap(a[mid],a[left]);
}
if (a[right]>a[mid])
{
swap(a[mid],a[right]);
}
}
swap(a[mid],a[right]);
int boundary=PartionSort(a,left,right);
QuickSort(a,left,boundary-1);
QuickSort(a,boundary+1,right);
}
}（3）對每次排序進行優(yōu)化，當(dāng)數(shù)列中個數(shù)小于13（STL中這樣實現(xiàn)的），應(yīng)用插入排序。
//單趟排序
int PartionSort(int *a1,int left,int right)
{
int begin=left;
int end=right-1;
int key=a[right];
while(begin<end)
{
while(begin<end&&a[begin]<key)
{
begin++;
}
while(end>begin&&a[end]>key)
{
end--;
}
if (end!=begin)
{
swap(a[end],a[begin]);
}
}
if (a[begin]>key)
{
swap(a[begin],a[right]);
return begin;
}
else
{
return right;
}
}
//快速排序中個數(shù)少時用插入排序
void QuickSort(int *a1,int left,int right)
{
assert(a);
if(right-left<13)
{
InsertSort(a,right-left+1);
}
if (left<right)
{
int boundary=PartionSort(a,left,right);
QuickSort(a,left,boundary-1);
QuickSort(a,boundary+1,right);
}
}(4)快排的非遞歸版本（棧實現(xiàn)）
//快速排序非遞歸實現(xiàn)
//手動利用棧來存儲每次分塊快排的起始點，棧非空時循環(huán)獲取中軸入棧。
void QuickSort(int *a1,int left,int right)
{
stack<int> s1;
if(left<right)
{
int boundary=PartionSort(a,left,right);
if (boundary-1-left>1)
{
s1.push(left);
s1.push(boundary-1);
}
if (right-(boundary+1)>1)
{
s1.push(boundary+1);
s1.push(right);
}
while (!s1.empty())
{
int r=s1.top();
s1.pop();
int l=s1.top();
s1.pop();
boundary=PartionSort(a,l,r);
if (boundary-1-l>1)
{
s1.push(l);
s1.push(boundary-1);
}
if (r-(boundary+1)>1)
{
s1.push(boundary+1);
s1.push(r);
}
}
}
}(5)模擬單鏈表中的快排
int PartionSortLink(int *a1,int left,int right)
{
int prev=left-1;
int cur=left;
int key=a[right];
while(cur<right)
{
if (a[cur]<key)
{
prev++;
if (prev!=cur)
{
swap(a[prev],a[cur]);
}
}
if (cur==right-1)
{
prev++;
swap(a[prev],a[right]);
}
cur++;
}
return prev;
}
void QuickSortLink(int *a1,int left,int right)
{
assert(a);
if (left<right)
{
int boundary=PartionSortLink(a,left,right);
QuickSortLink(a,left,boundary-1);
QuickSortLink(a,boundary+1,right);
}
}免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號
手機網(wǎng)站二維碼