七種常見的排序算法--c++直接上代碼，注釋詳細
class Solution { //常見7種排序算法
public:
Solution(){
}
//************************************
// 函數名稱: bubbleSort
// 函數全稱: Solution::bubbleSort
// 函數說明： 冒泡排序
// 函數屬性: public
// 函數參數: vector & a
// 返回值 : void
// Qualifier:
// 函數作者： Medal
// 編寫時間： 2016/08/10 17:53:36
// 是否調試： Y
//************************************
void bubbleSort(vector &a){ //冒泡排序算法
if(a.empty() || 1 == a.size()) return;
int aszie = (int)a.size();
for (int i = 0; i < aszie; ++i)
{
for (int j = aszie - 2; j >= i; --j )
{
if (a[j+1] < a[j]) //依次與相鄰的元素比較，滿足條件則交換
{
swap(a[j+1], a[j]);
}
}
}
}
//************************************
// 函數名稱: bubbleSort2
// 函數全稱: Solution::bubbleSort2
// 函數說明： 優化之後的冒泡排序，避免對已經有序的部分進行對於的比較操作
// 函數屬性: public
// 函數參數: vector & a
// 返回值 : void
// Qualifier:
// 函數作者： Medal
// 編寫時間： 2016/08/10 17:54:17
// 是否調試： Y
//************************************
void bubbleSort2(vector &a){ //優化的冒泡排序算法
if(a.empty() || 1 == a.size()) return;
int aszie = (int)a.size();
bool flag = true; //用於標記此次循環有沒有交換元素,避免前面序列已經有序，還要繼續比較的情況
for (int i = 0; i < aszie && flag; ++i)
{
flag = false;
for (int j = aszie - 2; j >= i; --j )
{
if (a[j+1] < a[j])
{
swap(a[j+1], a[j]);
flag = true;
}
}
}
}
//************************************
// 函數名稱: selectSort
// 函數全稱: Solution::selectSort
// 函數說明： 簡單選擇排序，從第一個元素開始，每次從未排序的部分序曲
// 第一個元素作為基准元素，並從剩余未排序的元素中找出最小的元素，如果滿足條件就交換
// 函數屬性: public
// 函數參數: vector & a
// 返回值 : void
// Qualifier:
// 函數作者： Medal
// 編寫時間： 2016/08/10 17:56:26
// 是否調試： Y
//************************************
void selectSort(vector &a){//簡單選擇排序算法
if(a.empty() || 1 == a.size()) return;
int aszie = (int)a.size();
for (int i = 0; i < aszie; ++i)
{
//尋找第i個元素之後的小於第i元素的最小的元素
int minj = i;
for (int j = i + 1; j < aszie ; ++j)
{
if (a[minj] > a[j])
{
minj = j;
}
}
if (i != minj)
{
swap(a[i],a[minj]);
}
}
}
//************************************
// 函數名稱: insertSort
// 函數全稱: Solution::insertSort
// 函數說明： 簡單插入排序，類比抓取撲克牌，從第一個元素i開始，後一個元素i+1與前一個元素比較，如果【i】>【i+1】
// 則從i向前搜索至小於【i+1】的元素j，依次將這之間的元素向後移位，將元素i+1放在j+1的位置，如此循環執行到最後一個元素即可
// 函數屬性: public
// 函數參數: vector & a
// 返回值 : void
// Qualifier:
// 函數作者： Medal
// 編寫時間： 2016/08/10 17:59:24
// 是否調試： Y
//************************************
void insertSort(vector &a){ //簡單插入排序
if(a.empty() || 1 == a.size()) return;
int aszie = (int)a.size();
int mypos = a[0];
for (int i = 1; i< aszie; ++i)
{
mypos = a[i];
if (a[i] < a[i-1])
{
int j;
for (j = i-1; j>=0 && a[j] > mypos; --j) //將當前i位置之前大於i號元素的元素全部整體後移以為，然後插入i號元素
{
a[j+1] = a[j];
}
a[++j] = mypos;
}
}
}
//************************************
// 函數名稱: shellSort
// 函數全稱: Solution::shellSort
// 函數說明： 希爾排序，選取小於總長度的一個步長inc，從第一個元素i開始，與i+inc元素比較，滿足條件則交換，並向前跳相同間隔的元素比較，若滿足，也交換；依次循環至i+inc等於最後一個元素，即一遍
// 然後第二、三。。遍依次按照比例減小步長，重復操作，直至步長不大於1，停止
// 函數屬性: public
// 函數參數: vector & a
// 返回值 : void
// Qualifier:
// 函數作者： Medal
// 編寫時間： 2016/08/10 18:06:58
// 是否調試： Y/N
//************************************
void shellSort(vector &a){ //希爾排序---間隔相等點比較交換
if(a.empty() || 1 == a.size()) return;
int aszie = (int)a.size();
int inc = aszie;
do
{
inc = inc/6 + 1;
for (int i = inc; i < aszie; ++i)
{
if (a[i] < a[i-inc])
{
int mypos = a[i];
for (int j = i; j-inc >= 0 && a[j-inc]>a[j]; j-=inc) //依次循環前跳，交換前面所有間隔點上大於該元素的元素
{
swap(a[j],a[j-inc]);
}
}
}
} while (inc > 1); //最後的間隔必須大於1
}
//************************************
// 函數名稱: heapSort
// 函數全稱: Solution::heapSort
// 函數說明： 堆排序，先通過元素對半原則，從中間元素mid開始到第0個元素，依次比較其左右孩子節點，若孩子節點大於根節點，則交換，並以該孩子節點為
// 根節點依次做比較；然後對mid-1~0重復上述操作，從而形成大頂堆。形成大頂堆後，將最頂端元素（即最大元素）與最末尾元素對調，
// 並從頂端元素開始，調整除末尾元素外的堆元素，重新調整為大頂堆；循環至第1個節點，則停止；排序完成。
// 函數屬性: public
// 函數參數: vector & a
// 返回值 : void
// Qualifier:
// 函數作者： Medal
// 編寫時間： 2016/08/10 21:38:53
// 是否調試： Y
//************************************
void heapSort(vector &a){ //堆排序
if(a.empty() || 1 == a.size()) return;
int aszie = (int)a.size();
for (int i = aszie/2-1; i >=0; --i)
{
heapAdjust(a,i,(int)a.size()); //調整為大頂堆，最大的元素始終在堆頂；
}
for (int i = aszie-1; i > 0 ; --i)
{
swap(a[0],a[i]); //將堆頂元素，即最大的元素調換至堆尾，依次將次大元素調整到堆次尾
heapAdjust(a,0,i); //重新調整為大頂堆，將最大元素放到堆頂，以便下一次調至目前未排序的堆尾
}
}
//************************************
// 函數名稱: mergeSort
// 函數全稱: Solution::mergeSort
// 函數說明： 歸並排序，對所有元素對半分組，標注每個分組的起始、中點、終點，分別對左右半組數據遞歸調用，至起點等於終點，則將該元素
// 存入輸出數組；遞歸調用完畢後，按照從小到大合並兩個半數組，至輸出數組，即可。
// 函數屬性: public
// 函數參數: vector & a
// 返回值 : void
// Qualifier:
// 函數作者： Medal
// 編寫時間： 2016/08/10 21:45:11
// 是否調試： Y
//************************************
void mergeSort(vector &a){ //歸並排序
if(a.empty() || 1 == a.size()) return;
int aszie = (int)a.size();
mSort(a,a,0,aszie-1); //歸並排序核心程序
}
//************************************
// 函數名稱: quickSort
// 函數全稱: Solution::quickSort
// 函數說明： 快速排序
// 函數屬性: public
// 函數參數: int a[]
// 函數參數: int n
// 返回值 : void
// Qualifier:
// 函數作者： Medal
// 編寫時間： 2016/08/10 22:20:35
// 是否調試： Y
//************************************
void quickSort(int a[],int n){ //快速排序
if(n == 0 || 1 > n) return;
int *pos1 =a,*pos2 = a+n-1;
while(pos1 < pos2){
while(pos1< pos2 && *pos2 >= a[0]){--pos2;}
while(pos1< pos2 && *pos1 <= a[0]){++pos1;}
if (pos1 & a
// 函數參數: int pos //待調整元素在堆中的序號，序號從0開始編號
// 函數參數: int n //需要調整的元素的最大序號，此序號之後的元素不作調整（主要是在後面排序時起作用）
// 返回值 : void
// Qualifier:
// 函數作者： Medal
// 編寫時間： 2016/08/10 22:14:06
// 是否調試： Y
//************************************
void heapAdjust(vector &a,int pos,int n){
int leftpos = 2*pos+1;
int rightpos = 2*pos+2; //由於堆為完全二叉樹，根據性質，可知pos號節點的左孩子和右孩子的編號
if (rightpos < n) //判斷是否含有右孩子，如果有，則表明左右孩子均有
{
int nextpos = a[leftpos] > a[rightpos] ? leftpos : rightpos; //選取左右孩子中最大的孩子，作為比較節點
if (a[pos] < a[nextpos]) //如果比較節點的值大於根節點，則互換位置
{
swap(a[pos], a[nextpos] ); //互換位置
heapAdjust(a,nextpos,n); //並調整互換位置後的比較節點開始調整堆為大頂堆
}
}else if (leftpos < n ) //如果只是有左孩子，則只對左孩子進行上述操作
{
if ( a[pos] < a[leftpos] )
{
int nextpos = leftpos;
swap( a[pos], a[nextpos] );
heapAdjust(a,nextpos,n);
}
}
}
//************************************
// 函數名稱: mSort
// 函數全稱: Solution::mSort
// 函數說明： 歸並排序核心程序，把數組分解成只有一個元素的子數組
// 函數屬性: private
// 函數參數: vectorsrc 輸入數組
// 函數參數: vector & dst 排序輸出數組
// 函數參數: int sta 數組起始點
// 函數參數: int ed 數組終止點
// 返回值 : void
// Qualifier:
// 函數作者： Medal
// 編寫時間： 2016/08/10 22:17:48
// 是否調試： Y
//************************************
void mSort(vectorsrc,vector &dst,int sta,int ed){
if (sta == ed)
{
dst[sta] = src[sta];
}else{
//vector tep = src;
int mid = (sta+ed)/2;
mSort(src,dst,sta,mid);
mSort(src,dst,mid+1,ed);
myMerge(dst,dst,sta,mid,ed);
}
}
//************************************
// 函數名稱: myMerge
// 函數全稱: Solution::myMerge
// 函數說明： 合並排序
// 函數屬性: private
// 函數參數: vectorsrc
// 函數參數: vector & dst
// 函數參數: int sta 起點
// 函數參數: int mid 中點
// 函數參數: int ed 終點
// 返回值 : void
// Qualifier:
// 函數作者： Medal
// 編寫時間： 2016/08/10 22:19:47
// 是否調試： Y
//************************************
void myMerge(vectorsrc,vector&dst,int sta,int mid,int ed){
int i,j,k;
for (i = sta,j = mid +1,k=i; i <= mid && j <= ed;++k) //按照從小到大順序放入目標數組
{
if (src[i] > src[j])
{
dst[k] = src[j++];
}else{
dst[k] = src[i++];
}
}
if (i <= mid) //存入剩下部分的元素至輸出數組
{
for ( ; i <= mid; ++i)
{
dst[k++] = src[i];
}
}
if (j<=ed) //存入剩下部分的元素至輸出數組
{
for (; j <= ed;++j )
{
dst[k++] = src[j];
}
}
}
};
int main()
{
Solution ss;
int a[]={50,10,90,30,70,40,80,60,20};
vector va(a,a+sizeof(a)/sizeof(int));
string str("abca");
//print_vector(va);
//ss.bubbleSort(va);
//ss.bubbleSort2(va);
//ss.selectSort(va);
//ss.insertSort(va);
//ss.shellSort(va);
//ss.heapSort(va);
ss.mergeSort(va);
//ss.quickSort(a,sizeof(a)/sizeof(int));
//print_vector(va);
system("pause");
return 0;
}
