排序算法思想和实现(代码)(二)

时间:2020-12-13 22:08:52

1. 快速排序算法

 

  1. /* --------------------------------------------------------------------------**
  2.  函数名称:  ms_quick_sort
  3.  参数含义:  int data[]  (i/o)   排序数组
  4.             int low     (i)     数组低序坐标
  5.             int high    (i)     数组高序坐标
  6.             int order   (i)     序列方式 (0 为递减,1 为递增)
  7.  功能简称:  快速排序。
  8.  功能描述:  将数组data[]中的范围在low到high的数据按制定的方式进行排序。
  9.  实现描述:  通过一趟排序将待排的记录分割为独立的两部分,其中一部分记录的关键字
  10.             均比另一部分的关键字小,然后分别对这两部分记录继续进行排序,以达到
  11.             整个序列有序。
  12.  创建日期:  2008年12月28日。
  13. / ---------------------------------------------------------------------------*/
  14. void ms_quick_sort(int data[], int low, int high, int order)
  15. {
  16.     int i;
  17.     int j;
  18.     int pivot;
  19.     bool exchg = false;
  20.     if ( low < high )
  21.     {
  22.         pivot = data[low];
  23.         i = low;
  24.         j = high;
  25.         while ( i<j )
  26.         {
  27.             // 高序数据的比较
  28.             while ( i<j )
  29.             {
  30.                 exchg = false;
  31.                 ms_data_order(exchg, pivot, data[j], order);
  32.                 if ( !exchg )
  33.                 {
  34.                     j--;
  35.                 }
  36.                 else
  37.                 {
  38.                     data[i++] = data[j];
  39.                     break;
  40.                 }
  41.             }   
  42.     
  43.             // 低序数据的比较
  44.             while ( i<j )
  45.             {
  46.                 exchg = false;
  47.                 ms_data_order(exchg, data[i], pivot, order);
  48.                 if ( !exchg )
  49.                 {
  50.                     i++;
  51.                 }
  52.                 else
  53.                 {
  54.                     data[j--] = data[i];
  55.                     break;
  56.                 }
  57.             }
  58.         }
  59.         data[i] = pivot;
  60.         ms_quick_sort(data, low, i-1, order);
  61.         ms_quick_sort(data, i+1, high, order);
  62.     }
  63. }