首页 > 代码库 > 常规的各种排序
常规的各种排序
1.插入排序:
平均情况:O(n^2);
最好情况:O(n)；
最坏情况:O(n^2);
辅助空间:O(1);
插入排序分为有序区和无序区，将r[0]作为有序区的初始元素，将无序区元素依次插入到有序区。
代码描述:外层循环为无序区：i初始为1（默认数组都是以0开始，下同）i<n;i++;内部循环为有序区，插入排序需要设置一个哨兵temp用来保存需要插入的元素，如果此处不设置哨兵的话，当有序区后退的话r[i]=r[j]，也就是说需要插入的元素变成了有序区的最后一个元素，因此此处需要设置哨兵，以便于可以插入在已经空出的位置。
2.希尔排序:
平均情况:O(n^2)~O(nLogn);
最好情况:O(n^1.3);
最坏情况:O(n^2);
辅助空间:O(1);
描述:希尔排序是针对于插入排序的优化，若待排序记录按关键码基本有序，直接插入排序的效率很高，由于直接插入排序算法简单，则在待排序记录个数较少时效率也很高
3.冒泡排序
平均情况:O(n^2);
最好情况:O(n);
最坏情况:O(n^2);
辅助空间:O(1);
描述:两两比较关键码，遇到反序则交换，知道没有反序
4.快速排序
平均情况:O(nlogn);
最好情况:O(nLogn);
最坏情况:O(n^2);
辅助空间:O(logn)~O(n)
描述:快排是冒泡的优化版，因为冒泡只能是相邻的两个进行比较，但是快排可以一次性将最大的替换到尾部或者将最小的一次性替换到头部，快排设置两个指针，i,j。i在序列的头部,j在序列的尾部。i，右移，j左移。当i==j时，此时的值即为轴值，轴值>=左边所有数,同时<=右边所有数，假设此时的轴值位于m，则[0,m-1]和[m+1,n]则又划分为两个子分区，将这俩分区按相同的方法继续划分，因此快排又叫分区排序。也由此看出快排是一个递归的过程。至于快排的非递归算法则是开辟一个栈，用栈来模拟递归的过程，再简化一点就是用自己开辟的栈储存，区间的头部和尾部，循环时将其弹出，压入新的分区的头部和尾部。
5.选择排序
平均情况:O(n^2);
最好情况:O(n);
最坏情况:O(n^2) ;
辅助空间:O(1);
描述:基本思想是第i趟排序在待排序序列r[i]~r[n]中选取关键码最小的元素并且和第i个元素互换
6.堆排序
平均情况:O(nLogn);
最好情况:O(nlogn)；
最坏情况:O(nlogn)；
辅助空间:O(1);
描述:堆排序是简单选择排序的一种改进，选择排序因为没有将没烫的比较结果保存下来，因此效率才会降低，堆排序再选出关键码的同时也找出了最小关键码，减少了在后面选择排序的次数。堆说白了就是一个具有特殊性质的完全二叉树，这里说的特殊性质指的是每个节点的值都小于或者等于左右孩子节点，被称为小根堆，因为按照这个性质，根节点肯定是最小的值，大根堆相反。堆排序首先需要初始化堆，即将一个数组变成一个堆，具体做法是从(n-1)/2节点开始(默认数组是从0开始)，分别与左孩子(2*n+1)以及与右孩子(2*n+2)进行比较，小的在上，大的换在下面。但是在进行置换其他元素的时候可能会打破现有的平衡，因此需要循环调整下方的元素。堆排序其实就是循环调整维持堆，因为如果是一个堆的话，其根节点肯定是最小的元素，将其与第n-i个元素互换，将[1,n-i-1]个元素继续维持成堆。
//
// main.cpp
// Sorts
//
// Created by sanyinchen on 14-8-29.
// Copyright (c) 2014年 sanyinchen. All rights reserved.
//
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
/*
*直接插入排序
*/
void InsertSort(int r[],int n)
{
int temp=-1;
int i,j;
for( i=1;i<n;i++)
{
temp=r[i];
for(j=i-1;temp<r[j]&&j>=0;j--)
{
r[j+1]=r[j];
}
r[j+1]=temp;
}
for(int i=0;i<n;i++)
cout<<r[i]<<" ";
cout<<endl;
}
/*
*希尔排序
*/
void ShellSort(int *r,int n)
{
int temp=-1,i,j;
for(int d=n/2;d>=1;d=d/2)
{
for(i=d;i<n;i++)
{
temp=r[i];
for(j=i-d;j>=0&&temp<r[j];j-=d)
{
r[j+d]=r[j];
}
r[j+d]=temp;
}
}
for(int i=0;i<n;i++)
cout<<r[i]<<" ";
cout<<endl;
}
/*
*冒泡排序的最优写法
*/
void BubbleSort(int *r,int n)
{
int temp,exchange=n;
while(exchange!=0)
{
int bunnd=exchange;
exchange=0;
for(int i=0;i<bunnd;i++)
{
if(r[i]>r[i+1])
{
temp=r[i];
r[i]=r[i+1];
r[i+1]=temp;
exchange=i;
}
}
}
for(int i=0;i<n;i++)
cout<<r[i]<<" ";
cout<<endl;
}
/*
*快排递归实现
*/
int Partition(int *r,int first,int end)
{
int i,j,temp;
i=first;
j=end;
while(i<j)
{
while(i<j&&r[j]>=r[i])j--;
if(i<j)
{
temp=r[i];
r[i]=r[j];
r[j]=temp;
i++;
}
while(i<j&&r[i]<=r[j])i++;
if(i<j)
{
temp=r[i];
r[i]=r[j];
r[j]=temp;
j--;
}
}
return i;
}
void QuickSort(int *r,int first,int end)
{
if(first>=end)
return ;
else
{
int mid=Partition(r, first, end);
QuickSort(r, first, mid-1);
QuickSort(r, mid+1, end);
}
}
/*
*快排非递归实现
*/
void QuickSortTypeTwo(int *r,int first,int end)
{
int stack[30];
int top=-1,mid;
mid=Partition(r, first, end);
if(first<mid-1)
{
stack[++top]=mid-1;
stack[++top]=first;
}
if(mid+1<end)
{
stack[++top]=end;
stack[++top]=mid+1;
}
while(top!=-1)
{
first=stack[top--];
end=stack[top--];
mid=Partition(r, first, end);
if(first<mid-1)
{
stack[++top]=mid-1;
stack[++top]=first;
}
if(mid+1<end)
{
stack[++top]=end;
stack[++top]=mid+1;
}
}
}
/*
*堆排序
*/
void Sift(int *r,int k,int m)
{
int i,j,temp;
i=k;
j=2*i+1;
while(j<=m)
{
if(j<m&&r[j]<r[j+1])j++;
if(r[i]>r[j])break;
else
{
temp=r[i];
r[i]=r[j];
r[j]=temp;
i=j;
j=2*i+1;
}
}
}
void HeapSort(int*r,int n)
{
int temp;
for(int i=n/2;i>=0;i--)
Sift(r, i, n);
for(int i=0;i<n;i++)
{
temp=r[0];
r[0]=r[n-i];
r[n-i]=temp;
Sift(r, 0, n-i-1);
}
}
/*
*选择排序实现
*/
void SelectSort(int *r,int n)
{
int index,temp;
for(int i=0;i<n;i++)
{
index=i;
for(int j=i+1;j<n;j++)
if(r[j]<r[index]) index=j;
if(index!=i)
{
temp=r[index];
r[index]=r[i];
r[i]=temp;
}
}
}
int main()
{
int a[20][20];
for(int j=0;j<20;j++)
for(int i=0;i<20;i++)
a[j][i]=random()%100;
cout<<"生成的序列1为:"<<endl;
for(int i=0;i<20;i++)
cout<<a[0][i]<<" ";
cout<<endl;
cout<<"直接插入排序"<<endl;
InsertSort(a[0],20);
cout<<"生成的序列2为:"<<endl;
for(int i=0;i<20;i++)
cout<<a[1][i]<<" ";
cout<<endl;
cout<<"希尔排序"<<endl;
ShellSort(a[1], 20);
cout<<"生成的序列3为:"<<endl;
for(int i=0;i<20;i++)
cout<<a[2][i]<<" ";
cout<<endl;
cout<<"冒泡排序"<<endl;
BubbleSort(a[2], 20);
cout<<"生成的序列4为:"<<endl;
for(int i=0;i<20;i++)
cout<<a[3][i]<<" ";
cout<<endl;
cout<<"快排递归实现"<<endl;
QuickSort(a[3], 0, 19);
for(int i=0;i<20;i++)
cout<<a[3][i]<<" ";
cout<<endl;
cout<<"生成的序列5为:"<<endl;
for(int i=0;i<20;i++)
cout<<a[4][i]<<" ";
cout<<endl;
cout<<"快排非递归实现"<<endl;
QuickSortTypeTwo(a[4], 0, 19);
for(int i=0;i<20;i++)
cout<<a[4][i]<<" ";
cout<<endl;
cout<<"生成序列6为:"<<endl;
for(int i=0;i<20;i++)
cout<<a[5][i]<<" ";
cout<<endl;
for(int i=19/2;i>=0;i--)
HeapSort(a[5], 19);
cout<<"堆排序实现"<<endl;
for (int i=0; i<20; i++)
cout<<a[5][i]<<" ";
cout<<endl;
cout<<"生成序列7为:"<<endl;
for(int i=0;i<20;i++)
cout<<a[6][i]<<" ";
cout<<endl;
cout<<"选择排序实现"<<endl;
SelectSort(a[6], 20);
for (int i=0; i<20; i++)
cout<<a[6][i]<<" ";
cout<<endl;
return 0;
}
常规的各种排序