排序算法总结

参考：

常见排序算法C++总结

各种排序算法的总结

冒泡、插入、选择等容易理解的排序思路

总结： Sort 排序算法

c++ 插入排序算法

1、插入排序稳定

时间复杂度O（n×n），空间复杂度O（1）。

两根指针，分别指向有序区最后一个元素和无序区第一个元素。

代码：

void insertSort(vector<int> &num)
{
    int size=num.size();
    for (int i=1;i<size;i++)
    {
        int temp=num[i]; //待排序第一个元素;
        int j=i-1;  //已排序元素最后一个索引;
        while(j>=0&&temp<num[j])
        {
            //从后向前逐个比较已经排序过数组，如果比它小，排序数组元素后移一位;
            //其实说白了就是数组逐个后移动一位,为找到合适的位置时候便于Key的插入;
            num[j+1]=num[j];
            j--;
        }
        num[j+1]=temp;
    }
}

2、冒泡排序稳定

时间复杂度O（n×n），空间复杂度O（1）。

每次比较如果发现较小的元素在后面，就交换两个相邻的元素。

代码：

/*
冒泡法循环终止条件说明(优化);
第一次找到n个元素中最大的放在最后;
第二次找到n-1个元素中最大的放在倒数第二位;
……
最后一次找到2个元素中最大的放在第二位;
即是说，外层循环一共进行了n-1次就已经排好序了;
*/

void BubbleSort(vector<int> &nums)
{
    int size=nums.size();
    for (int i=0;i<size-1;i++)//i<size也可以;
    {
        for (int j=0;j<size-i-1;j++)//注意循环终止条件,j+1不应超出范围;
        {
            if (nums[j]>nums[j+1])
            {
                swap(nums[j],nums[j+1]);
            }
        }
    }
}

//冒泡法改进(如果一趟扫描过程无交换，则排序可结束);

void BubbleSortBetter(vector<int> &nums)
{
    int size=nums.size();
    int current=0,last=size-1;//定义并初始化当前发生交换位置与最后一次发生交换的位置;

    while (last>0)//说明上次扫描有交换;
    {
        current=0;
        for (int i=0;i<last;i++)//last 之后的已排好，不再考虑;
        {
            if (nums[i]>nums[i+1])
            {
                swap(nums[i],nums[i+1]);
                //记录交换位置,交换一次更新一次;
                current=i;
            }
        }
        //若for循环中无交换，则current为0，last为0，循环结束;
        last=current;
    }
}

另一种形式的代码：

/*
说明;
第一次找到n个元素中最小的放在最前;
第二次找到n-1个元素中最小的放在第二位;
……
最后一次找到2个元素中最小的放在倒数第二位;
即是说，外层循环一共进行了n-1次就已经排好序了;
*/
void exchangeSort(vector<int> &nums)
{
    int size=nums.size();
    for (int i=0;i<size-1;i++)
    {
        for (int j=i+1;j<size;j++)
        {
            if (nums[i]>nums[j])
            {
                swap(nums[i],nums[j]);
            }
        }
    }
}

3、选择排序 不稳定

时间复杂度O（n×n），空间复杂度O（1）。

改进冒泡法，改进之处为：先并不急于调换位置，先从A[0]开始逐个检查，看哪个数最小就记下该数所在的位置P，等一趟扫描完毕，再把A[P]和A[0]对调，这时A[0]到A[n]中最小的数据就换到了最前面的位置。

冒泡与选择的区别可参考：

选择排序算法与冒泡排序算法有何异同

冒泡排序和选择排序

代码：

void selectSort(vector<int> &nums)
{
    int size=nums.size();
    for (int i=0;i<size-1;i++)
    {
        int temp=i;
        for (int j=i+1;j<size;j++)
        {
            if (nums[temp]>nums[j])  //寻找每趟扫描的最小值索引;
            {
                temp=j;
            }
        }
        if (temp!=i)//若最小值不在i位置，交换最小值与i位置元素;
        {
            swap(nums[i],nums[temp]);
        }
    }
}

4、快排序 不稳定

时间复杂度O（nlogn），空间复杂度O（1）。

挖坑填数+分治法。（递归）

选定基准，将大于基准的放到右边，小于基准的放到左边。每次处理完成后，就确定了该基准在数组中的位置。

参考：快速排序

5、归并排序稳定

时间复杂度O（nlogn），空间复杂度O（n）。

分为两个过程：划分数组，合并数组。可以简单理解为将数组从中间一分为二不停拆分，直到子数组只有单个元素。然后每两个子数组进行排序合并，然后再两两数组进行排序合并……重复该过程直到所有数组合并在一起。

参考：归并排序