数据结构复习：交换排序原理及C++实现

1. 交换排序的基本思想

两两比较key值，如果发生逆序（排列的顺序与期望的顺序相反）就交换，知道所有对象都排序完毕！常见的3种交换排序算法：冒泡排序，shaker排序和快速排序。

2. 冒泡排序

设待排序列中有 n 个对象，首先比较对象v[n-1]和v[n-2], 如果v[n-1] < v[n-2],则交换v[n-1]和v[n-2]，然后对v[n-i]和v[n-i-1]进行同样操作，知道对v[1]和v[0]进行完操作，每一次冒泡，使得值小的对象前移动，如此重复，直至有序，图解如下：

3.Shaker排序（双向冒泡排序）

此种排序是对冒泡排序的改进，冒泡排序每次只能从一个方向进行遍历，而shaker排序每次遍历包括两个方向，先从前向后，再从后往前双向交替，效率上较冒泡排序有所改进，图解如下：

4.快速排序

快速排序采用的是一种分治的思想：取待排序对象序列中的某个对象为基准（任意取一个），按照其他对象与该基准对象的大小关系，将整个序列划分为左右两个子序列，其中左侧子序列中所有对象值都小于或者等于基准值，右侧对象序列中的所有对象值都大于基准值，然后对左右这两个子序列重复上述操作（递归），直至子序列为空为止！还是比较容易理解，这里就不画图了。

5.C++实现

  1 #ifndef EXCHANGESORT_H
  2 #define EXCHANGESORT_H
  3 #include <vector>
  4 #include <iostream>
  5 using std::vector;
  6 using std::cout;
  7 using std::endl;
  8 template <typename T>
  9 class ExchangeSort
 10 {
 11 private:
 12     int len;
 13     vector<T> list;
 14 public:
 15     /*
 16      * Construction function
 17     */
 18     ExchangeSort(vector<T> _list, int _len)
 19     {
 20         for (int i = 0; i < _len; ++i) list.push_back(_list[i]);
 21         this->len = _len;
 22     }
 23 
 24     /*
 25     * bubbleSort functions
 26     */
 27     void bubbleSort()
 28     {
 29         for (int i = 0; i < len; ++i)
 30             for (int j = i + 1; j < len; ++j)
 31                 if (list[i] > list[j]) swap(i, j);
 32     }
 33 
 34     /*
 35     * shakerSort functions
 36     */
 37     void shakerSort()
 38     {
 39         int i, left = 0;
 40         int shift = 0;
 41         int right = len - 1;
 42         while (left < right)
 43         {
 44             for (i = left; i < right; ++i) // From left to right
 45             {
 46                 if (list[i] > list[i + 1])
 47                 {
 48                     swap(i, i + 1);
 49                     shift = i;// Record the last index
 50                 }
 51             }// end for
 52             right = shift;
 53             for (i = right; i > left; --i)//From right to left
 54             {
 55                 if (list[i] < list[i - 1])
 56                 {
 57                     swap(i, i - 1);
 58                     shift = i;
 59                 }
 60             }// end for
 61             left = shift;
 62         }//end while
 63     }
 64 
 65 
 66     
 67     /*
 68     * quick sort
 69     */
 70     void quickSort(int left, int right)
 71     {
 72         int i = left;
 73         int j = right;
 74         int pivot = list[left];
 75         while (i < j)
 76         {
 77             while (i < j && list[j] >= pivot) --j; // Search the number less than pivot
 78             if (i < j) swap(i, j);
 79             while (i < j && list[i] <= pivot) ++i; // Search the number larger than pivot
 80             if (i < j) swap(i, j);
 81         }
 82         if (i != left) quickSort(left, i - 1);
 83         if (j != right) quickSort(j + 1, right);
 84     }
 85     /*
 86     * Exchange two elements of list
 87     */
 88     void swap(int i, int j)
 89     {
 90         T temp = list[i];
 91         list[i] = list[j];
 92         list[j] = temp;
 93     }
 94 
 95     /*
 96     * Display the sorted result
 97     */
 98     void out()
 99     {
100         for (int i = 0; i < len; ++i)
101         {
102             cout << list[i] << " ";
103             if ((i + 1) % 18 == 0) cout << endl;
104         }
105         cout << endl;
106     }
107 };
108 
109 #endif
110 
111 
112 //exchangeSortTest
113 #include "ExchangeSort.h"
114 #include <vector>
115 using namespace std;
116 
117 const unsigned numEle = 8;
118 int data[numEle] = {1,5,7,3,8,2,6,4};
119 
120 
121 int main()
122 {
123     vector<int> testData;
124     for (unsigned i = 0; i < numEle; ++i) testData.push_back(data[i]);
125 
126     ExchangeSort<int> testBubble(testData, numEle);
127     cout << "Before sorting: ";
128     testBubble.out();
129     testBubble.bubbleSort();
130     cout << "After sorting with bubbleSort: ";
131     testBubble.out();
132     
133 
134     ExchangeSort<int> testShaker(testData, numEle);
135     cout << "Before sorting: ";
136     testShaker.out();
137     testShaker.shakerSort();
138     cout << "After sorting with shakerSort: ";
139     testShaker.out();
140 
141     ExchangeSort<int> testQuick(testData, numEle);
142     cout << "Before sorting: ";
143     testQuick.out();
144     testQuick.quickSort(0, numEle-1);
145     cout << "After sorting with testQuick: ";
146     testQuick.out();
147 
148     return 0;
149 }

6.参考文献

左飞：C++数据结构原理与经典问题求解