c++中八大排序算法

void print(int a[], int n ,int i){ 
  cout<<i <<":"; 
  for(int j= 0; j<8; j++){ 
    cout<<a[j] <<" "; 
  } 
  cout<<endl; 
} 
 
 
void InsertSort(int a[], int n) 
{ 
  for(int i= 1; i<n; i++){ 
    if(a[i] < a[i-1]){        //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入 
      int j= i-1;  
      int x = a[i];    //复制为哨兵，即存储待排序元素 
      a[i] = a[i-1];      //先后移一个元素 
      while(x < a[j]){ //查找在有序表的插入位置 
        a[j+1] = a[j]; 
        j--;     //元素后移 
      } 
      a[j+1] = x;   //插入到正确位置 
    } 
    print(a,n,i);      //打印每趟排序的结果 
  } 
   
} 
 
int main(){ 
  int a[8] = {3,1,5,7,2,4,9,6}; 
  InsertSort(a,8); 
  print(a,8,8); 
} 

void print(int a[], int n ,int i){ 
  cout<<i <<":"; 
  for(int j= 0; j<8; j++){ 
    cout<<a[j] <<" "; 
  } 
  cout<<endl; 
} 
/** 
 * 直接插入排序的一般形式 
 * 
 * @param int dk 缩小增量，如果是直接插入排序，dk=1 
 * 
 */ 
 
void ShellInsertSort(int a[], int n, int dk) 
{ 
  for(int i= dk; i<n; ++i){ 
    if(a[i] < a[i-dk]){     //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入 
      int j = i-dk;   
      int x = a[i];      //复制为哨兵，即存储待排序元素 
      a[i] = a[i-dk];     //首先后移一个元素 
      while(x < a[j]){   //查找在有序表的插入位置 
        a[j+dk] = a[j]; 
        j -= dk;       //元素后移 
      } 
      a[j+dk] = x;      //插入到正确位置 
    } 
    print(a, n,i ); 
  } 
   
} 
 
/** 
 * 先按增量d（n/2,n为要排序数的个数进行希尔排序 
 * 
 */ 
void shellSort(int a[], int n){ 
 
  int dk = n/2; 
  while( dk >= 1 ){ 
    ShellInsertSort(a, n, dk); 
    dk = dk/2; 
  } 
} 
int main(){ 
  int a[8] = {3,1,5,7,2,4,9,6}; 
  //ShellInsertSort(a,8,1); //直接插入排序 
  shellSort(a,8);      //希尔插入排序 
  print(a,8,8); 
} 

void print(int a[], int n ,int i){ 
  cout<<"第"<<i+1 <<"趟 : "; 
  for(int j= 0; j<8; j++){ 
    cout<<a[j] <<" "; 
  } 
  cout<<endl; 
} 
/** 
 * 数组的最小值 
 * 
 * @return int 数组的键值 
 */ 
int SelectMinKey(int a[], int n, int i) 
{ 
  int k = i; 
  for(int j=i+1 ;j< n; ++j) { 
    if(a[k] > a[j]) k = j; 
  } 
  return k; 
} 
 
/** 
 * 选择排序 
 * 
 */ 
void selectSort(int a[], int n){ 
  int key, tmp; 
  for(int i = 0; i< n; ++i) { 
    key = SelectMinKey(a, n,i);      //选择最小的元素 
    if(key != i){ 
      tmp = a[i]; a[i] = a[key]; a[key] = tmp; //最小元素与第i位置元素互换 
    } 
    print(a, n , i); 
  } 
} 
int main(){ 
  int a[8] = {3,1,5,7,2,4,9,6}; 
  cout<<"初始值："; 
  for(int j= 0; j<8; j++){ 
    cout<<a[j] <<" "; 
  } 
  cout<<endl<<endl; 
  selectSort(a, 8); 
  print(a,8,8); 
} 

void SelectSort(int r[],int n) { 
  int i ,j , min ,max, tmp; 
  for (i=1 ;i <= n/2;i++) {  
    // 做不超过n/2趟选择排序  
    min = i; max = i ; //分别记录最大和最小关键字记录位置 
    for (j= i+1; j<= n-i; j++) { 
      if (r[j] > r[max]) {  
        max = j ; continue ;  
      }  
      if (r[j]< r[min]) {  
        min = j ;  
      }   
   }  
   //该交换操作还可分情况讨论以提高效率 
   tmp = r[i-1]; r[i-1] = r[min]; r[min] = tmp; 
   tmp = r[n-i]; r[n-i] = r[max]; r[max] = tmp;  
 
  }  
} 

void print(int a[], int n){ 
  for(int j= 0; j<n; j++){ 
    cout<<a[j] <<" "; 
  } 
  cout<<endl; 
} 
 
 
 
/** 
 * 已知H[s…m]除了H[s] 外均满足堆的定义 
 * 调整H[s],使其成为大顶堆即将对第s个结点为根的子树筛选, 
 * 
 * @param H是待调整的堆数组 
 * @param s是待调整的数组元素的位置 
 * @param length是数组的长度 
 * 
 */ 
