排序

- 概述
分类
内排序：数据量少，在内存中
插入
交换
选择
归并
外排序：数据量大，内外存需要交换数据
按复杂度分
简单算法：冒泡、简单选择、直接插入
改进算法：希尔、堆、归并、快速
稳定性：两个一样的数字，排序后相对位置不变，则稳定
- 冒泡排序
思想：从上到下/从下到上，与相邻元素比较
改进：设置有无交换的标志位
复杂度：最好/最坏
稳定：arr[j]严格>arr[j+1]时，才做交换

void BubbleSort(vector<int> arr)
{
    int sz=arr.size();
    bool flag=true;
    for(int i=0;i<sz-1&&flag;i++)
    {
        flag=false;//没交换
        for(int j=sz-2;j>=i;j--)
        {
            if(arr[j]>arr[j+1])
            {
                swap(arr[j],arr[j+1]);
                flag=true;
            }
        }
    }
}

- 简单选择排序
思想：通过n-i次比较，从n-i+1中选出最小的，与位置i的交换
复杂度

void SelectSort(vector<int> arr)
{
    int sz=arr.size();
    int min;
    for(int i=0;i<sz-2;i++)
    {
        min=i;
        for(j=i+1;j<sz-1;j++)
        {
            if(arr[min]>arr[j])
                min=j;
        }
        if(i!=min) swap(arr[i],arr[min]);
    }                   
}

- 直接插入排序
思想：扑克牌 将一个元素插入已经排好序的序列中
复杂度
稳定

void InsertSort(vector<int> arr)
{
    int sz=arr.size();
    for(int i=1;i<sz;i++)
    {
        int tmp=arr[i];//摸下一张牌
        for(int j=i;j>0&&arr[j-1]>tmp;j--)
            arr[j]=arr[j-1];//为新牌找位置，比它大的都向后挪
        arr[j]=tmp;//新牌落座
    }
}

- 希尔排序
思想：定义增量序列（最后一定是1）；对每个增量序列进行排序；基本有序；跳跃；
更多增量序列
复杂度
不稳定

void ShellSort(vector<int> arr)
{
    int N=arr.size();
    for(int D=N/2;D>0;D/=2)//增量序列
    {
        for(int i=D;i<N;i++)//插入排序
        {
            int tmp=arr[i];
            for(int j=i;j>=D&&arr[j-D]>tmp;j-=D)
                arr[j]=arr[j-D];
            arr[j]=tmp;
        }
    }
}

- 堆排序（选择排序的改进）
思路：构建最大堆；堆顶与堆尾元素交换；删去堆尾后重建最大堆；重复
（利用堆的性质：完全二叉树；编号；父/子节点编号）
数组编号从0开始，堆从1开始
复杂度（最好/坏/平均一样）
不稳定
不适合待排序序列个数少的

// 递归方式构建大根堆(len是arr的长度，index是第一个非叶子节点的下标)
void adjust(vector<int> &arr, int len, int index)
{
    int left = 2*index + 1; // index的左子节点
    int right = 2*index + 2;// index的右子节点

    int maxIdx = index;//maxIdx保存根、左、右最大的下标
    if(left<len && arr[left] > arr[maxIdx])     maxIdx = left;
    if(right<len && arr[right] > arr[maxIdx])     maxIdx = right;

    if(maxIdx != index)
    {
        swap(arr[maxIdx], arr[index]);
        adjust(arr, len, maxIdx);//从此次最大子节点的位置递归
    }

}
// 堆排序
void HeapSort(vector<int> &arr, int size)
{
    // 构建大根堆（从最后一个非叶子节点向上）
    for(int i=size/2 - 1; i >= 0; i--)
    {
        adjust(arr, size, i);
    }
    // 调整大根堆
    for(int i = size - 1; i >= 1; i--)
    {
        swap(arr[0], arr[i]);  // 将当前最大的放置到数组末尾
        adjust(arr, i, 0);     // 去除最后位置的元素，将未完成排序的部分继续进行堆排序
    }
}

- 归并排序
思想：有序子列的归并
复杂度：最好/坏/平均一样
空复：常用于外排序
稳定：两两比较，无跳跃

递归：
void Merge(int a[], int b[], int left, int mid, int right)//归并到a
{
    int i=left,j=mid+1;
    int k=left;//存放结果数组的初始位置
    while(i<=mid&&j<=right)
    {
        if(a[i]<=a[j]) b[k++]=a[i++];
        else b[k++]=a[i++];
    }
    while(i<=mid) 
        b[k++]=a[i++];
    while(j<=right)
        b[k++]=a[j++];
    for(i=left;i<right-left+1;i++)
        a[i]=b[i];
}
void Msort(int a[], int b[], int l, int r)
{
    if (l >= r) //必须有等号
        return;
    int m = (l + r)/2;
    Msort(a, b, l, m);
    Msort(a, b, m + 1, r);
    Merge(a, b, l, m, r);
}
void MergeSort(int a[], int len)
{
    int *b = new int[len];
    //int *b;
    //b=malloc(len*sizeof(int));
    if(!b)
    {
        Error("空间不足");
    }
    else
    {
        Msort(a, b, 0, len - 1);
        delete[] b;
        //free(b);
    }
}

//非递归：
void MergePass(int a[],int b[],int len,int sz)
{
    int i;    
    for(i=0;i<=len-2*sz;i+=2*sz)
        Merge1(a,b,i,i+sz,i+2*sz-1);//将a归并到b
    if(i+sz<len)//归并最后两个子列
        Merge1(a,b,i,i+sz,len-1);
    else//最后只剩一个子列
        for(int j=i;j<len;j++)
            b[j]=a[j];
}
void MergeSort(int a[], int len)
{
    int sz=1;//初始化子序列长度
    int *b = new int[len];
    //int *b;
    //b=malloc(len*sizeof(int));
    if(!b)
    {
        Error("空间不足");
    }
    else
    {
        while(sz<len)
        {
            MergePass(a,b,len,sz);
            sz*=2;
            MergePass(b,a,len,sz);
            sz*=2;
        }        
        delete[] b;
        //free(b);
    }
}

• 稳定：冒泡、直接插入、归并
  不稳定：简单选择、希尔、堆、快速