- 选择排序
vector<int> selectionSort(vector<int> v){
int temp ;
int size = (int)v.size();
if(size<2) return v;
for(int i=0; i<=size-2;++i){
for(int j=i+1; j<=size-1;++j){
if(v[i]>v[j]){
temp = v[j];
v[j] = v[i];
v[i] = temp;
}
}
}
return v;
}
对于任何输入，时间为O(n*n)；
- 冒泡排序
vector<int> bubbleSort(vector<int> v){
int size = (int)v.size();
if(size<2) return v;
int temp;
bool finish ;
for(int i = size-1;i>0; --i){
finish = true;
for(int j = 0; j<i; ++j){
if(v[j]>v[j+1]){
temp = v[j];
v[j] = v[j+1];
v[j+1] = temp;
finish = false;
}
}
if(finish)
break;
}
return v;
}
最优（对于升序的数组，因为加入了一个跳出判断）：O(n)，平均：O(n*n)， 最差：O(n*n)
- 插入排序
vector<int> insertionSort(vector<int> v){
int size = (int)v.size();
if(size<2) return v;
int temp ;
for(int i=1; i<size;++i){
int j = i-1;
temp = v[i];
while(j>=0){
if(temp<v[j]){
v[j+1]=v[j];
--j;
}else{
break;
}
}
v[j+1]=temp;
}
return v;
}
最优(升序的数组)：O(n)， 最差（严格递减的数组）:O(n*n)，平均(比最差性能快一倍)：O(n*n)
（遇到基本有序的数组时能表现出优异的性能）
- 希尔排序
void shellSort(vector<int>& v)
{
int size = (int)v.size();
if(size<2) return;
int incre = size/2;
int temp;
for(; incre>=1; incre/=2)
{
for(int i=incre; i<size;++i)
{
int j = i - incre;
temp = v[i];
while(j>=0&&temp<v[j])
{
v[j+incre] = v[j];
j -= incre;
}
v[j+incre] = temp;
}
}
}
- 归并排序
void mergeSort(vector<int>& v, int begin, int end){
int size = end-begin;
if(size<2) return;
int mid = (end-begin)/2+begin;
mergeSort(v, begin, mid);
mergeSort(v, mid, end);
merge(v, begin, mid, end);
}
void merge(vector<int>& v, int begin, int mid, int end){
vector<int>va;
va.assign(v.begin()+begin, v.begin()+mid);
vector<int>vb;
vb.assign(v.begin()+mid, v.begin()+end);
int i=0, j=0;
int size_a = (int)va.size();
int size_b = (int)vb.size();
while(i<size_a&&j<size_b){
if(va[i]<vb[j]){
v[begin+i+j]=va[i];
++i;
}else{
v[begin+i+j]=vb[j];
++j;
}
}
while(i<size_a){
v[begin+i+j]=va[i];
++i;
}
while(j<size_b){
v[begin+i+j]=vb[j];
++j;
}
}
最优与平均与最差都是：O(n*log n)
优点在于其稳定性，缺点是需要额外的空间
- 快速排序
void quickSort(vector<int> &v, int begin, int end){
if(end-begin<2) return;
int i = begin;
int j = end-1;
int key = v[begin];
while(i<j){
while(i<j&&v[j]>key){
--j;
}
if(i<j){
v[i]=v[j];
}
while(i<j&&v[i]<key){
++i;
}
if(i<j){
v[j]=v[i];
}
}
v[i]=key;
quickSort(v, begin, i);
quickSort(v, i+1, end);
}
最优：O(n*log n) ， 平均：O(n*log n) ，最差（严格递增的数组，这时插入排序能表现出优异性能）：O(n*n) => 引入随机性即使用随机的元素作为中轴能解决这个窘境（随机快速排序）
- 归并排序对子数组的划分非常快速，时间耗在合并上，
而快速排序时间则耗在子数组的划分上。
- 堆排序
vector<int> heapSort(vector<int> &v){
int size = (int)v.size();
if(size<2)return v;
heapBottomUp(v);
int temp;
vector<int> sortedVector;
for(int i=0;i<size;++i){
temp = getTheHeadTop(v);
sortedVector.insert(sortedVector.begin(), temp);
}
return sortedVector;
}
//自底向上（即从无序到有序）构造最大堆
// 自底向上与自顶向下的区别：
//自顶向下：从无到有的构造 ； 自底向上：从无序到有序的构造
void heapBottomUp(vector<int> &v){
//默认根节点的号码为1， 而向量vector的索引起始为0，注意错位
int size = (int)v.size();
if(size<2)return ;
int i, k, j, fatherValue;
bool heap = false;
for( i=size/2;i>=1; --i){
k = i;
fatherValue = v[k-1];
heap = false;
while(!heap && 2*k<=size){
j = 2*k;
if(j+1<=size){ //存在两个子女
j = v[j-1]<v[j+1-1]? j+1:j;
}
if(fatherValue>v[j-1]){
heap=true;
}else{
v[k-1]=v[j-1];
k=j;
}
}
v[k-1] = fatherValue;
}
}
//获取最大堆顶上的数字
int getTheHeadTop(vector<int>& v){
int size = (int)v.size();
if(size<1) return 0;
int result = v[0];
if(size==1){
v.pop_back();
return result;
}
v[0]=v[size-1];
v.pop_back();
//堆复原处理
int i = 1; //根节点号码
int fatherValue = v[i-1];
int k;
while(2*i<=size){
k=2*i;
if(k+1<=size){
k = v[k-1]<v[k+1-1]?k+1:k;
}
if(fatherValue>v[k-1]){
break;
}else{
v[i-1]=v[k-1];
}
i=k;
}
v[i-1]=fatherValue;
return result;
}
- 堆排序与归并排序的性能差不多，不管平均还是最差情况下都是：O(n*log n)
但堆排序是可以在位的，即不需要额外的存储空间，相比归并排序更省空间。
针对随机文件的计时实验指出，堆排序比快速排序运行得慢。但与归并排序相差无几。
网友评论