void HeapAdjust(int H[],int s, int length) 
{ 
  int tmp = H[s]; 
  int child = 2*s+1; //左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置) 
  while (child < length) { 
    if(child+1 <length && H[child]<H[child+1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点) 
      ++child ; 
    } 
    if(H[s]<H[child]) { // 如果较大的子结点大于父结点 
      H[s] = H[child]; // 那么把较大的子结点往上移动，替换它的父结点 
      s = child;    // 重新设置s ,即待调整的下一个结点的位置 
      child = 2*s+1; 
    } else {      // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出 
       break; 
    } 
    H[s] = tmp;     // 当前待调整的结点放到比其大的孩子结点位置上 
  } 
  print(H,length); 
} 
 
 
/** 
 * 初始堆进行调整 
 * 将H[length-1]建成堆 
 * 调整完之后第一个元素是序列的最小的元素 
 */ 
void BuildingHeap(int H[], int length) 
{  
  //最后一个有孩子的节点的位置 i= (length -1) / 2 
  for (int i = (length -1) / 2 ; i >= 0; --i) 
    HeapAdjust(H,i,length); 
} 
/** 
 * 堆排序算法 
 */ 
void HeapSort(int H[],int length) 
{ 
  //初始堆 
  BuildingHeap(H, length); 
  //从最后一个元素开始对序列进行调整 
  for (int i = length - 1; i > 0; --i) 
  { 
    //交换堆顶元素H[0]和堆中最后一个元素 
    int temp = H[i]; H[i] = H[0]; H[0] = temp; 
    //每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整 
    HeapAdjust(H,0,i); 
 } 
}  
 
int main(){ 
  int H[10] = {3,1,5,7,2,4,9,6,10,8}; 
  cout<<"初始值："; 
  print(H,10); 
  HeapSort(H,10); 
  //selectSort(a, 8); 
  cout<<"结果："; 
  print(H,10); 
 
} 

void bubbleSort(int a[], int n){ 
  for(int i =0 ; i< n-1; ++i) { 
    for(int j = 0; j < n-i-1; ++j) { 
      if(a[j] > a[j+1]) 
      { 
        int tmp = a[j] ; a[j] = a[j+1] ; a[j+1] = tmp; 
      } 
    } 
  } 
} 

void Bubble_1 ( int r[], int n) { 
  int i= n -1; //初始时,最后位置保持不变 
  while ( i> 0) {  
    int pos= 0; //每趟开始时,无记录交换 
    for (int j= 0; j< i; j++) 
      if (r[j]> r[j+1]) { 
        pos= j; //记录交换的位置  
        int tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp; 
      }  
    i= pos; //为下一趟排序作准备 
   }  
}  

void Bubble_2 ( int r[], int n){ 
  int low = 0;  
  int high= n -1; //设置变量的初始值 
  int tmp,j; 
  while (low < high) { 
    for (j= low; j< high; ++j) //正向冒泡,找到最大者 
      if (r[j]> r[j+1]) { 
        tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp; 
      }  
    --high;         //修改high值, 前移一位 
    for ( j=high; j>low; --j) //反向冒泡,找到最小者 
      if (r[j]<r[j-1]) { 
        tmp = r[j]; r[j]=r[j-1];r[j-1]=tmp; 
      } 
    ++low;         //修改low值,后移一位 
  }  
}  

void print(int a[], int n){ 
  for(int j= 0; j<n; j++){ 
    cout<<a[j] <<" "; 
  } 
  cout<<endl; 
} 
 
void swap(int *a, int *b) 
{ 
  int tmp = *a; 
  *a = *b; 
  *b = tmp; 
} 
 
int partition(int a[], int low, int high) 
{ 
  int privotKey = a[low];               //基准元素 
  while(low < high){                  //从表的两端交替地向中间扫描 
    while(low < high && a[high] >= privotKey) --high; //从high 所指位置向前搜索，至多到low+1 位置。将比基准元素小的交换到低端 
    swap(&a[low], &a[high]); 
    while(low < high && a[low] <= privotKey ) ++low; 
    swap(&a[low], &a[high]); 
  } 
  print(a,10); 
  return low; 
} 
 
 
void quickSort(int a[], int low, int high){ 
  if(low < high){ 
    int privotLoc = partition(a, low, high); //将表一分为二 
    quickSort(a, low, privotLoc -1);     //递归对低子表递归排序 
    quickSort(a,  privotLoc + 1, high);    //递归对高子表递归排序 
  } 
} 
 
int main(){ 
  int a[10] = {3,1,5,7,2,4,9,6,10,8}; 
  cout<<"初始值："; 
  print(a,10); 
  quickSort(a,0,9); 
  cout<<"结果："; 
  print(a,10); 
 
} 

void print(int a[], int n){ 
  for(int j= 0; j<n; j++){ 
    cout<<a[j] <<" "; 
  } 
  cout<<endl; 
} 
 
void swap(int *a, int *b) 
{ 
  int tmp = *a; 
  *a = *b; 
  *b = tmp; 
} 
 
