devbox
从前慢现在也慢
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

排序算法总结--C++代码实现_c++快速输出每次顺序

作者：从前慢现在也慢 | 2024-06-27 23:36:15

赞

踩

c++快速输出每次顺序

1.常见排序算法

 

 

 

 

 

2. 插入排序

2.1 直接插入排序

  1.  
  2. void print(int *arr, int nCount, int n=0)
  3. {
  4. 	int i = 0;
  5. 	printf("%d==== ", n);
  6. 	while(i < nCount) printf("%2d  ", arr[i++]);
  7. 	printf("\n");
  8. }
  9. // Straight Insertion Sort
  10. void InsertSort(int* arr, int nCount)
  11. {
  12. 	if (arr == NULL || nCount < 2)
  13. 	{
  14. 		return;
  15. 	}
  16.  
  17. 	for(int i = 1; i < nCount; i++)
  18. 	{
  19. 		if(arr[i] < arr[i-1])
  20. 		{	
  21. 			int t= arr[i];
  22. 			int j = i;
  23. 			while((j > 0) && (t <= arr[j-1]))
  24. 			{
  25. 				arr[j] = arr[j-1];
  26. 				j--;
  27. 			}
  28. 			arr[j] = t;
  29. 		}
  30. 	}
  31. }
  32.

2.2 希尔排序 -- 插入

  1. void print(int *arr, int nCount, int n=0)
  2. {
  3. 	int i = 0;
  4. 	printf("%d==== ", n);
  5. 	while(i < nCount) printf("%2d  ", arr[i++]);
  6. 	printf("\n");
  7. }
  8. // ShellInsertSort
  9. void ShellInsertSort(int* arr, int nCount)
  10. {
  11. 	if (arr == NULL || nCount < 2)
  12. 	{
  13. 		return;
  14. 	}
  15. 	int dk = nCount/2;
  16. 	while(dk > 0)
  17. 	{
  18. 		for(int i = dk; i < nCount; i++)
  19. 		{
  20. 			if (arr[i] < arr[i-dk])
  21. 			{
  22. 				int t = arr[i];
  23. 				int j = i;
  24. 				while(j-dk>=0 && arr[j-dk]>t)
  25. 				{
  26. 					arr[j] = arr[j-dk];
  27. 					j-=dk;
  28. 				}
  29. 				arr[j] = t;
  30. 			}
  31. 			print(arr,nCount,i);
  32. 		}
  33. 		print(arr,nCount,dk);
  34. 		dk = dk/2;
  35. 	}
  36. }

3. 选择排序

3.1直接选择排序

  1. #include<iostream>
  2.  
  3. void print(int a[], int n ,int i){  
  4.     std::cout<<"第"<<i+1 <<"趟 : ";  
  5.     for(int j= 0; j<8; j++){  
  6.         std::cout<<a[j] <<"  ";  
  7.     }  
  8.     std::cout<<std::endl;  
  9. }  
  10. /** 
  11.  * 数组的最小值 
  12.  * 
  13.  * @return int 数组的键值 
  14.  */  
  15. int SelectMinKey(int a[], int n, int i)  
  16. {  
  17.     int k = i;  
  18.     for(int j=i+1 ;j< n; ++j) {  
  19.         if(a[k] > a[j]) k = j;  
  20.     }  
  21.     return k;  
  22. }  
  23.   
  24. /** 
  25.  * 选择排序 
  26.  * 
  27.  */  
  28. void selectSort(int a[], int n){  
  29.     int key, tmp;  
  30.     for(int i = 0; i< n; ++i) {  
  31.         key = SelectMinKey(a, n,i);           //选择最小的元素  
  32.         if(key != i){  
  33.             tmp = a[i];  a[i] = a[key]; a[key] = tmp; //最小元素与第i位置元素互换  
  34.         }  
  35.         print(a,  n , i);  
  36.     }  
  37. }  
  38.  
  39. /**
  40. * 优化
  41. */
  42. void SelectSort(int r[],int n) {  
  43.     int i ,j , min ,max, tmp;  
  44.     for (i=1 ;i <= n/2;i++) {    
  45.         // 做不超过n/2趟选择排序   
  46.         min = i; max = i ; //分别记录最大和最小关键字记录位置  
  47.         for (j= i+1; j<= n-i; j++) {  
  48.             if (r[j] > r[max]) {   
  49.                 max = j ; continue ;   
  50.             }    
  51.             if (r[j]< r[min]) {   
  52.                 min = j ;   
  53.              }     
  54.       }    
  55.       //该交换操作还可分情况讨论以提高效率  
  56.       tmp = r[i-1]; r[i-1] = r[min]; r[min] = tmp;  
  57.       tmp = r[n-i]; r[n-i] = r[max]; r[max] = tmp;   
  58.   
  59.     }   
  60. } 
  61. int main(){  
  62.     int a[8] = {3,1,5,7,2,4,9,6};  
  63.     std::cout<<"初始值：";  
  64.     for(int j= 0; j<8; j++){  
  65.         std::cout<<a[j] <<"  ";  
  66.     }  
  67.     std::cout<<std::endl<<std::endl;  
  68.     selectSort(a, 8);  
  69.     print(a,8,8);  
  70. }

