【交换排序】 是一种主要以交换的方式对序列进行排序的方法。 其实排序的基本方法或手段主要就是比较和交换，像选择法等都借助了交换的手段，但都不是主要以交换为手段，在直接选择排序的时候，一轮比较就能确定最大元素的位置，然后再进行交换，也就是说这样的交换是“稳定”的。 【冒泡排序法】 也叫起泡排序法，过程跟气泡从水里冒出来类似。一轮交换对相邻元素进行比较，如果逆序则交换，作用只能使一个元素到达最终位置，而其它的交换是多余的，如果只进行比较而不交换的话，就跟直接选择排序法一样，不同的是，它是不稳定的。 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);//对右侧元素以同样的方法对待   } }

评论