依旧的博客

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. 分划过程中改变方向时的交接。

算法分析：

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