内部排序
代码更新地址:https://github.com/myourys/Algorithm/blob/master/InternalSort.cpp
BubbingSort 冒泡排序 O(n^2)
SimpleSelectSort 简单选择排序 O(n^2)
QuickSort 快速排序O(n*logn)
InsertSort 插入排序O(n^2)
BInsertSort 折半插入排序O(n^2)
ShellSort 希尔排序 O(N*(logN))
RadixSort 基数排序O(nlog(r)m)
MergeSort 归并排序O(n*log(n))
HeapSort 堆排序O(n*log(n)
BucketSort 桶排序O(N)~O(n^2)
/*=============================================================================
# FileName: InternalSort.cpp
# Desc: 内部排序算法
# Author: Hector
# Email: myourys@gmail.com
# HomePage: http://www.yiwuye.com
# Version: 0.0.1
# LastChange: 2013-03-25 00:02:24
# History:
=============================================================================*/
#include<iostream>
#include <stdlib.h>
#include <ctime>
using namespace std;
void swap(int &a,int &b)
{
int t = a;
a = b;
b = t;
}
/*
* 冒泡排序
* O(n^2) = (n-1)*n/2
*
*/
void BubbingSort(int s[],int n)
{
int i,j;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(s[j]<s[i])
swap(s[i],s[j]);
}
/*
* 简单选择排序
* O(n^2) = (n-1)*n/2
* 对冒泡的一种改进，减少交换次数，如果内循环元素比外循环元素大，则记下位置和大小，内循环完成后得到最大的数
* 每次外循环将最大(小)的数放在前面
*/
void SimpleSelectSort(int s[],int n)
{
int i,j,t,pos;
for(i=0;i<n-1;i++)
{
t=s[i];
pos = i;
for(j=i+1;j<n;j++)
{
if(s[j]<t)
{
pos = j;
t = s[j];
}
}
if(i!=pos)
swap(s[i],s[pos]);
}
}
/*
* 快速排序
* O(n*logn)
* 以开头第一个元素为中间点,大的放在前面,小的放在后边,递归排序
* 分别从后往前搜索,将大数放前面,然后从前往后搜索,将小的放在后边
*/
void QuickSort(int s[],int begin,int end)
{
if(begin>=end) return; //重合点
// a,b 为前后搜索的定位点,e为中间点
int a = begin,b = end;
int e = a;
//从后往前搜索
for(b=end;b>a;b--)
{
if(s[b]<s[e])
{
swap(s[e],s[b]);
e=b;
//从前往后搜索
for(a = a+1;a<b;a++)
{
if(s[a]>s[e])
{
swap(s[e],s[a]);
e=a;
break;//反方向搜索
}
}
}
}
QuickSort(s,begin,e-1);
QuickSort(s,e+1,end);
}
/*
* 插入排序
* O(n^2)
* 算法适用于少量数据的排序
*⒈ 从第一个元素开始，该元素可以认为已经被排序
*⒉ 取出下一个元素，在已经排序的元素序列中从后向前扫描
*⒊ 如果该元素（已排序）大于新元素，将该元素移到下一位置
*⒋ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
*⒌ 将新元素插入到下一位置中
*⒍ 重复步骤2
*/
void InsertSort(int s[],int n)
{
int i,j;
for(i=0;i<n-1;i++) //i前面都是排好序的数列
for(j=i+1;j>0 && s[j] < s[j-1];j--) // 大数往前面冒泡
swap(s[j],s[j-1]);
}
/*
* 折半插入排序
* O(n^2)
* 只能减少插入排序的比较次数，移动次数不变
*/
void BInsertSort(int s[],int n)
{
int i,j,begin,end,mid,t;
for(i=0;i<n-1;i++) //i前面都是排好序的数列
if(s[i+1]<s[i])
{
begin = 0;
end = i;
// 找到最接近的右侧点
while(begin<=end)
{
mid = (begin+end)/2;
if(s[i+1]<s[mid])
end = mid-1;
else
begin = mid+1;
}
t = s[i+1];
//记录后移
for(j=i;j>=begin;j--)
s[j+1]=s[j];
s[begin]= t;
}
}
/*
* 希尔排序
* O(N*(logN)2)
* 希尔排序是插入排序的一种。
* 如此例第一次分为5组,上下为一组,然后每组排序
* 8,1,3,0,9 得到: 8,2,4,6,9
* 7,2,4,6,5 7,1,3,0,5
* 然后分为5/2=2组,每组排列...
* 直至分为1组就是有序了
*/
void ShellSort(int s[],int n)
{
int i,j;
for(int gap =n/2;gap>0;gap /=2) //每次折半
for(i=gap;i<n;i++) //从第二行数据开始,直接插入排序
{
for(j=i-gap;j>=0 && s[j+gap]<s[j];j-=gap) //与之前一列数据比较,此处参考插入排序
swap(s[j],s[j+gap]);
}
}
/*
* 基数排序
* O (nlog(r)m)，其中r为所采取的基数，而m为堆数
* 在某些时候，基数排序法的效率高于其它的比较性排序法
* 即:先按个位排序,然后按十位排序...
*/
void RadixSort(int m[],int n)
{
int w = 6,j,k,r=1; //最大6位数
for(int i = 1;i<=w;i++)
{
for(j=1;j<n;j++) //插入排序
for(k=j-1;k>=0 && m[k+1]/r % 10 < m[k]/r %10;k--)
swap(m[k],m[k+1]);
r*=10;
}
}
/*
* 堆排序
*/
/*
* 归并排序
* O(N*logN)
* 将两个有效数列合并成一个,因此可以考虑分成两个1组,2组合并成1组,直至整个数列完成
*/
void Merge(int a[], int b[], int low, int mid, int high) //将A序列的两组(low-mid,mid+1-high),合并到同大小的b中
{
int k = low;
int begin1 = low;
int end1 = mid;
int begin2 = mid + 1;
int end2 = high;
while(k <= high )
{
if(begin1 > end1) //第1组完成,将第二组附加上去
b[k++] = a[begin2++];
else if(begin2 > end2)
b[k++] = a[begin1++];
else
{
if(a[begin1] <= a[begin2])
b[k++] = a[begin1++];
else
b[k++] = a[begin2++];
}
}
}
//合并序列
void SubMerge(int a[], int b[], int ibegin, int mid,int iend)
{
int pos = ibegin,i,j;
for(i=ibegin,j=mid;i<=mid-1&&j<=iend;)
{
if(a[i]>a[j])
b[pos++] = a[j++];
else
b[pos++] = a[i++];
}
while(i<=mid-1)
b[pos++] = a[i++];
while(j<=iend)
b[pos++] = a[j++];
//同时保持a也有序
for(i=ibegin;i<=iend;i++)
a[i]=b[i];
}
/*
* 将a中的从seg开始，长度为size的数排好序
*/
void SubMergeSort(int a[], int b[], int seg, int size)
{
if(size>=2)
{
SubMergeSort(a,b,seg,size/2);//前一半合并到b中
SubMergeSort(a,b,seg+size/2,size-size/2);//后一半合并到b中
SubMerge(b,a,seg,seg+size/2,seg +size-1); //保持a,b都有序
}
}
void MergeSort(int a[],int size)
{
int *t=a;
int *temp=new int[size];
for(int i=0;i<size;i++)
temp[i]=a[i];
SubMergeSort(a,temp,0,size);
delete []temp;
}
/*
* 堆排序 [采用数组排序]
* O(N * logN)
* 1．父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
* 2．每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）
* i结点的父结点下标就为(i – 1) / 2，孩子2 * i + 1和2 * i + 2
* 由于每次重新恢复堆的时间复杂度为O(logN)，共N - 1次重新恢复堆操作，再加上前面建立堆时N / 2次向下调整，
* 每次调整时间复杂度也为O(logN)。二次操作时间相加还是O(N * logN)。故堆排序的时间复杂度为O(N * logN)
*/
void MiniHeap(int a[],int n); //堆话数组 ->建立最小堆
void MinHeapFixdown(int a[],int i,int n); //调整堆元素
void HeapSort(int a[],int n)
{
int* t = new int[n];
for(int i=0;i<n;i++)
t[i]=a[i];
MiniHeap(t,n);//建立堆
for(int i=0;i<n;i++)
{
a[i] = t[0];
t[0] = t[n-i-1];//删除堆顶，并调整堆,使堆顶是最小元素
MinHeapFixdown(t,0,n-i);
}
delete []t;
}
void MiniHeap(int a[],int n) //堆话数组 ->建立最小堆
{
//i 从最后一个不是叶子节点的位置开始调整堆
for(int i= n/2 - 1;i>=0;i--)
MinHeapFixdown(a,i,n);
}
void MinHeapFixdown(int a[],int i,int n) //大数下沉，自下而上
{
int child = 2*i+1; //左孩子
if(child>=n)//无左右孩子
return;
if(child+1<n && a[child+1]<a[child]) //找到左右孩子最小的
child++;
if(a[child]>=a[i]) //如果本身就是有序的
return;
swap(a[i],a[child]);
MinHeapFixdown(a,child,n);//孩子继续下沉
}
/*
* 桶排序
* 类似Hash,采用分治的思想
* O(N)-O(N^2)
*/
struct Bucket //桶结构
{
int* s;
int size;
Bucket()
{
s =NULL;
size = 0;
}
};
void BucketSort(int a[],int n)
{
Bucket b[1000]; //1千个桶
for(int i=0;i<1000;i++)
b[i].s = new int[n];
//假如数在[0~1,000,000) 之间,分桶
int t;
for(int i = 0;i<n;i++)
{
t = a[i]/1000;
b[t].s[b[t].size++] = a[i];
}
int pos =0;
for(int i=0;i<1000;i++)
{
if(b[i].size >0)
{
QuickSort(b[i].s,0,b[i].size-1); //桶中数字排序
for(int j=0;j<b[i].size;j++)
a[pos++] = b[i].s[j];
}
delete []b[i].s;
}
}
int main()
{
int Flag = 0;
while(Flag < 10)
{
Flag++;
int n = 1000000;
int* s =new int[n];
for(int i=0;i<n;i++)
s[i] = rand() %1000000; //注rand()产生的数在0到RAND_MAX之间
srand(time(NULL));
clock_t ibegin, iend;
ibegin = clock();
switch(Flag)
{
case 19:
cout<<"冒泡排序【BubbingSort】："<<endl;
BubbingSort(s,n);break;
case 29:
cout<<"简单选择排序【SimpleSelectSort】："<<endl;
SimpleSelectSort(s,n);break;
case 3:
cout<<"快速排序【QuickSort】："<<endl;
QuickSort(s,0,n-1);break;
case 49:
cout<<"插入排序【InsertSort】："<<endl;
InsertSort(s,n);break;
case 59:
cout<<"折半插入排序【BInsertSort】："<<endl;
BInsertSort(s,n);break;
case 6:
cout<<"希尔排序【ShellSort】："<<endl;
ShellSort(s,n);break;
case 7:
cout<<"归并排序【MergeSort】："<<endl;
MergeSort(s,n);break;
case 8:
cout<<"堆排序【MiniHeap】："<<endl;
HeapSort(s,n);break;
case 99:
cout<<"基数排序【RadixSort】："<<endl;
RadixSort(s,n);break;
case 10:
cout<<"桶排序【BucketSort】："<<endl;
BucketSort(s,n);break;
}
iend = clock();
if(iend - ibegin>0.1)
cout<<"时间（毫秒）："<<iend - ibegin<<endl;
//for(int i =0;i<n;i++)
// cout<<s[i]<<" ";
delete []s;
cout<<endl;
}
return 0;
}