3.2堆排序--选择 

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. void print(int a[], int n){  
  5.     for(int j= 0; j<n; j++){  
  6.         cout<<a[j] <<"  ";  
  7.     }  
  8.     cout<<endl;  
  9. }  
  10.  
  11. /** 
  12.  * 已知H[s…m]除了H[s] 外均满足堆的定义 
  13.  * 调整H[s],使其成为大顶堆.即将对第s个结点为根的子树筛选,  
  14.  * 
  15.  * @param H是待调整的堆数组 
  16.  * @param s是待调整的数组元素的位置 
  17.  * @param length是数组的长度 
  18.  * 
  19.  */  
  20. void HeapAdjust(int H[],int s, int length)  
  21. {  
  22.     int tmp  = H[s];  
  23.     int child = 2*s+1; //左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置)  
  24.     while (child < length) {  
  25.         if(child+1 <length && H[child]<H[child+1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)  
  26.             ++child ;  
  27.         }  
  28.         if(H[s]<H[child]) {  // 如果较大的子结点大于父结点  
  29.             H[s] = H[child]; // 那么把较大的子结点往上移动，替换它的父结点  
  30.             s = child;       // 重新设置s ,即待调整的下一个结点的位置  
  31.             child = 2*s+1;  
  32.         }  else {            // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出  
  33.              break;  
  34.         }  
  35.         H[s] = tmp;         // 当前待调整的结点放到比其大的孩子结点位置上  
  36.     }  
  37.     print(H,length);  
  38. }  
  39.   
  40. /** 
  41.  * 初始堆进行调整 
  42.  * 将H[0..length-1]建成堆 
  43.  * 调整完之后第一个元素是序列的最小的元素 
  44.  */  
  45. void BuildingHeap(int H[], int length)  
  46. {   
  47.     //最后一个有孩子的节点的位置 i=  (length -1) / 2  
  48.     for (int i = (length -1) / 2 ; i >= 0; --i)  
  49.         HeapAdjust(H,i,length);  
  50. } 
  51.  
  52. /** 
  53.  * 堆排序算法 
  54.  */  
  55. void HeapSort(int H[],int length)  
  56. {  
  57.     //初始堆  
  58.     BuildingHeap(H, length);  
  59.     //从最后一个元素开始对序列进行调整  
  60.     for (int i = length - 1; i > 0; --i)  
  61.     {  
  62.         //交换堆顶元素H[0]和堆中最后一个元素  
  63.         int temp = H[i]; H[i] = H[0]; H[0] = temp;  
  64.         //每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整  
  65.         HeapAdjust(H,0,i);  
  66.   }  
  67. }   
  68.   
  69. int main(){  
  70.     int H[10] = {3,1,5,7,2,4,9,6,10,8};  
  71.     cout<<"初始值：";  
  72.     print(H,10);  
  73.     HeapSort(H,10);  
  74.     //selectSort(a, 8);  
  75.     cout<<"结果：";  
  76.     print(H,10);  
  77.   
  78. }

4. 交换排序

4.1 冒泡排序

  1. void print(int *arr, int nCount, int n=0)
  2. {
  3. 	int i = 0;
  4. 	printf("%d==== ", n);
  5. 	while(i < nCount) printf("%2d  ", arr[i++]);
  6. 	printf("\n");
  7. }
  8.  
  9.  void BubbleSort(int *arr, int nCount)
  10.  {
  11. 	for(int i = 0; i < nCount; i++)
  12. 	{
  13. 		for(int j = 1; j < nCount-i; j++)
  14. 		{
  15. 			if (arr[j-1] > arr[j])
  16. 			{
  17. 				arr[j-1] += arr[j];
  18. 				arr[j] = arr[j-1] - arr[j];
  19. 				arr[j-1] = arr[j-1] - arr[j];
  20. 			}
  21. 		}
  22. 		print(arr, 10, i);
  23. 	}
  24.  }

