ソートアルゴリズムの概要---コード+パフォーマンス

// data_sort_alg.cpp :              。
//

#include "stdafx.h"
#include "sort_alg.h"
#include 
#include 

void show(std::vector &a)
{
	std::vector::iterator it=a.begin();

	while(it!=a.end())
	{
		std::cout< src(a,a+11);
	std::vector src1(b,b+12);					//heap sort
	std::vector src2(c,c+11);					//bucket sort
	std::vector src3(d,d+11);					//	radix sort
	
	std::cout<

#ifndef SORT_ALG_H
#define SORT_ALG_H
#include 

void bubble_sort(std::vector &a);
void shell_sort(std::vector &a);
void simple_sort(std::vector &a);
void merge_sort(std::vector &s,int b,int e);
void insert_sort(std::vector& a);
void heap_sort(std::vector &a);
void fast_sort(std::vector &a,int start,int end);
void bucket_sort(std::vector &a);
void radix_sort(std::vector &a);

#endif

#include "stdafx.h"
#include 
#include

#define STEP 5

/*==============================
1 name:bubble sort
--------------------------------
time complexity:
worst		average		best
O(n^2)	O(n^2)		O(n)
--------------------------------
space complexity:
O(1)
--------------------------------
stability:
stable
==============================*/

void bubble_sort(std::vector &a)
{
	for(int i=a.size()-1;i>0;i--)
	{
		for(int j=0;ja[j+1])
			{
				std::swap(a[j],a[j+1]);
			}
		}
	}
	return;
}

/*==============================
2 name:shell sort
--------------------------------
time complexity:
worst		average		best
O(ns)	O(nlogn)		O(n)
1 &a,int d)
{
	int i=d;
	while(i=j)
				{
					a[k]=a[k-d];
					k=k-d;
				}
				a[j]=temp;
				break;
			}	
			j=j+d;
		}
		i=i+d;
	}
	return;
}

void shell_sort(std::vector &a)
{
	int d=STEP;
	while(d!=0)
	{
		shell_sort_assist(a,d);
		d/=2;
	}
	return;
}

/*==============================
3 name:simple sort
--------------------------------
time complexity:
worst		average		best
O(n^2)	O(n^2)		O(n^2)
--------------------------------
space complexity:
O(1)
--------------------------------
stability:
unstable
==============================*/

void simple_sort(std::vector &a)
{
	std::vector::iterator it=a.begin(),it1,saveit;
	for(;it!=a.end();it++)
	{
		int min=*it;
		saveit=it;
		
		it1=it;
		while(it1!=a.end())
		{
			if(min>*it1)
			{
				min=*it1;
				saveit=it1;
			}
			it1++;
		}
		if(saveit!=it)
		{
			std::swap(*it,*saveit);
		}
	}
	return;
}

/*==============================
4 name: merge sort
--------------------------------
time complexity:
worst			average			best
O(nlogn)	O(nlogn)		O(nlogn)
--------------------------------
space complexity:
O(n)
--------------------------------
stability:
stable
==============================*/

void merge(std::vector &s,int b,int m,int e)
{
	int* temp=new int[e-b+1];

	int i=b;
	int j=m+1;
	int k=0;
	while(is[j])
		{
			temp[k++]=s[j++];
		}
		else
		{
			temp[k++]=s[i++];
		}
	}

	if(i &s,int b,int e)
{	
	int m;
	if(e>b)
	{
		m=(b+e)/2;
		merge_sort(s,b,m);
		merge_sort(s,m+1,e);
		merge(s,b,m,e);
	}
	return;
}

/*==============================
5 name: insert sort
--------------------------------
time complexity:
worst			average		best
O(n^2)		O(n^2)		O(n)
--------------------------------
space complexity:
O(1)
--------------------------------
stability:
stable
==============================*/

void insert_sort(std::vector& a)
{
	std::vector::iterator it,it1,it2;
	int temp;

	it=a.begin();
	while(it!=a.end())
	{
		it1=a.begin();
		while(it1!=it)
		{
			if(*it &a,int i,int end)
{
	int lchild=2*i;
	int rchild=2*i+1;
	int max=i;

	if(rchilda[max])
		{
			max=lchild;
		}
		if(a[rchild]>a[max])
		{
			max=rchild;
		}
		if(max!=i)
		{
			std::swap(a[max],a[i]);
			heap_adjust(a,max,end);
		}
	}
}

void build_heap(std::vector &a)
{
	int size=a.size()-1;
	for(int i=size/2;i>0;i--)
	{
		heap_adjust(a,i,size);
	}
	return;
}

void heap_sort(std::vector &a)
{
	build_heap(a);

	for(int i=a.size()-1;i>0;i--)
	{
		std::swap(a[1],a[i]);
		heap_adjust(a,1,i-1);
	}
}

/*==============================
7 name: fast sort
--------------------------------
time complexity:
worst				average			best
O(n^2)			O(nlogn)		O(nlogn)
--------------------------------
space complexity:
O(logn)
--------------------------------
stability:
unstable
==============================*/

void fast_sort(std::vector &a,int start,int end)
{
	int med=a[start];

	int i=start;
	int j=end;
	while(j>i)
	{
		while(a[j]>=med && j>i)
		{
			j--;
		}
		a[i]=a[j];
		while(a[i]<=med && j>i)
		{
			i++;
		}
		a[j]=a[i];
	}
	a[i]=med;

	if(start &a)
{
	std::vector<:vector>> bucket;
	bucket.resize(10);

	std::vector::iterator it=a.begin();
	while(it!=a.end())
	{
		int idx=*it/10;
		bucket[idx].push_back(*it);
		it++;
	}

	std::vector<:vector>>::iterator it1=bucket.begin();
	while(it1!=bucket.end())
	{
		simple_sort(*it1);
		it1++;
	}

	it=a.begin();
	it1=bucket.begin();
	while(it!=a.end() && it1!=bucket.end())
	{
		std::vector::iterator tmp_it=(*it1).begin();
		while(tmp_it!=(*it1).end())
		{
			*it=*tmp_it;
			tmp_it++;
			it++;
		}
		it1++;
	}
}

/*==============================
9 name: radix sort
--------------------------------
time complexity:
average		
O(2dn)
--------------------------------
space complexity:
O(n)
--------------------------------
stability:
stable
==============================*/

void refresh_data(std::vector &a, std::vector<:vector>> &sto)
{
	std::vector::iterator it,it1;
	std::vector<:vector>>::iterator it2;

	it=a.begin();
	it2=sto.begin();
	while(it!=a.end() && it2!=sto.end())
	{
		it1=(*it2).begin();
		while(it1!=(*it2).end())
		{
			*it=*it1;
			it1++;
			it++;
		}
		(*it2).clear();
		it2++;
	}

	return;
}

//suppose:there are no minus number
void radix_sort(std::vector &a)
{
	std::vector<:vector>> sto;
	sto.resize(10);
	int max=0;

	std::vector::iterator it=a.begin();
	while(it!=a.end())
	{
		int idx;

		if(max