溫故而知新:C++常用排序算法

2019-11-17 05:04:29

字體：大中小

來源：轉載

供稿：網友

　　選擇排序法SelectionSort(int arr[],int n)

　　template <typename T>
　　void SelectionSort(T arr[],int n)
　　{
　　int smallIndex;   //表中最小元素的下標
　　int pass,j;       //用來掃描子表的下標
　　T temp;           //用來交換表元素的臨時變量
　　
　　//pass的范圍是0~n-2
　　for (pass=0;pass<n-1;pass++)
　　{
　　//從下標pass開始掃描子表
　　smallIndex=pass;
　　
　　//j遍歷整個子表arr[pass+1]到arr[n-1]
　　for(j=pass+1;j<n;j++)
　　
　　//假如找到更小的元素,則將該位置賦值給smallIndex
　　if(arr[j]<arr[smallIndex])
　　smallIndex=j;
　　
　　//假如smallIndex和pass不在相同的位置
　　//則將子表中的最小項與arr[pass]交換
　　if(smallIndex!=pass)
　　{
　　temp=arr[pass];
　　arr[pass]=arr[smallIndex];
　　arr[smallIndex]=temp;
　　}
　　}
　　} 　　/************************************************************************
　　雙端選擇排序算法:是上面選擇排序算法的變種,可以定位每個子表中最小和最大元素
　　并把它們分別放在子表的開頭和結尾.
　　************************************************************************/
　　//雙端選擇排序算法函數deSelSort()的實現

　　template <typename T>
　　void deSelSort(T arr[],int n)
　　{
　　int smallIndex,largeIndex; //表中最小及最大元素的下標
　　int leFTPass=0,rightPass=n-1,i,j;     //用來從表左邊及右邊掃描子表的下標
　　T temp;                        //用于交換元素的臨時變量

更多內容請看C/C++技術專題專題，或

　　

　　while (leftPass<=rightPass)
　　{
　　//從左邊及右邊開始掃描子表
　　smallIndex=leftPass;
　　largeIndex=rightPass;
　　
　　//j和i遍歷整個子表arr[LeftPass]~arr[rightPass]
　　for (i=leftPass+1;i<rightPass;i++)
　　//假如找到更小的元素,則將該位置賦值給smallIndex
　　if (arr[i]<arr[smallIndex])
　　smallIndex=i;
　　
　　//假如smallIndex和leftPass不在相同的位置
　　//則將子表中的最小項與arr[pass]交換
　　if (smallIndex!=leftPass)
　　{
　　temp=arr[leftPass];
　　arr[leftPass]=arr[smallIndex];
　　arr[smallIndex]=temp;
　　}
　　
　　for (j=rightPass-1;j>leftPass;j--)
　　if(arr[j]>arr[largeIndex])
　　largeIndex=j;
　　
　　if(largeIndex!=rightPass)
　　{
　　temp=arr[rightPass];
　　arr[rightPass]=arr[largeIndex];
　　arr[largeIndex]=temp;
　　}
　　
　　//從兩頭收縮子表
　　leftPass++;
　　rightPass--;
　　}
　　} 　　//自編冒泡法排序算法函數bubbleSort()的實現

　　template <typename T>
　　int bubbleSort(T arr[],int n)
　　{
　　bool exchanged=false; //是否發生交換
　　int i,j; //用于遍歷子表的下標
　　T temp; //用于交換元素的臨時變量

更多內容請看C/C++技術專題專題，或

　　

　　//開始遍歷過程,以下標j構成子表,共有n-1個子表
　　for (j=n-1;j>=0;j--) //j從后往前收縮n-1~0,以構成子表0~n-1,0~n-2,0~n-3..0~1
　　{
　　exchanged=false;
　　for (i=0;i<j;i++) //遍歷子表范圍0~j
　　{
　　
　　if (arr[i]>arr[i+1])
　　{
　　temp=arr[i];
　　arr[i]=arr[i+1];
　　arr[i+1]=temp;
　　exchanged=true;
　　}
　　}
　　if (!exchanged) return n-j-1;//假如在一次遍歷中沒有發生交換,則表示已經
　　//排序好,中斷遍歷過程
　　}
　　return n-1-j;
　　} 　　//冒泡法排序一般算法函數bubbleSortEx()的實現

　　template <typename T>
　　int bubbleSortEx(T arr[],int n)
　　{
　　int i,pass;              //用于遍歷子表的下標
　　T temp;               //用于交換元素的臨時變量
　　
　　//開始遍歷過程,以下標j構成子表,共有n-1個子表
　　for (pass=0;pass<n;pass++) //pass從后往后擴大0~n-1,以構成子表0~n-1,0~n-2,0~n-3..0~1
　　{
　　for (i=0;i<n-pass;i++) //遍歷子表范圍0~n-pass
　　{
　　if (arr[i]>arr[i+1])
　　{
　　temp=arr[i];
　　arr[i]=arr[i+1];
　　arr[i+1]=temp;
　　}
　　}
　　}
　　return pass;
　　}
　　

更多內容請看C/C++技術專題專題，或

上一篇：C++中幾個比較不常用的關鍵字

下一篇：C++基礎:初始化類對象