【交换排序】
是一种主要以交换的方式对序列进行排序的方法。

其实排序的基本方法或手段主要就是比较和交换，像选择法等都借助了交换的手段，但都不是主要以交换为手段，在直接选择排序的时候，一轮比较就能确定最大元素的位置，然后再进行交换，也就是说这样的交换是“稳定”的。

【冒泡排序法】
也叫起泡排序法，过程跟气泡从水里冒出来类似。一轮交换对相邻元素进行比较，如果逆序则交换，作用只能使一个元素到达最终位置，而其它的交换是多余的，如果只进行比较而不交换的话，就跟直接选择排序法一样，不同的是，它是不稳定的。

void bubblesort(int n,list r)
{
  for (i=1;i=n-1,i++)
  {
    flag=1;//标记是否有交换
    for (j=1;j=n-1;j++)
      if (r[j].key>r[j+1].key)
      {
      flag=0;
      swap(r[j],r[j+1]);//交换相邻元素
      }
    if(flag)return;//如果一轮比较没有元素交换则说明整体有序，直接退出
  }
}

【快速排序法】
也是一种交换排序法，实际上它是冒泡法的改进。

【算法】
思想是：一次划分使整个元素部分有序，即从序列中任选一个元素，然后对其它元素进行这样的划分，使得所有比它小（大）的元素在左侧而所有比它大（小）的元素在右侧，然后用分治的思想对左右侧的序列同样的处理，直到只有一个元素为止。

一次划分的算法如下：
int quickpass(list r,int low,int high)
{
  int i=low; j=high; x=r[i];  //置初值，i指最左端，j指最右端，选第i个元素为划分比较元素x
  while (i<j)
  {  
    while ((r[j].key>=x.key)&&(i<j))--j;
      //自尾端进行比较，因为i处为空
    if (i<j)
    {
      r[i]=r[j]; i++;//填入i处
      while ((r[i].key<=x.key&&(i<j)++i;
      //自首端进行比较，j处已空
      if (i<j){r[j]=r[i];j--;}
    }
  }
  r[i]=x;//一趟快速排序结束，将x移至正确位置
  return i;//返回划分比较元素的位置
}

整个快速排序的过程用递归算法设计，思想当然是分治的思想：
void quicksort(list r,int low,int high)
//对r[low]，r[low+1],...r[high]进行快速排序
{
  if(low<high)
  {
    int k;
    k=quickpass(r,low,high);//一次划分
    quicksort(r,low,k-1);//对左侧元素以同样的方法对待
    quicksort(r,k+1,high);//对右侧元素以同样的方法对待
  }
}

评论