#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
//折半插入排序
入口参数:long* Array:指向数组的指针;long key:关键字;long Start:开始索引;long End:结束索引
int HalfSearch(long* Array,long Key,long Start,long End){
long half=(Start+End)/2; //找折半点
if(Array[half]<=Key && Array[half+1]>Key ) //找到了插入的位置
return half+1;
if(Array[half]>Key) //折半点比关键字大,在左边找
return HalfSearch(Array,Key,Start,half-1);
else
return HalfSearch(Array,Key,half+1,End); //在右边找
}
void HalfInsSort(long* array/*数组*/,long leng/*数组长度*/){
long temp;
long i,j,Pos;
for(i=2;i<=leng;i++){
temp=array[i];//从第二个数开始
j=i-1;//找到前一个数
if((temp<array[j]) && (j>=1)){//如果此处不是TEMP 的正确位置,则折半查找
Pos=HalfSearch(array,temp,1,j);
while(Pos<=j && Pos!=-1)//移动元素,腾出空间
{array[j+1]=array[j];
j--;}
array[Pos]=temp;//放入适当的位置
}
}
}
//希尔排序,参数解释同上
void ShellSort(long* array,long leng){
int temp,step;
step=leng/2;//以长度的1/2做为步长,也可以自己设定一个步长序列
while(step!=0){
for(int i=step+1;i<=leng;i++){//又i来控制循环 /*因为从最小步长前面开始排序,前面的
temp=array[i];//从步长数的第二个开始 /*已经有序了,所以象插入排序一样,只是将后面的
int j=i-step;//找到了前一个的位置 /*小的数插入到前面适当的位置*/
while(temp<array[j] && j>=1){
array[j+step]=array[j];//大的数交换到后面,temp保存小的数
j=j-step;
}
array[j+step]=temp;//小的数放到适当的位置
}
step=step/2;//再找下一个步长
}
}
//二叉树排序
//1.数组表示
/*如果恰好此树是一个从大到小的序列,则需要的树空间为2的元素次方个存储空间*/
/*空间的浪费太大,不划算*/
void BinaryTree(long* btree,/*排序的数组*/long* array,/*原始数组*/long leng/*数组长度*/){
/*建树的过程就是排序的过程*/
long i;
long parent;
btree[1]=array[1];/*头接点赋值*/
for(i=2;i<=leng;i++){
parent=1; //确保每次的找插入节点都从ROOT开始
while(btree[parent]!=0){
if(array[i]>btree[parent]) //插入节点大于父节点,则作右孩子
parent=parent*2+1;
else
parent=parent*2; //插入节点小于父节点,则作左孩子
}
btree[parent]=array[i]; //找到正确的位置后插入。返回开始处再找;
}
}
void Inorder(long* btree,/*树的头接点*/long pos,/*找到的索引*/long leng/*数组长*/){ //树的中序遍历*/
if(btree[pos]!=0 && pos<=leng){ //由于是数组表示,所以加上此条件
Inorder(btree,pos*2,leng); //遍历左孩子
if(btree[pos]!=0)
cout<<btree[pos]<<" "; //打印节点
Inorder(btree,pos*2+1,leng);//遍历右孩子
}
}
//2.链表表示
typedef struct Node{//基本数据结构
Node* left;
long data;
Node* right;
}_Node;
Node* CreateTree(long* array,/*给定的元素*/long leng/*长度*/){
long item;
int leftflag;
Node *root,*parent,*Left=NULL,*Right=NULL;
root=new Node;/*建头接点*/
root->data=array[1];
root->left=root->right=NULL;
for(item=2;item<=leng;item++){
Node* newnode=new Node; //分配节点
newnode->data=array[item];
newnode->left=newnode->right=NULL;
parent=root;
while(parent!=NULL){
if(newnode->data<parent->data){//如果小于节点的值,到左子树
if(parent->left==NULL)
Left=parent; //左子树为空,保存父节点
parent=parent->left;
leftflag=1;}
else{ if(parent->right==NULL)//右子树为空,保存父节点
Right=parent;
parent=parent->right;
leftflag=0;
}
};
if(leftflag==1)//在左子树
Left->left =newnode;
else//在右子树
Right->right =newnode;
}
if(root!=NULL)
return root;
else
return NULL;
}
void Inorder(Node* root){//中序遍历
if(root==NULL)
return;
Inorder(root->left);
cout<<root->data<<" ";
Inorder(root->right);
}
//交换排序
//1.冒泡排序
void BubbleSort(long* array,long leng){
long i,j;
int finish=0; //是否交换的标志,如果上一次有交换,此标志为0,下一次
long temp; //可继续比较,如果没有交换,则表示排序完成,不须再比较。这是一个控制排序
//次数的小技巧,可减少排序的时间。
while(!finish){
finish=1; //假定已完成;
for(j=leng;j>=1;j--){//控制次数
for(i=1;i<=j-1;i++){//交换的索引
if(array[i]>array[i+1]){
temp=array[i];
array[i]=array[i+1];
array[i+1]=temp;
finish=0;//有交换,设定标志位,以便上面的判断
}
}
}
}
}
//2.快速排序
//基本思想是找一个关键字,小于它的放在它的左边,大于的放在右边;对两边的序列继续排
void QuickSort(long* array,long low,long high){
long key;
long scanup,scandown;
long temp;
if((high-low)<=0) //设定第一个返回条件
return;
if(high-low==1) //相临的两个数要比较是否要交换
if(array[high]>array[low]){//符合条件,交换
temp=array[high];
array[high]=array[low];
array[low]=temp;
return;
}
key=array[low];//一般以最小索引的数做关键字
scanup=low;
scandown=high;
do{
while(array[scandown]>=key && scanup<scandown)//向前找到小于关键字的数
scandown--;
array[scanup]=array[scandown]; //交换到前面
while(array[scanup]<=key && scanup<scandown)//向后找到大于关键字的数
scanup++;
array[scandown]=array[scanup]; //交换到后面
}while(scandown!=scanup); //直到前后的扫描键在同一位置为关键字的地方
array[scanup]=key;
QuickSort(array,low,scandown-1);//向前快排
QuickSort(array,scanup+1,high);//向后快排
}
/*选择排序*/
//1.直接选择排序
void SelectSort(long* array,long leng){
long temp,k;
long i,j;
for(i=1;i<leng;i++){
k=i; //给临时变量赋值;
for(j=i+1;j<=lung s++)
if(array[k]>=array[j])
k=j; //在此循环内找到当前最小值的下标
//只做一次交换;
temp=array[k];
array[k]=array[i];
array[i]=temp;
}
}
//2.堆排序
//基本思想:先由给出的关键字来建立一个堆,然后用
void CreateHeap(long* heap,/*数组表示堆的指针*/long root/*头接点的序号*/,long leng){//建堆
long child;//孩子接点
long temp;
int finish=0;
child=2*root; //找到子节点
temp=heap[root];
while(child<leng && finish==0){//在子接点的序号小于长度时或不需要交换时退出循环
if(child <leng)
if(heap[child]<heap[child+1])
child++; //选出最大的子节点由于交换
if(temp >= heap[child]) //交换完成
finish=1;
else{
heap[child/2]=heap[child]; //交换
child=2*child; //再找下层,直到不满足循环的条件
}
}
heap[child/2]=temp; //节点放入适当的位置
}
void HeapSort(long* heap,long leng){//排序
long i,temp;
for(i=(leng/2);i>=1;i--) //建成大根堆
CreateHeap(heap,i,leng);
for(i=leng;i>=1;i--){ //排序的方法是:由大根堆的最后一个开始,最后一个是大根堆里关键值最小的一个,它和第一个数交换,将最大的数交换到最后,然后在对剩下的n-1个数进行建堆,重复此过程,使得大的数不断放到后面,最后使整个序列有序。
temp=heap[i];
heap[i]=heap[1];
heap[1]=temp;
CreateHeap(heap,1,i-1); //对余下的部分建堆
}
}
排序效率比较
排序法
|
最差时间分析 |
平均时间复杂度 |
稳定度 |
空间复杂度 |
冒泡排序 |
O(n2) |
O(n2) |
稳定 |
O(1) |
快速排序 |
O(n2) |
O(n*log2n) |
不稳定 |
O(log2n)~O(n) |
选择排序 |
O(n2) |
O(n2) |
稳定 |
O(1) |
二叉树排序 |
O(n2) |
O(n*log2n) |
不一顶 |
O(n) |
插入排序
|
O(n2) |
O(n2) |
稳定 |
O(1) |
堆排序 |
O(n*log2n) |
O(n*log2n) |
不稳定 |
O(1) |
希尔排序 |
O |
O |
不稳定 |
O(1) |
|