重点：插入排序、选择排序、冒泡、快速排序。 要求：
被排序的对象由计算机随机生成。算法中增加比较次数和移动次数的统计功能。main.h #include"sort.h" void main() {
vector<Etype> sqlist; random_device rd; //随机种子生成器 seed_seq sd = { rd(), rd(), rd() };//种子序列 default_random_engine rng{ sd };//随机数生成器 CreateRandomSqlist(20, sqlist,rng);//创建内容随机的表 PrintKey(sqlist);//打印表 Count Count1= InsertSort<vector<Etype>, Count>(sqlist);//插入排序 cout << "插入排序:比较次数" << Count1.compare << " " <<"移动次数"<< Count1.motion<<'\n'; PrintKey(sqlist); shuffle(sqlist.begin(), sqlist.end(), rng);//打乱原表 PrintKey(sqlist); Count Count2 = SlectSort< vector<Etype>, Count>(sqlist); cout << "选择排序：比较次数" << Count2.compare << " " << "移动次数" << Count2.motion << '\n'; PrintKey(sqlist); shuffle(sqlist.begin(), sqlist.end(), rng);//打乱原表 PrintKey(sqlist); Count Count3 = BubbleSort<vector<Etype>, Count>(sqlist);//冒泡排序 cout << "冒泡排序：比较次数" << Count3.compare << " " << "移动次数" << Count3.motion << '\n'; PrintKey(sqlist); shuffle(sqlist.begin(), sqlist.end(), rng);//打乱原表 PrintKey(sqlist); Count Count4 = QuickSort(sqlist); cout << "快速排序：比较次数" << Count4.compare << " " << "移动次数" << Count4.motion << '\n'; PrintKey(sqlist); system ("pause");}
sort.h
#pragma once #include <vector #include <iterator #include <iostream #include <random #include<algorithm using namespace std;
//顺序表储存数据类型 struct Etype { int key; string name; }; //统计 比较和移动 次数 struct Count { size_t compare; size_t motion; };
void CreateRandomSqlist(size_t length, vector& sqlist, default_random_engine rng); void PrintKey(vector sqlist); template <typename T, typename Tr> Tr InsertSort(T& L);//直接插入排序 template <typename T, typename Tr> Tr SlectSort(T& L);//简单选择排序 template <typename T, typename Tr>Tr BubbleSort(T& L);//冒泡排序
//创建指定长度,vector顺序表,数据key随机 void CreateRandomSqlist(size_t length, vector &sqlist, default_random_engine rng) {
uniform_int_distribution<> dist(0, 200);//随机数均匀分布范围 Etype q; for (size_t i = 0; i <= length; i++)//第0个作插入排序时暂存器，实际创建 length+1个节点 { sqlist.emplace_back( q = { dist(rng) });//随机数节点压入表 }}
//打印顺序表key值 void PrintKey(vector sqlist) { for(vector::iterator iter = sqlist.begin()+1; iter != sqlist.end(); ++iter)//第0个作排序时暂存器，不打印 { cout << (*iter).key << " ";// *解除迭代器 & 引用 } cout << ‘\n’; //可以使用范围 for 循环更加简单地完成相同操作 //for (auto num : sqlist) 相当于 auto && __range = (sqlist); for （auto __begin = __range.begin(), __end = __range.end(); __begin != __end; ++__begin） //{ // // no deference operator // cout << num.key << " "; //} }
//直接插入排序 template <typename T, typename Tr> Tr InsertSort(T& L) {
int i, j; Tr count1 = { 0,0 }; for (i = 2; i < L.size(); ++i) { count1.compare++; if (L[i].key < L.data()[i - 1].key)//i比前一个小 需插入有序子表 { L[0] = L[i];//将待插入的记录暂存到监视哨 L[i] = L[i - 1];//L[i - 1]后移 count1.motion = count1.motion + 2; for (j = i - 2; L[0].key < L[j].key; --j)//从i的前一个的前一个开始向前寻找插入点 { count1.compare++; L[j + 1] = L[j];//逐个后移 count1.motion++; }; count1.compare++;//插入点循环内最后一次比较 L[j + 1] = L[0];//插入 count1.motion++; } } return count1;}
//简单选择排序 template <typename T, typename Tr> Tr SlectSort(T& L) { size_t i,j,small; size_t l = L.size(); Tr count1 = { 0,0 }; for ( i = 1; i < l; i++) { small = i; for (j = i+1; j< l; j++ ) { count1.compare++; if (L[j].key<L[small].key) { small = j; } } if (small!=i) {//交换 L[0] = L[i]; L[i] = L[small]; L[small] = L[0]; count1.motion = count1.motion +3; } } return count1; }
//冒泡排序 template <typename T, typename Tr> Tr BubbleSort(T& L) { bool flag = 1; size_t l = L.size(); size_t i, j; Tr count1 = { 0,0 }; for (i = 1; ((i < l-1)&&flag); i++) { flag = 0; for (j = 1; j <l-i; j++) { count1.compare++; if (L[j].key > L[j+1].key) { flag = 1; L[0] = L[j]; L[j] = L[j + 1]; L[j + 1] = L[0];//交换 count1.motion = count1.motion + 3; } } } return count1; }
//快速排序
auto Partition(vector& sqlist, size_t low, size_t high, Count &CountQ) {
sqlist[0] = sqlist[low]; auto pivotkey = sqlist[low].key; while (low < high) { while ((low < high) && (sqlist[high].key >= pivotkey)) { CountQ.compare++; --high; } sqlist[low] = sqlist[high]; while ((low < high) && (sqlist[low].key <= pivotkey)) { CountQ.compare++; ++low; } sqlist[high] = sqlist[low]; CountQ.motion = CountQ.motion + 2; } sqlist[low] = sqlist[0]; return low;}
void QSort(vector& sqlist, size_t low, size_t high, Count& CountQ) { if (low < high) { auto pivotloc = Partition(sqlist, low, high, CountQ); QSort(sqlist, low, pivotloc-1, CountQ); QSort(sqlist, pivotloc+1, high, CountQ); } }
auto QuickSort(vector& sqlist) { Count CountQ = { 0,0 }; QSort(sqlist, 1, sqlist.size() - 1, CountQ); return CountQ; }
