经典排序算法

• 经典排序算法
• 一、排序的分类
• 二、七大排序算法
• • 1.冒泡排序
  • 2.简单选择排序
  • 3.直接插入排序
  • 4.希尔排序
  • 5.堆排序
  • 6.归并排序
  • 7.快速排序
• 总结

稳定排序：是两个相等的元素在排序前后相对位置不变则是稳定排序，反正为不稳定排序。
内排序与外排序：内排序是在整个排序过程中，待排序的所有记录全部被放置在内存中。外排序是由于排序的数据太多，不能同时放于内存中，整个排序过程需要在内外存之间多次交换数据才能进行。
按照方法分为：插入排序，交换排序，选择排序，归并排序

备注：这里的数组第一个开头元素都是哨兵不参与排序，哨兵的用法在直接插入排序中比较方便。

时间复杂度：O(n^2),最好是有序的时间一次遍历即可O(n)
空间复杂度：O(1)
是否是稳定排序：是，两两比较，没有跳跃性的比较和交换。

代码如下：

#include 
#include 
using namespace std;

void swap(int &a,int &b){
    int temp=a;
    a=b;
    b=temp;
}

void bubbleSort(int*array,int length){
    for(int i=1;i<=length;i++){
        bool flag=false;
        for(int j=length;j>i;j--){
          if(array[j]
              flag=true;
              swap(array[j],array[j-1]);
          }  
        }
        if(!flag){
            break;
        }
    }
}