4.2 快速排序

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. void print(int a[], int n){  
  5.     for(int j= 0; j<n; j++){  
  6.         cout<<a[j] <<"  ";  
  7.     }  
  8.     cout<<endl;  
  9. }  
  10.   
  11. void swap(int *a, int *b)  
  12. {  
  13.     int tmp = *a;  
  14.     *a = *b;  
  15.     *b = tmp;  
  16. }  
  17.   
  18. int partition(int a[], int low, int high)  
  19. {  
  20.     int privotKey = a[low];                             //基准元素  
  21.     while(low < high){                                   //从表的两端交替地向中间扫描  
  22.         while(low < high  && a[high] >= privotKey) --high;  //从high 所指位置向前搜索，至多到low+1 位置。将比基准元素小的交换到低端  
  23.         swap(&a[low], &a[high]);  
  24.         while(low < high  && a[low] <= privotKey ) ++low;  
  25.         swap(&a[low], &a[high]);  
  26.     }  
  27.     print(a,10);  
  28.     return low;  
  29. }  
  30.   
  31. void quickSort(int a[], int low, int high){  
  32.     if(low < high){  
  33.         int privotLoc = partition(a,  low,  high);  //将表一分为二  
  34.         quickSort(a,  low,  privotLoc -1);          //递归对低子表递归排序  
  35.         quickSort(a,   privotLoc + 1, high);        //递归对高子表递归排序  
  36.     }  
  37. }  
  38.   
  39. int main(){  
  40.     int a[10] = {3,1,5,7,2,4,9,6,10,8};  
  41.     cout<<"初始值：";  
  42.     print(a,10);  
  43.     quickSort(a,0,9);  
  44.     cout<<"结果：";  
  45.     print(a,10);  
  46.   
  47. }

优化快速排序

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. void print(int a[], int n){  
  5.     for(int j= 0; j<n; j++){  
  6.         cout<<a[j] <<"  ";  
  7.     }  
  8.     cout<<endl;  
  9. }  
  10.   
  11. void swap(int *a, int *b)  
  12. {  
  13.     int tmp = *a;  
  14.     *a = *b;  
  15.     *b = tmp;  
  16. }  
  17.   
  18. int partition(int a[], int low, int high)  
  19. {  
  20.     int privotKey = a[low];                 //基准元素  
  21.     while(low < high){                   //从表的两端交替地向中间扫描  
  22.         while(low < high  && a[high] >= privotKey) --high; //从high 所指位置向前搜索，至多到low+1 位置。将比基准元素小的交换到低端  
  23.         swap(&a[low], &a[high]);  
  24.         while(low < high  && a[low] <= privotKey ) ++low;  
  25.         swap(&a[low], &a[high]);  
  26.     }  
  27.     print(a,10);  
  28.     return low;  
  29. }   
  30.   
  31. void qsort_improve(int r[ ],int low,int high, int k){  
  32.     if( high -low > k ) { //长度大于k时递归, k为指定的数  
  33.         int pivot = partition(r, low, high); // 调用的Partition算法保持不变  
  34.         qsort_improve(r, low, pivot - 1,k);  
  35.         qsort_improve(r, pivot + 1, high,k);  
  36.     }   
  37. }   
  38. void quickSort(int r[], int n, int k){  
  39.     qsort_improve(r,0,n,k);//先调用改进算法Qsort使之基本有序  
  40.   
  41.     //再用插入排序对基本有序序列排序  
  42.     for(int i=1; i<=n;i ++){  
  43.         int tmp = r[i];   
  44.         int j=i-1;  
  45.         while(tmp < r[j]){  
  46.             r[j+1]=r[j]; j=j-1;   
  47.         }  
  48.         r[j+1] = tmp;  
  49.     }   
  50.   
  51. }  
  52.   
  53. int main(){  
  54.     int a[10] = {3,1,5,7,2,4,9,6,10,8};  
  55.     cout<<"初始值：";  
  56.     print(a,10);  
  57.     quickSort(a,9,4);  
  58.     cout<<"结果：";  
  59.     print(a,10);  
  60.   
  61. }

