常用排序算法之交换排序 ( 冒泡排序、快速排序 )

利用交换数据元素的位置进行排序的方法称为交换排序。

常用的交换排序方法有冒泡排序和快速排序。快速排序是一种分区交换排序方法。

冒泡排序

方法：设数组a中存放了n个数据元素，循环进行n-1次如下的排序过程：第1次时，依次比较相邻两个数据元素 a[i].key 和 a[i+1].key ( i = 0,1,2,...,n-1 )，若为逆序，即 a[i].key > a[i+1].key ，则交换两个数据元素，否则不交换，这样数值最大的数据元素将被放置在 a[n-1] 中。第2次时，数据元素个数减1，即数据元素个数为 n-1 ，操作方法和第1次类似，这样整个n个数据元素集合中的数值较大的数据元素将被放置在 a[n-2] 中。当第 n-1 次结束时，整个n个数据元素集合中次小的数据元素将被放置在 a[1] 中，a[0] 中放置了最小的数据元素。有些待排序的数据元素序列已基本有序，这样实际上并不需要全部执行完上述过程数据元素已经全部排好序。在算法设计中设计一个flag变量，flag变量用于标记本次交换排序过程中是否有交换动作，若本次交换排序过程没有交换动作，则说明数据元素已全部排好序，就可提前结束排序过程。

C++实现：

BubbleSort.cpp

 1 void BubbleSort( DataType a[], int n )
 2 {
 3     int i, j, flag = 1;
 4     DataType temp;
 5 
 6     for ( i = 1; i < n && flag = 1; i ++ )
 7     {
 8         flag = 0;
 9         for ( j = 0; j < n; j -- )
10         {
11             if ( a[j].key > a[j+1].key )
12             {
13                 flag = 1;
14                 temp = a[j+1];
15                 a[j+1] = a[j];
16                 a[j] = temp;
17             }
18         }
19     }
20 }

时间复杂度：最好与最坏。

最好：数据元素集合已全部排好序，这里循环 n-1 次，每次循环因没有交换动作而退出。因此冒泡排序算法最好情况的时间复杂度为 O(n) 。

最坏：数据元素集合全部逆序排放，这时循环 n-1 次，比较次数和交换移动次数共计为：

    比较次数 = (i=n-1,i=1)i = n(n-1)/2 。

    移动次数 = 3(i=n-1,i=1)i = 3n(n-1)/2 。

因此冒泡排序算法最坏的时间复杂度为 O(n^2) 。

空间复杂度： O(1) 。

---------------------------------------------------------------------------------

快速排序

一种二叉树结构的交换排序方法。

方法：设数组a中存放了n个数据元素，low为数组的低端下标，high为数组的高端下标，从数组a中任取一个元素(通常取a[low])作为标准，调整数组a中各个元素的位置，使排在标准元素前面元素的关键字小于标准元素的关键字，排在标准元素后面元素的关键字均大于标准元素的关键字。这样一次过程结束之后，一方面将标准元素放在了未来排好序的数组中该标准元素应位于的位置上，另一方面将数组中的元素以标准元素为中心分成了两个子数组，位于标准元素左边子数组中元素的关键字均小于标准元素的关键字，位于标准元素右边子数组中元素的关键字均大于标准元素的关键字。对这两个子数中的元素分别再进行方法类同的递归快速排序。递归算法的出口条件是 high > low 。

C++实现：

QuickSort.cpp

 1 void QuickSort( DataType a[], int low, int high )
 2 {
 3     int i = low, j = high;
 4     DataType temp;
 5 
 6     while ( i < j )
 7     {
 8         while ( i < j && temp.key <= a[j].key )
 9             j --;
10         if ( i < j )
11         {
12             a[i] = a[j];
13             i ++;
14         }
15 
16         while ( i < j && a[j].key < temp.key )
17             i ++;
18         if ( i < j )
19         {
20             a[j] = a[i];
21             j --;
22         }
23     }
24     a[i] = temp;
25 
26     if ( low < i )  QuickSort(a, low, i-1);
27     if ( i < high)  QuickSort&(a, j+1, high);
28 }