溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
選擇排序
圖像化顯示： 
選擇排序的基本思想：從待排序序列中找到最小（大）的元素，存放到序列起始位置，縮小排序范圍，再找當前序列最小（大）的元素，放在起始位置之后，直到所有數據都被排完。
時間復雜度=O(n^2)
空間復雜度=O(1)
最好情況：已經有序 交換次數O(1)
最壞情況：逆序 交換次數O(n-1)
下面是c++版本的代碼實現
#include <iostream>
using namespace std;
//初始版本，每次找到最小的
void SelectSort(int *a,size_t size)
{
//比較次數：n*(n-1)/2
for(size_t i=0;i<size;i++)
{
int min=i;
for(size_t j=i+1;j<size;j++)
{
//交換次數：0~n-1之間
if(a[min]>a[j])
{
min=j;
}
}
//賦值次數：0~3(n-1)之間
if(min!=i)
{
swap(a[min],a[i]);
}
}
}
//改進版本，每次確定最大的和最小的
void SelectSort(int *a,size_t size)
{
//1/2數列的長度
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]);
}
}
}堆排序
堆排序的基本思想：利用堆這種數據結構進行選擇排序。
堆：堆是一個完全二叉樹，其任意一個非葉子結點滿足：
（最大堆）a[key]>a[key*2+1]&&a[key]>a[key*2+2];(非葉子結點大于任意一個孩子結點)
（最小堆）a[key]<a[key*2+1]&&a[key]<a[key*2+2]
升序：由最大堆（根結點是所有結點中的最大值，任意一個結點都比它的孩子結點的值要大）將頂部元素與末尾元素交換，減小堆中元素個數，每次都將當前堆中最大的數排到正確的位置，直到只有一個根結點，這種通過二叉樹的結構的排序，其n個數每次的找最大的數的執行次數是O(logn)即一個n個數的二叉樹深度，共有n個數所以最終的時間復雜度是O(nlogn)
時間復雜度：O(nlogn)
空間復雜度：O(1)
降序：與之相反
圖形化表示：
下面是c++版本的代碼實現
#include <iostream>
using namespace std;
//建局部堆----向下調整
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++;
}
//如果孩子結點大于父結點，交換，并且看交換完之后，這個局部是否還滿足條件
if(a[child]>a[parent])
{
swap(a[child],a[parent]);
parent=child;
child=parent*2=1；
}
//如果孩子結點不大于父節點，可以直接跳出
else
{
break;
}
}
}
//堆排序
void HeapSort(int *a,int size)
{
//將數組轉化成堆----O(logn)
for(int i=(size-2)/2;i>=0;i--)
{
AdjustDown(a,size,i);
}
//O(nlogn)
for(int i=0;i<size;i++)
{
//交換堆頂和最后一個結點
swap(a[size-1-i],a[0]);
//堆得范圍減小，并且建堆
AdustDown(a,size-i-1,0);
}
}直接插入排序
大家都玩過撲克牌吧，直接插入排序，就是撲克牌抓牌調整的過程，一開始手上只有一張牌，不用調整，第二張牌來了，這個時候如果它比前面的那張小，且前面沒有牌或者是前面的比你要插入的牌小就插入到比它小的牌后面或者最前面，假如（2，6，7）是你手上的牌，現在你抽到一張4，它比7小，繼續比，直到找到比4小的的2，插在2后面
時間復雜度：O(n^2)
空間復雜度：O(1)
最好情況下：已經是升序，需要比較n-1次
最壞情況下：逆序，需要比較n*(n-1)/2次
適用于：n比較小，n小于千次一下，插入排序較為有效
以下是c++代碼實現
#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--;
}
//當end所在位置的數比temp小時，while跳出循環，end指向帶插入位置的前一個位置
//所以end+1，才是temp該放的位置
a[end+1]=temp;
}
}希爾排序
希爾排序是插入排序的優化版本，可以盡快的讓小數往前走，大數往后走。
方法：把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，算法便終止。
優點：對已經有序的序列，效率高，可以達到線性效率即O(n)
缺點：每次只能移動一位（一般情況下的低效）
時間復雜度：O(n^2)
空間復雜度：O(1)
圖形化顯示：
以下是c++代碼實現
#include <iostream>
using namespace std;
void ShellSort(int *a,int size)
{
//增量值得設定
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;
}
}
}歸并排序
歸并排序應用的是分治法的思想，將一個無序序列，分成兩部分，再將這兩部分，看成子問題，在進行劃分，一直到序列中只有一個數字的時候，當前子序列就有序了，然后將這些個子序列進行有序合并，知道合并成整個序列。速度僅次于快速排序，為穩定排序算法。
簡潔的說就是：無序序列-----劃分成不可再分子序列----子序列有序合并----有序序列
時間復雜度為O(nlogn) 這是該算法中最好、最壞和平均的時間性能。
空間復雜度為 O(n)
圖形化顯示：
以下是c++實現(遞歸和非遞歸版本)
//合并
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]----數組越界
//[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);
}
}冒泡排序
算法思想：
冒泡排序算法的運作如下：（從后往前）
比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。在這一點，最后的元素應該會是最大的數。
針對所有的元素重復以上的步驟，除了最后一個。
持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。
優點：穩定性算法
缺點：時間復雜度高
時間復雜度：O(N^2)（平均時間復雜度）
空間復雜度：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]);
}
}
}
}快速排序
快速排序是對冒泡排序的一種改進。
它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。其中作為分隔數據的關鍵數據我們成為Key,當key為當前數列中的最大值時，快速排序就是冒泡排序.
最好情況：O(nlogn)
最壞情況：O(n^2)
時間復雜度:O(nlogn)
空間復雜度：O(1)
C++代碼實現
（1）基礎版---選擇數列的最后一個數作為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值時，用三數取中，避免最壞情況的發生。
//單趟排序
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;
}
}
//快速排序---三數取中
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）對每次排序進行優化，當數列中個數小于13（STL中這樣實現的），應用插入排序。
//單趟排序
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;
}
}
//快速排序中個數少時用插入排序
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)快排的非遞歸版本（棧實現）
//快速排序非遞歸實現
//手動利用棧來存儲每次分塊快排的起始點，棧非空時循環獲取中軸入棧。
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);
}
}免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
