常见的几种排序算法

1. 插入排序

插入排序原理很简单，讲一组数据分成两组，将其称为有序组与待插入组。每次从待插入组中取出一个元素，与有序组的元素进行比较，并找到合适的位置，将该元素插到有序组当中。就这样，每次插入一个元素，有序组增加，待插入组减少。直到待插入组元素个数为0。当然，插入过程中涉及到了元素的移动。

1. 代码实现

void SortManager::insert_sort(int*a, int len){
    for (int j = 1; j < len; j++)
    {
        int key = a[j]; //待排序第一个元素
        int i = j - 1;  //代表已经排过序的元素最后一个索引数
        while (i >= 0 && key < a[i])
        {
            //从后向前逐个比较已经排序过数组，如果比它小，则把后者用前者代替，
            //其实说白了就是数组逐个后移动一位,为找到合适的位置时候便于Key的插入
            a[i + 1] = a[i];
            i--;
        }
        a[i + 1] = key;//找到合适的位置了，赋值,在i索引的后面设置key值。
    }
}

2. 复杂度分析
   当待排数组有序时，没有移动操作（第8行for不成立），此时复杂度为O(N)，当待排数组是逆序时，比较次数达到最大--对于下标 i 处的元素，需要比较 i-1 次。总的比较次数：1+2+...+N-1 ，即(n^{2-n)/2，故时间复杂度为O(N}2)

可以看出，算法中只用到了一个临时变量key，故空间复杂度为O(1)

2.快速排序

从数组中抽出一个元素作为基数v（我们称之为划界元素）,一般是取第一个、最后一个元素或中间的元素
将剩余的元素中小于v的移动到v的左边，将大于v元素移动到v的右边
对左右两个分区重复以上步骤直到所有元素都是有排序好。

1. 代码实现

void SortManager::quick_sort(int*p, int startPos, int endPos){
    if (startPos<endPos) {
        int key = SortManager::getPart(p, startPos, endPos);

        SortManager::quick_sort(p, startPos, key - 1);
        SortManager::quick_sort(p, key + 1, endPos);
    }
    
}
int SortManager::getPart(int*p, int startPos, int endPos){
    int low = startPos,high=endPos;
    int key = p[endPos];
    while (low<high) {
        //从左到右查大于key的值
        while (low<high&&key>=p[low]) {
            low++;
        }
        SortManager::swapPos(p[low], p[high]);
        
        //从右到左查小于key的值，
        while (high>low&&key<=p[high]) {
            high--;
        }
        SortManager::swapPos(p[low], p[high]);

    }
    return low;
}
void SortManager::swapPos(int &a, int &b){
    int temp;
    temp=a;
    a=b;
    b=temp;
}

2. 复杂度
   最差时间复杂度是O(N2) 和冒泡一样，但是它的平均时间复杂度是O(nlog2N)

3. 冒泡排序

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
   2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
   3.针对所有的元素重复以上的步骤，除了最后一个。
   4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

1.代码实现

void SortManager::bubble_sort(int*p, int len){
    for (int i=0; i<len; i++) {
        for (int j=0; j<len-i-1; j++) {
            if (p[j]>p[j+1]) {
                std::swap(p[j], p[j+1]);
            }
        }
    }
}

2.复杂度 O(n2)

4. 选择排序

简单选择排序为最简单的选择排序法，基本思想为：将待排序列分为有序区和无序区，每次排序都在无序区中寻找出最小的关键值放在无序区的最前面和已有的有序区构成新的有序区，然后继续对无序区的元素进行选择直到排序完毕。

1. 代码实现

void SortManager::select_sort(int*p, int len){
    for (int i=0; i<len; i++) {
        int min = i;
        //选出带排序序列中最小的元素
        for (int j=i+1; j<len; j++) {
            if (p[j]<p[min]) {
                min = j;
            }
        }
        if (min != i) {
            std::swap(p[i], p[min]);
        }
    }
}

2.复杂度 O(n2)