|
排序法 |
最差时间分析 | 平均时间复杂度 | 稳定度 | 空间复杂度 |
| 冒泡排序 | 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 (n的1.2次幂) | 不稳定 | O(1) |
| 归并排序 | O(nlogn) | O(n*log2n) | 稳定 | O(n) |
| 基数排序 | O(d(n+rd)) | O (d(n+rd)) | 稳定 | O(rd) |
注：选择排序：在找那个最小的元素时，如果是从前向后找，那么就是不稳定的；如果是从后往前找，那么就是稳定的。一般的书上都是从前往后找，所以一般当作是不稳定的。
1.数组的大小是2的幂，这样分下去始终可以被2整除。假设为2的k次方，即k=log2(n).
2.每次我们选择的值刚好是中间值，这样，数组才可以被等分。
第一层递归，循环n次，第二层循环2*(n/2)......
所以共有n+2(n/2)+4(n/4)+......+n(n/n)=n+n+n+......+n=k*n=log2(n)*n
所以共有O(log2(n)*n)
其他的情况只会比这种情况差，最差的情况是每次选择到的middle都是最小值或最大值，那么他将变成交换法（由于使用了递归，情况更糟）。但是你认为这种情况发生的几率有多大？大多数情况下，快排总是最好的。
稳定性：
首先，排序算法的稳定性大家应该都知道，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。
其次，说一下稳定性的好处。排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，对基于比较的排序算法而言，元素交换的次数可能会少一些。
（1）冒泡排序
冒泡排序就是把小的元素往前调或者把大的元素往后调，比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的，如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定的排序算法。
（2）选择排序
选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依此类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。例如5 8 5 2 9，第一趟选择第一个5和2交换，第一个5在第二个5的后面了。
（3）插入排序
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插排是稳定的。
（4）快速排序
快排有两个方向，左边的i下标一直往右走，当a[i]<=a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组的第0个元素，而右边的j下标一直往右走，当a[j]>a[center_index]。如果i和j都走不动了，i<=j，交换a[i]和a[j]，重复上面的过程，直到i>j。交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列5 3 3 4 3 8 9 10 11，现在中枢元素和3（第五个元素）交换就会把元素3的稳定性打乱。
（5）归并排序
归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素（认为直接有序）或者2个序列（1次比较和交换），然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏?没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。
（6）基数排序
#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;//有交换，设定标志位，以便上面的判断
}
}
}
}
}
//基本思想是找一个关键字，小于它的放在它的左边，大于的放在右边；对两边的序列继续排
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;
}
}
//基本思想：先由给出的关键字来建立一个堆，然后用
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); //对余下的部分建堆
}
}