感谢cnblog@一像素 是他的BLOG帮助我更加清楚的认识了排序算法
排序算法的分类
排序算法的复杂度分析
相关概念补充:
稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面。(不稳定则反之)
1.直接插入排序(Insertion Sort)
工作原理:取出元素与序列中的其他元素比较后插入
代码实现:
void inserttionsort(){
for(int i=1;i<=arraysize;i++){
int pre=i-1;//当前取出的元素的前一个
int now=a[i];//当前元素的值
while(pre>0&&a[pre]>now){
a[pre+1]=a[pre];
now--;
}
a[pre+1]=now;
}
}
2.希尔排序(Shell Sort)
工作原理:分割为几个序列分别进行直接插入排序
改进后的插入排序,区别在于将每次步进的长度改为合适值
代码实现:
void shellsort(){
int shell=arraysize>>1;;//希尔值一般初始化为序列长度的一半
while(shell!=0){
for(int i=1;i<=n;i+=shell){
int pre=i-shell;
int now=a[i];
while(pre>0&&a[pre]>now){
a[pre+shell]=a[pre];
pre=pre-shell;
}
}
shell=shell>>1;
}
}
3.冒泡排序(Bubble Sort)
工作原理:从头走到尾,如果两元素逆序则交换,一直循环
代码实现:
void bubblesort(){
for(int i=1;i<n;i++){
int ok=0;
for(int i=1;i<n;i++){
if(a[i]>a[i+1]){
ok=1;
swap(a[i],a[i+1]);
}
}
if(!ok)return;
}
}
4.选择排序(Selection Sort)
工作原理:找出最小的放在队首
代码实现:
void choosesort(){
for(int i=1;i<=n;i++){
int now=a[i],cur=i;
for(int j=i;j<=n;j++){
if(a[j]<now){
now=a[j];
cur=j;
}
}
swap(a[i],a[cur]);
}
5.归并排序(Merge Sort)
工作原理:分割序列分别排序后合并
代码实现:
void merge(int l,int mid,int r){
int i=l,j=mid+1;
int t=l;
while(i<=mid&&j<=r)
{
if(a[i]<=a[j]) b[t++]=a[i++];
else b[t++]=a[j++];
}
while(i<=mid) b[t++]=a[i++];
while(j<=r) b[t++]=a[j++];
for(int i=l;i<=r;i++) a[i]=b[i];
}
void mergesort(int l,int r){
if(l<r){
int mid=(l+r)/2;
mergesort(l,mid);
mergesort(mid+1,r);
merge(l,mid,r);
}
}
6.快速排序(Quick Sort)
工作原理:设置两哨兵标记逆序元素
代码实现:
void quicksort(int l,int r){
int i,j,mid;
i=l;j=r;
mid=a[(i+j)/2];
while(i<=j){
while(a[i]<mid)i++;
while(a[j]>mid)j--;
if(i<=j){
swap(a[i],a[j]);
i++;
j--;
}
}
if(l<j)quicksort(l,j);
if(i<r)quicksort(i,r);
}
7.堆排序(Heap Sort)
工作原理:利用近似完全二叉树(保证子结点的值小于父节点)
代码实现:
int left(int n){
return n*2;
}
int right(int n){
return n*2+1;
}
void maxheapify(int i){//调整堆
int l=left(i);
int r=right(i);
int largest;
if(l<=heapsize&&a[l]>a[i])
largest=l;
else largest=i;
if(r<=heapsize&&a[r]>a[largest])
largest=r;
if(largest!=i)
{
swap(a[i],a[largest]);
maxheapify(largest);
}
}
void buildmaxheap(){//初始化最大堆
heapsize=n;
for(int i=n/2;i>=1;i--)
maxheapify(i);
}
void heapsort(){
buildmaxheap();
for(int i=n;i>=2;i--){
swap(a[1],a[i]);
heapsize--;
maxheapify(1);
}
}
余下的线性时间排序待本人有时间再继续更啦 溜了