程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 溫故而知新:C++常用排序算法

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

編輯:C++入門知識
  選擇排序法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++技術專題專題,或
 
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved