---

交换排序的基本思想是：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。

首先来看著名的交换排序算法：冒泡法。冒泡法的排序思想是：从第n个元素开始，扫描数组，比较相邻两个元素，如果次序相反则交换。如此反复，直到没有任何两个违反相反原则的元素。

下面是冒泡法的算法实现：

 

void bubblesort(int a[], int n)

{

     int i, j, tmp;

     for (i = 0; i < n-1; i++)

    {

         for (j = n; j >= i+1; j--)

        {

              if (a[j] < a[j-1])

            {

                   tmp = a[j];

                   a[j] = a[j-1];

                   a[j-1] = tmp;

              }

         }

     }

}

 

冒泡排序的时间复杂度为O(n²)，它是稳定排序。

 

快速排序的思想是：在当前无序区R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为X)，用此基准将当前无序区划分为左右两个较小的无序区：R[1..I-1]和R[I+1..H]，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即R[1..I-1]≤X.Key≤R[I+ 1..H](1≤I≤H)，当R[1..I-1]和R[I+1..H]均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。

下面是快速排序算法的C代码实现：

 

void quicksort(int a[], int s, int t)

{

     int i, j;

     i = s;

     j = t;

     if (s < t)

    {

         do

        {

              a[0] = a[s];

              while (j > i && a[j] >= a[0])

                   j--;

              if (i < j)

             {

                   a[i] = a[j];

                   i++;

              }

              while (i < j && a[i] <= a[0])

                   i++;

              if (i < j)

             {

                   a[j] = a[i];

                   j--;

              }

         } while (i < j)

         a[i] = a[0];

         quicksort(a, s, i - 1);

         quicksort(a, j + 1, t);

     }

}

 

快速排序的时间复杂度为O(nlogn)，最坏情况为O(n²)。对于大的、乱数序列一般相信是最快的已知排序。待排记录序列按关键字顺序有序时，直接插入排序和起泡排序能达到O(n)的时间复杂度，而对于快速排序而言，这是最不好的情况。对于很小的数组（如N<=20），快速排序不如插入排序好。