#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/*
*冒泡
*从未排序序列首元素开始，依次与相邻元素进行比较，将较小的放在前面
**/
void bubble(vector<int> &m)
{
int len = m.size();
for (int i = 0; i < len;i++)
{
for (int j = i;j < len;j++)
{
if (m[i] > m[j])
{
swap(m[i],m[j]);
}
}
}
}
/*
*选择
*选择序列中最小元素放在已排序部分，在未排序序列中再选择次小的放入已排序序列后
**/
void selectsort(vector<int>&m)
{
int len = m.size();
for (int i = 0;i < len -1;i++)
{
int x = i;
for (int j = i+1;j < len;j++)
{
if (m[x] > m[j])
{
x = j;
}
}
if(x != i)
swap(m[x],m[i]);
}
}
/*
*快速
*在序列中选择一个元素，一般以起始元素作为基准，把所有比该值小的放左边，比该值大的放右边，以此递归
**/
void quick(vector<int>&m,int start,int end)
{
int i = start;
int j = end;
int x = m[i];
if(start >= end)
return;
while(i != j)
{
while(i < j && m[j] >= x)
j--;
if(i < j)
m[i] = m[j];
while(i < j && m[i] <= x)
i++;
if(i < j)
m[j] = m[i];
}
m[i] = x;
quick(m,start,i-1);
quick(m,i+1,end);
}
/*
*插入
*从第一个元素开始，该元素可被认为是已经被排序，取出下一个元素，在已经排序好的元素中从后向前扫描，如果已经排序元素大于新元素，将已排序元素移到下一个位置
*重复上述步骤，直到找到已排序的元素小于或者等于新元素的位置，新元素插入到该位置后
**/
void insert(vector<int>&m)
{
int len = m.size();
for(int i = 1;i < len;i++)//未排序
{
int get = m[i];
int j = i - 1;
while(j >= 0 && m[j] > get)
{
m[j+1] = m[j];
j--;
}
m[j+1] = get;//找到了，进行插入
}
}
/*
*希尔排序
*插入排序改进版，增大插入步伐
**/
void hillsort(vector<int>&m)
{
int len = m.size();
int h = 0;
while(h < len)
{
h = h * 3 + 1;
}
while(h >= 1)
{
for(int i = h;i < len;i++)
{
int j = i - h;
int get = m[i];
while(j >= 0 && m[j] > get)
{
m[j+h] = m[j];
j = j - h;
}
m[j+h] = get;
}
h = (h - 1) / 3;
}
}
/*
*归并排序
*将两个已排序的子序列合并为一个序列
**/
void merge(vector<int>&m,int left,int mid,int right)
{
int len = right - left + 1;
int * temp = new int[len];
int index = 0;
int i = left;
int j = mid + 1;
while( i <= mid && j <= right)
temp[index++] = (m[i] <= m[j]) ? m[i++] : m[j++];
while(i <= mid)
temp[index++] = m[i++];
while(j <= right)
temp[index++] = m[j++];
for (int i = 0;i < len;i++)
{
m[left++] = temp[i];
}
}
void mergesort(vector<int> &m,int left,int right)
{
if (left == right)
{
return;
}
int mid = (left + right) / 2;
mergesort(m,left,mid);
mergesort(m,mid+1,right);
merge(m,left,mid,right);
}
/*
*堆排序
*构造大顶堆，作为初始无序区
**/
void swap(vector<int> &m,int i,int j)
{
int temp = m[i];
m[i] = m[j];
m[j] = temp;
}
void adjustheap(vector<int> &m,int i, int size)
{
int temp = m[i];//先取出当前元素
for (int k = i * 2 + 1;k < size;k = k * 2 + 1)//从i节点的左子节点开始，也就是2*i+1处开始
{
if(k+1 < size && m[k] < m[k+1])//如果左子节点小于右子节点，k指向右子节点
k++;
if (m[k] > temp)//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
{
m[i] = m[k];
i = k;
}
else
break;
}
m[i] = temp;//将temp值放到最终的位置
}
void heapsort(vector<int> &m)
{
for (int j = m.size() / 2 - 1;j >= 0;j--)//构造大顶堆
{
adjustheap(m,j,m.size());//从第一个非叶子节点从下至上，从右至左调整结构
}
for (int i = m.size() - 1;i > 0;i--)//调整元素，交换元素
{
swap(m,0,i);
adjustheap(m,0,i);
}
}
int main()
{
vector<int>m;
m.push_back(2);
m.push_back(4);
m.push_back(1);
m.push_back(7);
m.push_back(0);
m.push_back(5);
//bubble(m);
//selectsort(m);
//quick(m,0,m.size()-1);
//insert(m);
//mergesort(m,0,m.size()-1);
heapsort(m);
for (int i = 0;i < m.size();i++)
{
cout<<m[i];
}
cout<<endl;
return 0;
}
网友评论