首页 > 代码库 > 数据结构复习：交换排序原理及C++实现
数据结构复习：交换排序原理及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 #endif110 111 112 //exchangeSortTest113 #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++数据结构原理与经典问题求解
数据结构复习：交换排序原理及C++实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。