《MY数据结构与算法》----八大排序算法（含优化与算法拓展）

素颜马尾好姑娘i 2022-05-18 11:00 209阅读 0赞

一：八大排序算法比较

20150821162219212

二：八大排序算法代码实现，以及优化与拓展

冒泡排序：优化为增加哨兵。
选择排序：
希尔排序：
插入排序：
归并排序：拓展为应用在求逆序对
快速排序：拓展为求数组中第n大的值。
堆排序： 拓展为求数组中前n个大的值。
归并排序，快速排序，堆排序，的优化方法之一都可以在数组元素个数小于15的时候用插入排序。（代码未添加）
快速排序：可优化为当重复的元素过多的时候选择3路归并（代码未添加）
快速排序：变形可变为不使用递归，而使用栈和队列的方式（代码未添加）
具体我在此博客看到有介绍。可作参考：https://blog.csdn.net/Vichyssoise/article/details/78922138

  1. #include <iostream>
  2. #include <stdlib.h>
  4. #define ARR_MAX_COUNT 10
  5. #define p() cout << "-----------------------------\n";
  6. #define __PRINT_FUNC() cout << __func__ << endl;
  8. using namespace std;
  10. class TEST_SORT_ARR {
  12. private :
  13.     int arr[ARR_MAX_COUNT];
  14.     int inversion_num;
  16. public  :
  17.     TEST_SORT_ARR() ;
  18.     ~TEST_SORT_ARR() ; 
  19.     void prn();
  21.     void bubbling_sort();
  22.     void bubbling_sort_add_sentry_optimize();
  23.     void select_sort();
  24.     void insert_sort();
  25.     void shell_sort();
  26.     void merge_sort();
  27.     int  merge_sort_app_get_inversion();
  28.     void quick_sort();
  29.     int  quick_sort_app_return_value_of_nox(int id);
  30.     void heap_sort();
  32. private :
  33.     void __shellInsertSort(int arr[] , int n , int dk);
  34.     void __merge_sort(int arr[] , int l , int r);
  35.     void __merge(int arr[] , int l , int middle ,int  r) ;
  36.     void __merge_sort_app_inversion_num(int arr[] , int l , int r);
  37.     void __merge_app_inversion_num(int arr[] , int l , int middle ,int  r) ;
  38.     void __quick_sort(int arr[] , int l , int r);
  39.     int  __quick(int arr[] , int l ,int r);
  40.     void __heap_sort(int arr[] , int count);
  41.     int  __parent(int n);
  42.     int  __leftchild(int n);
  43.     int  __rightchild(int n);
  44.     void __shift_down(int arr[] , int len , int i);
  45. };
  47. int TEST_SORT_ARR::__parent(int n) {
  48.     return (n-1)/2;
  49. }
  50. int TEST_SORT_ARR::__leftchild(int n) {
  51.     return 2*n+1;
  52. }
  53. int TEST_SORT_ARR::__rightchild(int n) {
  54.     return 2*n+2;
  55. }
  57. void TEST_SORT_ARR::__shift_down(int arr[] , int len , int i) {
  58.     int lchild = __leftchild(i);
  59.     int rchild = __rightchild(i);
  60.     int nmax;
  62.     if( lchild <  len && arr[lchild] > arr[i] )    
  63.         nmax = lchild;    
  64.     else 
  65.         nmax = i;
  67.     if( rchild < len && arr[rchild] > arr[nmax] )
  68.         nmax = rchild;
  70.     if( nmax != i)
  71.     {
  72.         swap(arr[i] , arr[nmax]);
  73.         __shift_down(arr, len, nmax);
  74.     }
  75. }
  77. void TEST_SORT_ARR::__heap_sort(int arr[] , int n) {
  78.     for(int i = __parent(n-1) ; i>=0 ; i--)
  79.     {
  80.         __shift_down(arr,n,i);
  82.     }
  83.     for(int i = n-1 ; i>0 ; i-- ) {
  84.         swap(arr[0] , arr[i] );
  85.         n--;
  86.         __shift_down(arr,n,0);
  87.     }
  88. }
  90. void TEST_SORT_ARR::heap_sort() {
  91. __PRINT_FUNC();
  92.     __heap_sort(arr,ARR_MAX_COUNT);
  93. }
  96. int TEST_SORT_ARR::quick_sort_app_return_value_of_nox(int id) {
  97. __PRINT_FUNC();
  98.     int middle = __quick(arr, 0 , ARR_MAX_COUNT-1);
  99.     while( middle != id) {
  100.         if( middle>id) {
  101.             middle = __quick(arr,0,middle-1);
  102.         }
  103.         else {
  104.             middle = __quick(arr,middle+1,ARR_MAX_COUNT-1);
  105.         }
  106.     }
  107.     return arr[middle];
  108. }
  110. int TEST_SORT_ARR::__quick(int arr[] , int l , int r) {
  111.     if( l>=r )
  112.         return l;
  113.     swap(arr[l] , arr[ rand()%(r-l+1)+l ]);
  115.     int v = arr[l];
  117.     int i = l+1;
  118.     int j = r;
  119.     while( true ) {
  120.         while( i<=r && arr[i]<= v) {
  121.             i++;
  122.         }
  123.         while( j>=l+1 && arr[j]>= v) {
  124.             j--;
  125.         }
  126.         if( i>=j)
  127.             break;
  128.         swap(arr[i] , arr[j]);
  129.         i++;
  130.         j--;
  133.     }
  134.     swap(arr[j] , arr[l]);
  135.     return j;
  136. }
  139. void TEST_SORT_ARR::__quick_sort(int arr[] , int l , int r) {
  140.     if( l>=r )
  141.         return ;
  142.     int middle = __quick(arr, l , r);
  143.     __quick_sort(arr,l,middle-1);
  144.     __quick_sort(arr,middle+1 , r);
  145. }
  147. void TEST_SORT_ARR::quick_sort() {
  148. __PRINT_FUNC();
  149.     __quick_sort(arr,0,ARR_MAX_COUNT-1);
  150. }
  157. void TEST_SORT_ARR::__merge_app_inversion_num(int arr[] , int l , int middle ,int  r) {
  158.     int tempArr[r-l+1] ;
  159.     for( int i=l ; i<=r ; i++){
  160.         tempArr[i-l] = arr[i];    
  161.     }
  163.     int lp = l,lr=middle+1;
  164.     for( int i=l ; i<=r ; i++) {
  165.         if( lp > middle ) {
  166.             arr[i] = tempArr[lr-l];
  167.             lr++;
  168.         }
  169.         else if( lr > r ) {
  170.             arr[i] = tempArr[lp-l];
  171.             lp++;
  172.         }
  173.         else if( tempArr[lr-l] <= tempArr[lp-l] ) {
  174.             arr[i] = tempArr[lr-l];    
  175.             inversion_num += (middle-lp+1);
  176.             lr++;
  177.         }
  178.         else {
  179.             arr[i] = tempArr[lp-l];
  180.             lp++;
  181.         }
  182.     }    
  183. }
  185. void TEST_SORT_ARR::__merge_sort_app_inversion_num(int arr[] , int l , int  r) {
  186.     if( l>=r)
  187.         return ;
  188.     int middle = (r-l)/2+l;
  189.     __merge_sort_app_inversion_num(arr,l,middle);
  190.     __merge_sort_app_inversion_num(arr,middle+1,r);
  191.     __merge_app_inversion_num(arr,l,middle,r);    
  192. }
  194. int  TEST_SORT_ARR::merge_sort_app_get_inversion() {
  195. __PRINT_FUNC();
  196.     inversion_num = 0;
  197.     __merge_sort_app_inversion_num(arr,0,ARR_MAX_COUNT-1);
  198.     return inversion_num;
  199. }
  201. void TEST_SORT_ARR::__merge(int arr[] , int l , int middle ,int  r) {
  202.     int tempArr[r-l+1] ;
  203.     for( int i=l ; i<=r ; i++){
  204.         tempArr[i-l] = arr[i];    
  205.     }
  207.     int lp = l,lr=middle+1;
  208.     for( int i=l ; i<=r ; i++) {
  209.         if( lp > middle ) {
  210.             arr[i] = tempArr[lr-l];
  211.             lr++;
  212.         }
  213.         else if( lr > r ) {
  214.             arr[i] = tempArr[lp-l];
  215.             lp++;
  216.         }
  217.         else if( tempArr[lr-l] < tempArr[lp-l] ) {
  218.             arr[i] = tempArr[lr-l];    
  219.             lr++;
  220.         }
  221.         else {
  222.             arr[i] = tempArr[lp-l];
  223.             lp++;
  224.         }
  225.     }    
  226. }
  228. void TEST_SORT_ARR::__merge_sort(int arr[] , int l , int  r) {
  229.     if( l>=r)
  230.         return ;
  231.     int middle = (r-l)/2+l;
  232.     __merge_sort(arr,l,middle);
  233.     __merge_sort(arr,middle+1,r);
  234.     __merge(arr,l,middle,r);    
  235. }
  238. void TEST_SORT_ARR::merge_sort() {
  239. __PRINT_FUNC();
  240.     __merge_sort(arr,0,ARR_MAX_COUNT-1);
  241. }
  245. void TEST_SORT_ARR::__shellInsertSort(int arr[] , int n , int dk) {
  246.     for(int i=dk ; i<ARR_MAX_COUNT ; i+=dk) {
  247.         int flag = i-dk;
  248.         int val = arr[i];
  249.         while( (flag>=0)&&(arr[flag]>val))
  250.         {
  251.             arr[flag+dk] = arr[flag];
  252.             flag -= dk;    
  253.         }
  254.         arr[flag+dk] = val;
  255.     }
  256. }
  258. void TEST_SORT_ARR::shell_sort() {
  259. __PRINT_FUNC();
  260.     int dk = ARR_MAX_COUNT/2;
  261.     while(dk>=1) {
  262.         __shellInsertSort(arr,ARR_MAX_COUNT,dk);
  263.         dk /= 2;
  264.     }
  265. }
  269. void TEST_SORT_ARR::insert_sort() {
  270. __PRINT_FUNC();
  271.     for(int i=1; i<ARR_MAX_COUNT ; i++) {
  272.         int flag = i-1;
  273.         int val = arr[i];
  274.         // ba dangqianzhi tichulai baocunwei val;
  275.         // ranhou qianmian de meigezhi he val bijiao , bitada,jiu wanghou yidong 
  276.         while((flag>=0) && (arr[flag]>val))
  277.         {
  278.             arr[flag+1] = arr[flag];
  279.             flag--;
  280.         }
  281.         //zuihou zai jiang val fuzhi guoqu ;
  282.         arr[flag+1] = val;
  283.     }
  285. }
  287. void TEST_SORT_ARR::select_sort() {
  288. __PRINT_FUNC();
  289.     for(int i=0 ; i<ARR_MAX_COUNT-1 ; i++) {
  290.         for(int j=i+1 ; j<ARR_MAX_COUNT ; j++)
  291.         {
  292.             if(arr[i] > arr[j])
  293.                 swap(arr[i],arr[j]);
  294.         }
  295.     }
  296. }
  298. void TEST_SORT_ARR::prn() {
  299.     for(int i=0 ; i<ARR_MAX_COUNT ; i++)
  300.         cout << arr[i] << " ";
  301.     cout << endl;
  302. }
  304. TEST_SORT_ARR::TEST_SORT_ARR() {
  305.     for(int i=0 ; i<ARR_MAX_COUNT ; i++) {
  306.         arr[i] = rand()%88;
  307.     }
  308. }
  309. TEST_SORT_ARR::~TEST_SORT_ARR() {}
  313. void TEST_SORT_ARR::bubbling_sort(){
  314.     for(int i=0 ; i<ARR_MAX_COUNT-1; i++) {
  315.         for(int j=0 ; j<ARR_MAX_COUNT-1-i ; j++) {
  316.             if(arr[j] > arr[j+1])
  317.                 swap(arr[j],arr[j+1]);
  318.         }
  319.     }
  320. }
  322. void TEST_SORT_ARR::bubbling_sort_add_sentry_optimize(){
  323.     int flag = 0;
  324.     for(int i=0 ; i<ARR_MAX_COUNT-1; i++) {
  325.         for(int j=0 ; j<ARR_MAX_COUNT-1-i ; j++) {
  326.             if(arr[j] > arr[j+1]) {
  327.                 swap(arr[j],arr[j+1]);
  328.                 flag = 1;
  329.             }
  330.         }
  331.         if( 1==flag ) {
  332.             flag = 0;
  333.         }
  334.         else {
  335.             return ;
  336.         }
  337.     }
  338. }
  341. int main() 
  342. {
  343.     TEST_SORT_ARR  d;
  344.     d.prn();
  345.     d.merge_sort();
  346.     d.prn();
  347.     p();
  349.     TEST_SORT_ARR  h;
  350.     h.prn();
  351.     h.heap_sort();
  352.     h.prn();
  353.     p();
  355.     TEST_SORT_ARR  f;
  356.     f.prn();
  357.     f.quick_sort();
  358.     f.prn();
  359.     p();
  362.     TEST_SORT_ARR  g;
  363.     p();
  364.     g.prn();
  365.     cout << "no.3 is :" << g.quick_sort_app_return_value_of_nox(3) << endl;
  366.     g.prn();
  367.     p();
  369.     TEST_SORT_ARR  e;
  370.     e.prn();
  371.     cout << "ni xu dui num : " << e.merge_sort_app_get_inversion() <<endl;
  372.     e.prn();
  373.     p();
  375.     TEST_SORT_ARR  a;
  376.     a.prn();
  377.     a.bubbling_sort();
  378.     a.prn();
  379.     p();
  381.     TEST_SORT_ARR  c;
  382.     c.prn();
  383.     c.shell_sort();
  384.     c.prn();
  385.     p();
  387.     TEST_SORT_ARR  b;
  388.     b.prn();
  389.     b.insert_sort();
  390.     b.prn();
  391.     p();
  393.     TEST_SORT_ARR  aa;
  394.     aa.prn();
  395.     aa.bubbling_sort_add_sentry_optimize();
  396.     aa.prn();
  397.     p();
  400.     TEST_SORT_ARR  ab;
  401.     ab.prn();
  402.     ab.select_sort();
  403.     ab.prn();
  404.     p();
  405. }

发表评论

表情：
评论列表 （有 0 条评论，209人围观）

还没有评论，来说两句吧...

相关阅读

    相关 数据结构与算法之八大排序

    排序是编程的基础，在程序中会经常使用，好的排序方法可以帮助你提高程序运行的效率，所以学好排序，打好基础，对于程序的优化会手到擒来。无论你的技术多么强，如果没有基础也强不到哪去

    野性酷女野性酷女/ 0 赞/ 367 阅读