int partition(int a[], int low, int high) 
{ 
  int privotKey = a[low];         //基准元素 
  while(low < high){          //从表的两端交替地向中间扫描 
    while(low < high && a[high] >= privotKey) --high; //从high 所指位置向前搜索，至多到low+1 位置。将比基准元素小的交换到低端 
    swap(&a[low], &a[high]); 
    while(low < high && a[low] <= privotKey ) ++low; 
    swap(&a[low], &a[high]); 
  } 
  print(a,10); 
  return low; 
} 
 
 
void qsort_improve(int r[ ],int low,int high, int k){ 
  if( high -low > k ) { //长度大于k时递归, k为指定的数 
    int pivot = partition(r, low, high); // 调用的Partition算法保持不变 
    qsort_improve(r, low, pivot - 1,k); 
    qsort_improve(r, pivot + 1, high,k); 
  }  
}  
void quickSort(int r[], int n, int k){ 
  qsort_improve(r,0,n,k);//先调用改进算法Qsort使之基本有序 
 
  //再用插入排序对基本有序序列排序 
  for(int i=1; i<=n;i ++){ 
    int tmp = r[i];  
    int j=i-1; 
    while(tmp < r[j]){ 
      r[j+1]=r[j]; j=j-1;  
    } 
    r[j+1] = tmp; 
  }  
 
}  
 
 
 
int main(){ 
  int a[10] = {3,1,5,7,2,4,9,6,10,8}; 
  cout<<"初始值："; 
  print(a,10); 
  quickSort(a,9,4); 
  cout<<"结果："; 
  print(a,10); 
 
} 

//将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n] 
void Merge(ElemType *r,ElemType *rf, int i, int m, int n) 
{ 
  int j,k; 
  for(j=m+1,k=i; i<=m && j <=n ; ++k){ 
    if(r[j] < r[i]) rf[k] = r[j++]; 
    else rf[k] = r[i++]; 
  } 
  while(i <= m) rf[k++] = r[i++]; 
  while(j <= n) rf[k++] = r[j++]; 
} 

void print(int a[], int n){ 
  for(int j= 0; j<n; j++){ 
    cout<<a[j] <<" "; 
  } 
  cout<<endl; 
} 
 
//将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n] 
void Merge(ElemType *r,ElemType *rf, int i, int m, int n) 
{ 
  int j,k; 
  for(j=m+1,k=i; i<=m && j <=n ; ++k){ 
    if(r[j] < r[i]) rf[k] = r[j++]; 
    else rf[k] = r[i++]; 
  } 
  while(i <= m) rf[k++] = r[i++]; 
  while(j <= n) rf[k++] = r[j++]; 
  print(rf,n+1); 
} 
 
void MergeSort(ElemType *r, ElemType *rf, int lenght) 
{  
  int len = 1; 
  ElemType *q = r ; 
  ElemType *tmp ; 
  while(len < lenght) { 
    int s = len; 
    len = 2 * s ; 
    int i = 0; 
    while(i+ len <lenght){ 
      Merge(q, rf, i, i+ s-1, i+ len-1 ); //对等长的两个子表合并 
      i = i+ len; 
    } 
    if(i + s < lenght){ 
      Merge(q, rf, i, i+ s -1, lenght -1); //对不等长的两个子表合并 
    } 
    tmp = q; q = rf; rf = tmp; //交换q,rf，以保证下一趟归并时，仍从q 归并到rf 
  } 
} 
 
 
int main(){ 
  int a[10] = {3,1,5,7,2,4,9,6,10,8}; 
  int b[10]; 
  MergeSort(a, b, 10); 
  print(b,10); 
  cout<<"结果："; 
  print(a,10); 
 
} 

void MSort(ElemType *r, ElemType *rf,int s, int t) 
{  
  ElemType *rf2; 
  if(s==t) r[s] = rf[s]; 
  else 
  {  
    int m=(s+t)/2;     /*平分*p 表*/ 
    MSort(r, rf2, s, m);    /*递归地将p[s…m]归并为有序的p2[s…m]*/ 
    MSort(r, rf2, m+1, t);   /*递归地将p[m+1…t]归并为有序的p2[m+1…t]*/ 
    Merge(rf2, rf, s, m+1,t);  /*将p2[s…m]和p2[m+1…t]归并到p1[s…t]*/ 
  } 
} 
void MergeSort_recursive(ElemType *r, ElemType *rf, int n) 
{  /*对顺序表*p 作归并排序*/ 
  MSort(r, rf,0, n-1); 
} 

Void RadixSort(Node L[],length,maxradix) 
{ 
  int m,n,k,lsp; 
  k=1;m=1; 
  int temp[10][length-1]; 
  Empty(temp); //清空临时空间 
  while(k<maxradix) //遍历所有关键字 
  { 
   for(int i=0;i<length;i++) //分配过程 
  { 
    if(L[i]<m) 
     Temp[0][n]=L[i]; 
    else 
     Lsp=(L[i]/m)%10; //确定关键字 
    Temp[lsp][n]=L[i]; 
    n++; 
  } 
  CollectElement(L,Temp); //收集 
  n=0; 
  m=m*10; 
 k++; 
 } 
}