课程作业6（归并排序 冒泡排序 插入排序 选择排序）
/*归并排序 冒泡排序 插入排序 选择排序*/
//主程序
#include<iostream>
#include<vector>
using std::vector;
using std::cout;
using std::endl;
using std::swap;
#include"bubble_sort.h"
#include"insert_sort.h"
#include"select_sort.h"
#include"merge_sort.h"
template<typename T>
void print(vector<T>& a)
{
for (int i = 0; i != a.size(); i++)
{
cout << a[i] << " ";
}
cout << endl;
}
int main()
{
//vector<int> v = { 34,8,64,51,32,21 };
//vector<int> v = { 6,5,4,3,2,1 };
vector<int> v = { 34,8,64,51,32,21,67,34,8,64,51,32,21,12,34,8,64,51,32,21,34 };
//vector<int> v = { 34,34,34,34,34,34,34 };
//vector<char> v = { 'd','s','A','P','k','a','T' };
//int a[] = { 34,8,23,51,32,23,21 };
//vector<int> v(&a[0],&a[0]+7);
cout << "原始排序：";
print(v);
cout << "归并排序：";
merge_sort(v);
print(v);
cout << "冒泡排序：";
bubble_sort(v);
print(v);
cout << "插入排序：";
insert_sort(v);
print(v);
cout << "选择排序：";
select_sort(v);
print(v);
system("pause");
return 0;
}
/********************bubble_sort.h*******************/
#pragma once
//冒泡排序算法（全部元素）
template<typename T>
void bubble_sort(vector<T>& a)
{
bubble_srt(a, 0, a.size());
}
//冒泡
template<typename T>
void bubble(vector<T>& a, int first, int last)
{
for (int i = first + 1; i != last; i++)if (a[i - 1] > a[i]) swap(a[i - 1], a[i]);
}
//冒泡排序算法
template<typename T>
void bubble_srt(vector<T>& a, int first, int last)
{
for (int i = last; i != first; i--)bubble(a, first, i);
}
/********************merge_sort.h*******************/
#pragma once
#include<deque>
using std::deque;
#include<algorithm>
//合并排序算法a[first,last)
template<typename T>
void merge_sort(vector<T>& a, int first, int last)
{
if (first<last-1)
{
int mid = (first + last) / 2;
merge_sort(a, first, mid);
merge_sort(a, mid, last);
merge(a, first, mid, last);
}
}
//合并a[first,mid)和a[mid,last)
template<typename T>
void merge(vector<T>& a, int first, int mid, int last)
{
deque<T> dq;
int k = first;
for (int i = first; i < mid; i++)dq.push_back(a[i]);
for (int i = last-1; i >= mid; i--)dq.push_back(a[i]);
while (!dq.empty())
{
if (dq.front()<dq.back())
{
a[k++] = dq.front();
dq.pop_front();
}
else
{
a[k++] = dq.back();
dq.pop_back();
}
}
}
//归并排序算法（全部元素）
template<typename T>
void merge_sort(vector<T>& a)
{
merge_sort1(a, 0, a.size());
}
//自底向上合并排序
template<typename T>
void merge_sort1(vector<T>& a, int first, int last)
{
for (int i = 1; i <= last-first; i=i+i)//子区间长度倍增
{
for (int j = first; j <= last-i; j+=i+i)
{
merge(a, j, j + i, std::min(j + i + i, last));
}
}
}
//自然合并排序
/********************insert_sort.h*******************/
#pragma once
//插入元素a[last]到有序区间[first,last)
template<typename T>
void insert(vector<T>& a, int first, int last)
{
T x = a[last];
int i = last;
while ((i != first) && (x < a[i - 1]))//注意前后顺序
{
a[i] = a[i - 1]; i--;
}
a[i] = x;
}
//插入排序算法
template<typename T>
void insert_sort(vector<T>& a, int first, int last)
{
for (int i = first+1; i != last; i++)
{
insert(a, first, i);
}
}
//插入排序算法（全部元素）
template<typename T>
void insert_sort(vector<T>& a)
{
insert_sort(a, 0, a.size());
}
/********************select_sort.h*******************/
#pragma once
//确定[first,last)中最小元素位置
template<typename T>
int min_elem(vector<T>& a, int first, int last)
{
int pos = first;
for (int i = first + 1; i != last; i++)if (a[i] < a[pos])pos = i;
return pos;
}
//选择排序算法
template<typename T>
void select_sort(vector<T>& a, int first, int last)
{
for (int i = first; i != last-1; i++)
{
int j = min_elem(a, i, last);
if(i!=j)swap(a[i], a[j]);
}
}
//选择排序算法（全部元素）
template<typename T>
void select_sort(vector<T>& a)
{
select_sort(a, 0, a.size());
}
课程作业7（快速排序 随机快速排序）
/* 快速排序 随机快速排序*/
//主程序
#include<iostream>
#include<vector>
using std::vector;
using std::cout;
using std::endl;
using std::swap;
#include"insert_sort.h"
#include"qsort.h"
#include"rand_qsort.h"
template<typename T>
void print(vector<T>& a)
{
for (int i = 0; i != a.size(); i++)
{
cout << a[i] << " ";
}
cout << endl;
}
//快速排序
int main()
{
vector<int> v = { 34,8,64,51,32,21,67,34,8,64,51,32,21,12,34,8,64,51,32,21,34 };
cout << "原始排序：";
print(v);
cout << "快速排序：";
rand_qsort(v);
print(v);
vector<int> v1 = { 34,8,64,51,32,21,67,34,8,64,51,32,21,12,34,8,64,51,32,21,34 };
cout << "原始排序：";
print(v1);
cout << "随机快速排序：";
rand_qsort(v1);
print(v1);
system("pause");
return 0;
}
/********************qsort.h*******************/
#pragma once
const int threshold =1;
//区间分割
template<typename T>
int partition(vector<T>& a, int first, int last,T pivot)
{
while (true)
{
last--;
while (a[first] < pivot)first++;
//while ((a[first] <= pivot) && (first<last))first++;//error
while (pivot < a[last])last--;
//while ((pivot < a[last])&&(first<last))last--;//error
if (!(first < last))
return first;
swap(a[first], a[last]);
first++;
}
}
/*template<typename T>
int partition(vector<T>& a, int first, int last, T pivot)
{
last--;
while (last >first)
{
while ((a[first] < pivot))first++;//error && (first<last)
while ((pivot < a[last]))last--;//error&&(first<last)
swap(a[first], a[last]);
}
return first;
}*/
//递归快速排序ooooooo
template<typename T>
void qsort(vector<T>& a, int first, int last)
{
while (last - first > threshold)
{
T pivot = median(a[first], a[(first + last) / 2], a[last - 1]);
//T pivot = a[last-1];
//T pivot = a[first];//error
int cut = partition(a, first, last, pivot);
qsort(a, cut, last);
last = cut;
}
insert_sort(a, first, last);
}
//取三点的中位数
template<typename T>
const T& median(const T& a, const T& b, const T& c)
{
if (a < b)
if (b < c)return b;
else if (a < c)return c;
else return a;
else if (a < c)return c;
else if (b < c)return c;
else return b;
}
template<typename T>
void qsort(vector<T>& a)
{
qsort(a, 0, a.size());
}
/********************rand_qsort.h*******************/
#pragma once
#include <ctime>
using std::rand;
template<typename T>
void rand_qsort(vector<T>& a, int first, int last)
{
while (last - first > threshold)
{
T pivot = a[random(first,last)];
int cut = partition(a, first, last, pivot);
rand_qsort(a, cut, last);
last = cut;
}
insert_sort(a, first, last);
}
template<typename T>
void rand_qsort(vector<T>& a)//随机化快速排序
{
rand_qsort(a, 0, a.size());
}
int random(int first, int last)
{
//根据系统时间设置随机数种子
srand(time(NULL));//(unsigned)
return first+rand()%(last-first);
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