int main(){
    int array[]={-1,4,5,6,8,7,9,0,1,2,3};
    bubbleSort(array,11);
    for(int i=1;i
        cout< 
2.简单选择排序 
时间复杂度：O(n^2),最好最坏情况一样
 空间复杂度：O(1)
 是否是稳定排序：不稳定排序，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序是不稳定的排序算法。
 代码如下：
 
#include 
using namespace std;

void swap(int &a,int &b){
    int temp=a;
    a=b;
    b=temp;
}

void selection_sort(int*array,int length){
    for(int i=1;i
        int min=i;
        for(int j=i;j
            if(array[j]
                min=j;
            }
        }
        if(i!=min){
            swap(array[i],array[min]);
        }
    }
}

int main(){
    int array[]={-1,4,5,6,8,7,9,0,1,2,3};
    selection_sort(array,11);
    for(int i=1;i
        cout< 
3.直接插入排序 
时间复杂度：O(n^2),最好是有序的时间一次遍历即可O(n)
 空间复杂度：O(1)
 是否是稳定排序：是，两两比较，没有跳跃性的比较和交换。
 代码如下：
 
#include 
using namespace std;

void insertSort(int *array,int length){
    int i,j;
    for(i=2;i
        array[0]=array[i];
        for(j=i-1;j>=1;j--){
            if(array[j]>array[0]){
                array[j+1]=array[j];
            }
            else{
                break;
            }
        }
        array[j+1]=array[0];
    }
}

int main(){
    int array[]={-1,4,5,6,8,7,9,0,1,2,3};
    insertSort(array,11);
    for(int i=1;i
        cout< 
4.希尔排序 
希尔排序本质上就是多次插入排序，使得数组不断向有序的方向发展，其中间隔的取法不固定，但是间隔对整个算法影响很大。
 
时间复杂度：O(n*logn)~O(n^2)
 空间复杂度：O(1)
 是否是稳定排序：否，跳跃性的比较和交换，由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
 代码如下：
 
#include 

using namespace std;


void shell_sort(int*array,int length){
    int increment=length/2;
    for(int i=increment;i>=1;i--){
        for(int j=i+1;j
            if(array[j]
                array[0]=array[j];
                int k;
                for(k=j-i;k>0&&array[k]>array[0];k=k-i){
                    array[k+i]=array[k];
                }
                array[k+i]=array[0];
            }
        }
    }
}

int main(){
    int array[]={-1,4,5,6,8,7,9,0,1,2,3};
    shell_sort(array,11);
    for(int i=1;i
        cout< 
5.堆排序 
堆排序:首先就要构造堆，顶部与尾部交换数据，长度减一，同时进行堆调整。
 
时间复杂度：O(n*logn)，无最好最坏之分
 空间复杂度：O(1)
 是否是稳定排序：否，跳跃性的比较和交换，堆排序的过程是从第n / 2开始和其子节点共3个值选择最大（大顶堆）或者最小（小顶堆），这3个元素之间的选择当然不会破坏稳定性。但当为n / 2 - 1， n / 2 - 2， … 1这些个父节点选择元素时，就会破坏稳定性。有可能第n / 2个父节点交换把后面一个元素交换过去了，而第n / 2 - 1个父节点把后面一个相同的元素没 有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。
 
#include
using namespace std;

void swap(int &a,int &b){
    int temp=a;
    a=b;
    b=temp;
}

//注意要构造小根堆的话需要将先选出较大的元素放到数组最后
void creat_small_heap(int*array,int length){
    int end=(length-1)/2;
    for(int i=end;i>=1;i--){
        int temp=i;
        while(temp<=end){
            int left=2*temp;
            int right=2*temp+1;
            if(right>=length){
                if(array[left]>array[temp]){
                    swap(array[left],array[temp]);
                    temp=left;
                }
                else{
                    //要在这里退出循环
                    break;
                }
            }
            else{
                if(array[left]
                    if(array[right]>array[temp]){
                        swap(array[right],array[temp]);
                        temp=right;
                    }
                    else{
                        break;
                    }
                }
                else{
                    if(array[left]>array[temp]){
                        swap(array[left],array[temp]);
                        temp=left;
                    }
                    else{
                        break;
                    }
                }
            }
        }
    }
}
void heap_sort(int *array,int length){
    for(int i=0;i
        creat_small_heap(array,length-i);
        swap(array[1],array[length-i-1]);
    }
}

int main(){
    int array[]={-1,4,5,6,8,7,9,0,1,2,3};
    heap_sort(array,11);
    for(int i=1;i
        cout< 
6.归并排序 
堆排序:不断进行拆分数组，数组长度唯一的时候进行返回
 
时间复杂度：O(n*logn)，无最好最坏之分
 空间复杂度：O(n)，记录数据
 是否是稳定排序：是，两两比较。
 代码如下：
 
#include 
#include 
using namespace std;

vector merge(vector&a,vector&b){
    vectorans;
    int left1=0;
    int left2=0;
    while(left1
        if(left1
            if(a[left1]<=b[left2]){
                ans.push_back(a[left1]);
                left1++;
            }
            else{
                ans.push_back(b[left2]);
                left2++;
            }
        }
        else if(left1==a.size()&&left2
            ans.push_back(b[left2]);
            left2++;
        }
        else if(left1
            ans.push_back(a[left1]);
            left1++;
        }
    }
    return ans;
}

vector merge_sort(vectorv){
    int length=v.size();
    if(length==1){
        return v;
    }
    vectorleft(v.begin(),v.begin()+length/2);
    vectorright(v.begin()+length/2,v.end());
    //这里是关键
    left=merge_sort(left);
    right=merge_sort(right);
    return merge(left,right);
}

int main(){
    vectorv;
    v={3,1,2,0,5,6,8,7,9};
    v=merge_sort(v);
    for(int i=0;i
        cout< 
7.快速排序 
快速排序:一次遍历确定一个数据
 
时间复杂度：O(n^2)，最好O(n*logn),取决于递归次数（如何划分数组，平衡二叉树知识）
 空间复杂度：O(logn)~O(n)，递归占用栈空间大小
 是否是稳定排序：否，跳跃性的比较和交换，eg：在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为5 3 3 4 3 8 9 10 11，现在中枢元素5和3（第5个元素，下标从1开始计）交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j] 交换的时刻。
 代码如下：
 
#include 
#include 
using namespace std;

vector merge(vector&a,vector&b){
    vectorans;
    int left1=0;
    int left2=0;
    while(left1
        if(left1
            if(a[left1]<=b[left2]){
                ans.push_back(a[left1]);
                left1++;
            }
            else{
                ans.push_back(b[left2]);
                left2++;
            }
        }
        else if(left1==a.size()&&left2
            ans.push_back(b[left2]);
            left2++;
        }
        else if(left1
            ans.push_back(a[left1]);
            left1++;
        }
    }
    return ans;
}

vector merge_sort(vectorv){
    int length=v.size();
    if(length==1){
        return v;
    }
    vectorleft(v.begin(),v.begin()+length/2);
    vectorright(v.begin()+length/2,v.end());
    //这里是关键
    left=merge_sort(left);
    right=merge_sort(right);
    return merge(left,right);
}

int main(){
    vectorv;
    v={3,1,2,0,5,6,8,7,9};
    v=merge_sort(v);
    for(int i=0;i
        cout< 
 
总结 
另外判断一个排序算法是否是稳定的，主要由其关键字的比较和交换，如果是两两比较非跳跃式的则是稳定排序，若是跳跃式比较排序则是不稳定的，简单选择排序是否是稳定的还存在争议，目前我写的代码是非稳定的。