5. 归并排序

归并的合并方法：

  1. //将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]  
  2. void Merge(ElemType *r,ElemType *rf, int i, int m, int n)  
  3. {  
  4.     int j,k;  
  5.     for(j=m+1,k=i; i<=m && j <=n ; ++k){  
  6.         if(r[j] < r[i]) rf[k] = r[j++];  
  7.         else rf[k] = r[i++];  
  8.     }  
  9.     while(i <= m)  rf[k++] = r[i++];  
  10.     while(j <= n)  rf[k++] = r[j++];  
  11. }

归并的迭代算法

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. void print(int a[], int n){  
  5.     for(int j= 0; j<n; j++){  
  6.         cout<<a[j] <<"  ";  
  7.     }  
  8.     cout<<endl;  
  9. }  
  10.   
  11. //将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]  
  12. void Merge(ElemType *r,ElemType *rf, int i, int m, int n)  
  13. {  
  14.     int j,k;  
  15.     for(j=m+1,k=i; i<=m && j <=n ; ++k){  
  16.         if(r[j] < r[i]) rf[k] = r[j++];  
  17.         else rf[k] = r[i++];  
  18.     }  
  19.     while(i <= m)  rf[k++] = r[i++];  
  20.     while(j <= n)  rf[k++] = r[j++];  
  21.     print(rf,n+1);  
  22. }  
  23.   
  24. void MergeSort(ElemType *r, ElemType *rf, int lenght)  
  25. {   
  26.     int len = 1;  
  27.     ElemType *q = r ;  
  28.     ElemType *tmp ;  
  29.     while(len < lenght) {  
  30.         int s = len;  
  31.         len = 2 * s ;  
  32.         int i = 0;  
  33.         while(i+ len <lenght){  
  34.             Merge(q, rf,  i, i+ s-1, i+ len-1 ); //对等长的两个子表合并  
  35.             i = i+ len;  
  36.         }  
  37.         if(i + s < lenght){  
  38.             Merge(q, rf,  i, i+ s -1, lenght -1); //对不等长的两个子表合并  
  39.         }  
  40.         tmp = q; q = rf; rf = tmp; //交换q,rf，以保证下一趟归并时，仍从q 归并到rf  
  41.     }  
  42. }  
  43.  
  44. int main(){  
  45.     int a[10] = {3,1,5,7,2,4,9,6,10,8};  
  46.     int b[10];  
  47.     MergeSort(a, b, 10);  
  48.     print(b,10);  
  49.     cout<<"结果：";  
  50.     print(a,10);  
  51.   
  52. }

 

两路归并的递归算法

  1. void MSort(ElemType *r, ElemType *rf,int s, int t)  
  2. {   
  3.     ElemType *rf2;  
  4.     if(s==t) r[s] = rf[s];  
  5.     else  
  6.     {   
  7.         int m=(s+t)/2;          /*平分*p 表*/  
  8.         MSort(r, rf2, s, m);        /*递归地将p[s…m]归并为有序的p2[s…m]*/  
  9.         MSort(r, rf2, m+1, t);      /*递归地将p[m+1…t]归并为有序的p2[m+1…t]*/  
  10.         Merge(rf2, rf, s, m+1,t);   /*将p2[s…m]和p2[m+1…t]归并到p1[s…t]*/  
  11.     }  
  12. }  
  13. void MergeSort_recursive(ElemType *r, ElemType *rf, int n)  
  14. {   /*对顺序表*p 作归并排序*/  
  15.     MSort(r, rf,0, n-1);  
  16. }

6. 基数排序

  1. Void RadixSort(Node L[],length,maxradix)  
  2. {  
  3.    int m,n,k,lsp;  
  4.    k=1;m=1;  
  5.    int temp[10][length-1];  
  6.    Empty(temp); //清空临时空间  
  7.    while(k<maxradix) //遍历所有关键字  
  8.    {  
  9.      for(int i=0;i<length;i++) //分配过程  
  10.     {  
  11.        if(L[i]<m)  
  12.           Temp[0][n]=L[i];  
  13.        else  
  14.           Lsp=(L[i]/m)%10; //确定关键字  
  15.        Temp[lsp][n]=L[i];  
  16.        n++;  
  17.    }  
  18.    CollectElement(L,Temp); //收集  
  19.    n=0;  
  20.    m=m*10;  
  21.   k++;  
  22.  }  
  23. }

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/764231
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号