/*****************************************************
copyright (C), 2014-2015, Lighting Studio. Co., Ltd.
File name：
Author:fhb Version:0.1 Date:
Description：
Funcion List:
*****************************************************/
#include <iostream>
#include <cstring>
#include<iomanip>
using namespace std;
template<class T>
void print(T keys[],int n)//输出字符串
{
for(int i = 0;i<n;i++)
{
cout<<setw(3)<<keys[i]<<" ";
}
cout<<endl;
}
/****************************************************************
直接插入排序：
第i次将a[i]插入到前面a[0]~a[i-1]的子序列中
时间复杂度：平均O(N^2),最好O(N),最坏O(N^2)
空间复杂度O(1),算法稳定
***************************************************************/
template<class T>
void insertSort(T keys[],int n)
{
for(int i = 1;i < n;i++)
{
T temp = keys[i];
int j;
for(j = i-1;j >=0&&temp<keys[j];j--)//若换成temp<=keys[j]，遇到相同的数会多交换一次
{
keys[j+1] = keys[j];
}
keys[j+1] = temp;
cout<<"第"<<i<<"次 temp="<<temp<<"\t";
print(keys,n);
}
}
/****************************************************************************
折半排序（二分插入排序）：
类似于直接插入排序，第i次将a[i]以二分查找的方法找到位置插入到前面的子序列中
时间复杂度：平均O(N^2),最好O(N),最坏O(N^2)
空间复杂度：O(1) 算法稳定
******************************************************************************/
template<class T>
void half_sort(T keys[],int n)
{
int i,j,low,mid,high;
T temp;
for(i=1;i<n;i++)
//最开始第一个元素仍然被看作已经排好的部分
{
low=0;
//最低位置
temp=keys[i];
//要插入的元素,已经排好序的最高位的下一位元素
high=i-1;
//最高位置
while(low<=high)
{
mid=(low+high)/2;
//折中,取中间位置
if(keys[mid]>temp)
//判断要插入的元素和中间元素的大小
high=mid-1;
//中间元素大,最高位置取当前中间位置的前一位,重新再求中间位置
else
low=mid+1;
//中间元素小,最高位置取当前中间位置的后一位,重新再求中间位置
}
cout<<"high="<<setw(2)<<high<<" low="<<setw(2)<<low<<" "; //查看每次寻找到位置后的高位和低位的位置
for(j=i-1;j>high;j--) //将(high+1)～i的所有元素后移一位
keys[j+1]=keys[j];
keys[high+1]=temp; //插入元素
print(keys,n);
}
}
/******************************************************************************
shell排序(希尔排序)：
将数据分成若干组，每组相隔一段距离，在一组内用直接插入排序，后每次距离减半至1
时间复杂度平均O(N^1.3),最好O(N),最坏O(N^2)
空间复杂度O(1),算法不稳定
********************************************************************************/
template<class T>
void shellSort(T keys[],int n)
{
for(int delta = n/2;delta>0;delta/=2)//若干次，控制增量每次减半
{
for(int i = delta;i < n;i++)//1次若干组，每组直接插入排序
{
T temp = keys[i];//当前待插元素
int j;
for(j = i-delta;j>=0&&temp<keys[j];j-=delta)
{
keys[j+delta] = keys[j];
}
keys[j+delta] = temp;
}
cout<<"delta = "<<delta<<" ";
print(keys,n);
}
}
/******************************************************************************
冒泡排序：
。。。。。。。。。
时间复杂度：平均O(N^2)，最好O(N),最坏O(N^2)
空间复杂度O(1),算法稳定
*********************************************************************************/
template<class T>
void bubbleSort(T keys[],int n)
{
bool exchange = true;//交换标志
for(int i = 1;i < n&&exchange;i++)//如果上次没有交换过数据，则停止
{
exchange = false;
for(int j = 0;j<n-1;j++)
{
if(keys[j]>keys[j+1])
{
T temp = keys[j];
keys[j] = keys[j+1];
keys[j+1] = temp;
exchange = true;
}
}
cout<<"第"<<i<<"次： ";
print(keys,n);
}
}
/*************************************************************************
快速排序：
在序列中选择一个值作基准，小于基准的元素换到序列前，大于的换到序列后，
再对子序列分别再进行快速排序
时间复杂度：平均O(N*lgN)，最好O(N*lgN)，最坏O(N^2)
空间复杂度：O(lgN），算法不稳定（？）
*****************************************************************************/
template<class T>
void quickSort(T keys[],int n,int begin,int end)
{
if(begin>=0&&begin<n&&end>=0&&end<=n&&begin<end)//序列有效
{
int i = begin,j = end;
T vot= keys[i];
while(i != j)
{
while(i<j&&vot<=keys[j])
{
j--;
}
if(i<j)
{
keys[i++]=keys[j];
}
while(i<j&&keys[i]<=vot)
{
i++;
}
if(i<j)
{
keys[j--]=keys[i];
}
}
keys[i] = vot;
cout<<begin<<".."<<end<<",vot="<<vot<<", ";
print(keys,n);
quickSort(keys,n,begin,j-1);
quickSort(keys,n,i+1,end);
}
}
template<class T>
void quickSort(T keys[],int n)
{
quickSort(keys,n,0,n-1);
}
/**********************************************************************
直接选择排序：
第i次从后n-i个元素序列中选择最小的元素放到第i个位置
时间复杂度：平均O(N^2)，最好O(N^2)，最坏O(N^2)
空间复杂度：O(1)，算法不稳定
***********************************************************************8*/
template<class T>
void selectSort(T keys[],int n)
{
for(int i=0;i<n-1;i++)
{
int min = i;
for(int j = i+1;j<n;j++)
{
if(keys[j]<keys[min])
{
min = j;
}
}
if(min!=i)
{
T temp = keys[i];
keys[i] = keys[min];
keys[min] = temp;
}
cout<<"第"<<i+1<<"次 min="<<min<<",\t";
print(keys,n);
}
}
/********************************************************************************
堆排序：
1、将一个数据序列建成最小堆，根节点值最小
2、选择排序，每次将最小值交换到后面，再将其余值调整成堆，直到子序列长度为1
时间复杂度：平均O(N*lgN)，最好O(N*lgN)，最坏O(N*lgN)
空间复杂度：O(1)，算法不稳定
*********************************************************************************/
template<class T>
void sift_minheap(T keys[],int n,int begin,int end)
{
int parent = begin,child = 2*parent+1;
T value = keys[parent];
while(child<=end)
{
if(child<end&&keys[child]>keys[child+1])
child++;
if(value>keys[child])
{
keys[parent] = keys[child];
parent = child;
child = 2*parent+1;
}
else
break;
}
keys[parent] = value;
cout<<"sift "<<begin<<".."<<end<<" ";
print(keys,n);
}
template<class T>
void heapSort_down(T keys[],int n)
{
for(int i=n/2-1;i>=0;i--)
sift_minheap(keys,n,i,n-1);
for(int i = n-1;i > 0;i--)
{
T temp = keys[0];
keys[0] = keys[i];
keys[i] = temp;
sift_minheap(keys,n,0,i-1);
}
}
/************************************************************************************
归并排序：
将n个长度为1的排序子序列，反复将相邻的子序列归并成一个排序的子序列，知道合并成1个序列;
时间复杂度：平均O(N*lgN)，最好O(N*lgN)，最坏O(N*lgN);
空间复杂度：O(N),算法稳定;
***************************************************************************************/
template<class T>
void merge(T X[],int len,T Y[],int begin1,int begin2,int n)
{
int i = begin1,j = begin2,k = begin1;
while(i<begin1+n&&j<begin2+n&&j<len)
{
if(X[i] < X[j])
{
Y[k++] = X[i++];
}
else
{
Y[k++] = X[j++];
}
}
while(i<begin1+n&&i<len)
{
Y[k++] = X[i++];
}
while(j<begin2+n&&j<len)
{
Y[k++] = X[j++];
}
}
template<class T>
void mergepass(T X[],int len,T Y[],int n)
{
cout<<"子序列长度n="<<n<<" ";
for(int i = 0;i<len;i+=2*n)
{
merge(X,len,Y,i,i+n,n);
}
print(Y,len);
}
template<class T>
void mergeSort(T X[],int len)
{
T *Y = new T[len];
int n = 1;
while(n < len)
{
mergepass(X,len,Y,n);
n*=2;
if(n<len)
{
mergepass(Y,len,X,n);
n*=2;
}
}
}
//主函数
int main()
{
int keys[]={32,26,87,72,26,17};
cout<<"关键字序列： ";
print(keys,6);
//insertSort(keys,6);
//half_sort(keys,6);
//shellSort(keys,6);
//quickSort(keys,6);
//bubbleSort(keys,6);
//selectSort(keys,6);
//heapSort_down(keys,6);
mergeSort(keys,6);
return 0;
}
