C++算法初级5——排序1

本文介绍排序的几种方法，默认均为从小到大排序，内容来源参考boyuai

选择排序

基本思想：

1. 将1-n位的元素依次归位
2. 当归位第i个元素时，需要选出第i位元素~第n位元素的最小值，和第i位元素互换位置，此时此时，1到i的元素分别为第1小到第i小的元素。
3. 当第n个元素归位完毕以后，整个序列的排序过程结束。

代码

void selectSort(int a[], int n)
{
    for (int i=0;i<n;i++)
    {
        int min = i;
        for (int j=i+1;j<n;j++)
        {
            if (a[j] < a[min])
            {
                min = j;
            }
        }
        if (min != i)
        {
            int temp = a[i];
            a[i] = a[min];
            a[min] = temp;
        }
    }
    // 输出
    for (int i=0;i<n;i++)
    {
        cout << a[i] << " ";
    }
}

复杂度$O(n^2)$

冒泡排序

基本思想：

1. 冒泡排序和选择排序一样，都是将原问题转换为长度减一的子问题的过程。
2. 冒泡排序分为n-1个阶段，每个阶段通过“冒泡”的过程，将未排序序列中的最大值移动到最后一位。
3. 冒泡的过程，具体是通过一段连续交换过程使得最大元素被“传送”到最后一位。
4. 冒泡排序的思路：

冒泡排序分为n-1个阶段。

在第1个阶段，通过“冒泡”，我们将前n个元素的最大值移动到序列的最后一位。此时只剩前n-1个元素未排序。

在第i个阶段，此时序列前n-i+1个元素未排序。通过“冒泡”，我们将前n-i+1个元素中的最大值移动到最后一位。此时只剩前n-i个元素未排好序。

对一段序列从左到右连续做交换操作的代码：

if (a[i] > a[i + 1]) swap(a[i], a[i + 1]);

代码

//冒泡排序
void bubbleSort(int a[],int n)
{
    for(int i=0;i<n-1;i++) // 一共n-1个阶段，在第i个阶段，未排序序列长度从0到n-i-1。
    {
        for(int j=0;j<n-i-1;j++) //循环的角标只到n-i-2，因为会考虑j+1即n-i-1
        {
            if(a[j]>a[j+1])
            {
                swap(a[j],a[j+1]);
            }
        }
    }
    //输出  
    for(int i=0;i<n;i++)
    {
        cout<<a[i]<<" ";
    }
}

复杂度$O(n^2)$

插入排序

插入排序的基本思想就是不断扩展有序序列的长度。

具体方式是对于一个有序序列，如果想在其中新加入一个元素，就应通过插入操作找出正确的插入位置，并且将插入位置空出来，然后插入新元素。

插入操作的基本思想就是从后向前不断“试探”分界线的位置。

一个合法的分界线，分界线前的元素需满足小于等于新元素大小，分界线后元素需满足大于新元素大小。所以寻找分界线的过程，就是不断把当前在分界线前，但本应该在分界线后的元素向后移动。

插入操作的算法描述：

假设序列1~(i-1)已经有序, 从i到1枚举分界线的下标j;

如果分界线前面的元素a[j-1]大于x，说明a[j-1]应该在分界线后面。所以将a[j-1]移动到a[j]，分界线前移变成j-1。

如果分界线前面没有元素（j=1），就将x放在数组第1位。否则如果碰到一个j-1号元素小于等于x，说明分界线位置正确，就将x插到j位。

代码：

// 插入排序
void insertSort(int a[],int n)
{
    for(int i=1;i<n;i++) // 从第二个元素开始，第一个元素认为是有序的
    {
        int temp = a[i]; // 保存当前元素
        int j = i-1; // 从当前元素的前一个元素开始
        while(j>=0 && a[j]>temp) // 从后往前遍历，直到找到比当前元素小的元素
        {
            a[j+1] = a[j]; // 后移
            j--;
        }
        a[j+1] = temp; // 插入
    }
    // 输出
    for(int i=0;i<n;i++)
    {
        cout<<a[i]<<" ";
    }
}

复杂度$O(n^2)$