依旧的博客

技术学习

C++博客 首页 新随笔 联系 聚合 管理
  17 Posts :: 1 Stories :: 2 Comments :: 0 Trackbacks
1. 冒泡排序

 思想:

  1. 从现有元素中取出最大的元素,移到相应的位置,直到所有元素都就位。
  2. 通过比较和交换逐步调整现有序列,最终找出最大元素并使其就位。

 设计:

  输入是待排数组及其长度,输出排序后的数组。
  在冒泡过程中对数组的有序情况进行检查,在数组已经有序时便结束算法。

代码:

void BubbleSort(int nArray[], int nLength)
{
     bool bSorted = false;
   
     if (nArray == NULL)
         throw -1;
   
     if (nLength < 2)
         return;
   
    for (int i = nLength; !bSorted && i > 1; i--)
    {
         bSorted = true;
       
         for (int j = 1; j < i; j++)
        {
             if (nArray[j] < nArray[j-1])
            {
                 int n;
                 n = nArray[j];
                 nArray[j] = nArray[j-1];
                 nArray[j-1] = n;
       
                 bSorted = false;
             }//if
         }
     }

}

2. 双向冒泡排序

void BiBubbleSort(int nArray[], int nLength)
{
    int  low, high;
 
    if (nArray == NULL)
       throw -1;

    if (nLength < 2)
       returnt;

    low = 0;
    high = nLength - 1;
    while (low < high)
   {
       int t;

       t = low;
       for (int i = low; i < high; i++)
       {
           if (nArray[i] > nArray[i+1])
          {
              int n;
              n = nArray[i];
              nArray[i] = nArray[i+1];
              nArray[i+1] = n;

              t = i + 1;
          }
       }
       high = t - 1;

      t = high;
      for (int j = high; j > low; j--)
      {
          if (nArray[j] < nArray[j-1])
          {
             int n;
             n = nArray[j];
             nArray[j] = nArray[j-1];
             nArray[j-1] = n;
            
             t = j - 1;
          }
      }

     low = t + 1;

  }//while

}

3. 快速排序

 思想:

 选一个枢轴元素,把待排序列划分成两段,前一段不大于枢轴, 后一段不小于枢轴。如果这两段分别有序,原序列也随之有序。通过划分,一个段的排序可以转化为两个子段的排序,即同样性质但较小规模的问题。当段的长度为1时,本身是有序的,转化可以终止。

设计:

用一个递归函数来实现快速排序算法,递归终止条件是段的长度小于等于1。
一次划分过程设计如下:取段的第一个元素为枢轴,从最后一个元素向前与枢轴比较,发现小于枢轴的元素时,与枢轴交换位置,从第二个元素向后与枢轴比较,这样两端是已完成划分的部分,中间是待划分的部分,枢轴始终处于中间部分的一端,比较从另一端向该端进行,发现分类不同的元素就同枢轴交换。随着比较和交换的进行,中间部分不断收缩(每次长度缩短1),当收缩到长度为1时,划分终止。

实现要点:

递归函数的参数是待排序列及前后边界。
划分过程需要用两个变量记录中间部分的边界。

代码:

void QuickSort(int nArray[], int low, int high)
{
     int pivot = nArray[low];
     int i = low,j = high;
   
     if (high < low)
           return;   
    
     while (i < j)
     {
          while (i < j && nArray[j] >= pivot) j--;
          if (i < j) 
               nArray[i++] = nArray[j];
 
          while (i < j && nArray[i] <= pivot) i++;
          if (i < j) 
               nArray[j--] = nArray[i];
     }
    
     nArray[i] = pivot;
   
     QuickSort(nArray, low, i - 1);
     QuickSort(nArray, i + 1, high);
}

测试要点:

  1. 递归终止条件。必须是high < low,而不能是 high == low。递归的终止是很重要的边界情况,在实现之前有一个概念上的终止条件,但在实现时处理必须准确。终止条件和递推方式有关,需要结合实际的递推方式来确定。
  2. 递归的递推方式。
  3. 分划的终止条件。分划过程在i == j时终止,虽然在比较的过程中可能进行交换,但是每次未分划部分的长度减1,用该长度控制分划的终止。
  4. 分划过程中改变方向时的交接。

算法分析:

假设原序列有2n个元素,每次分划把一个段等分成两段,则经过n级递归算法终止,每一级递归的比较总数为n, 所以QuickSort()的时间为O(nlog(n)),这是平均情况。当原序列本身有序时,QuickSort()出现最坏情况,时间为O(n2)。

posted on 2006-05-09 16:37 依旧的博客 阅读(352) 评论(0)  编辑 收藏 引用 所属分类: 编程

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理