标题:实现交换排序,冒泡,快速排序


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

首先来看著名的交换排序算法:冒泡法。冒泡法的排序思想是:从第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(n2),它是稳定排序。

 

快速排序的思想是:在当前无序区R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为X),用此基准将当前无序区划分为左右两个较小的无序区:R[1..I-1]R[I+1..H],且左边的无序子区中数据元素均小于等于基准元素,右边的无序子区中数据元素均大于等于基准元素,而基准X则位于最终排序的位置上,即R[1..I-1]X.KeyR[I+ 1..H](1IH),当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(n2)。对于大的、乱数序列一般相信是最快的已知排序。待排记录序列按关键字顺序有序时,直接插入排序和起泡排序能达到O(n)的时间复杂度,而对于快速排序而言,这是最不好的情况。对于很小的数组(如N<=20),快速排序不如插入排序好。



看文字不过瘾?点击我,进入周哥教IT视频教学
麦洛科菲长期致力于IT安全技术的推广与普及,我们更专业!我们的学员已经广泛就职于BAT360等各大IT互联网公司。详情请参考我们的 业界反馈 《周哥教IT.C语言深学活用》视频

我们的微信公众号,敬请关注