第十章 排序

10.2 插入排序

直接插入排序

找到插入的位置，后边的往后移

二分插入法

查找位置的方式用二分

表插入法

思想是不动元素的位置，给每个元素配一个link指向下一个元素的序号，插入时，从第一个开始遍历，直到找到一个比自己大的，假设当前元素是insert，当前比自己大的是current，当前比自己大的前一个是pre，那么我们把pre的link填成我们的insert的序号，insert的link填成current。

Shell插入排序

假设有n个元素，每间隔b个取一个元素，组成一组，组内排序，不断减小b到1.

如 排序 0 1 2 3 4 5

d = 3

0 3 一组排序 1 4 一组排序 2 一组排序

d = 2

0 2 4 一组排序 1 3 5 一组排序

d = 1

0 1 2 3 4 5一组排序

其实感觉优化力度不大，没啥用

10.3 选择排序

直接选择排序

每次选出最小的值，放在最前面

树形选择排序

就是把元素放到一棵二叉树的叶子节点，每两个节点选出一个小值，给上面的节点，一直到根节点，这样根节点就是当前的最小值，然后递归找到这个最小值，把这个最小值改成无穷大，一直更新回去到根节点，就能再得到一个最小值，不断重复即可，可知每得到一个最小值，需要lgn的复杂度，整体时间复杂度是nlgn

堆排序

就是把一个数组当成一个二叉树，调整为大顶堆，让后把最大值放到最后，对剩下的元素继续建立大顶堆，直到排序完成。

建立大顶堆的好处是，容易访问左右孩子。

在第一次构建大顶堆的时候，需要调整所有非叶子节点（看看是否有比自己大的叶子节点），从最后一个非叶子节点调整，一直到根节点。

一般是用数组来进行堆排序，把数组当作一个丰满二叉树，并且这个数最后一次的叶子节点是从左到右一次排列着的。

即两种情况：

假如树有n个节点，如果是满二叉树即第一种情况

可知，最后一层有（n+1）/2个节点，前面有n/2个节点。那么最后一个非叶子节点在数组种的序号即 n/2-1

假如最后一层有m个节点，那么可知，去掉最后一层的m个节点有n-m个节点，对应了(n-m)/2个非叶子节点，而最后一层的m个节点又带来了m/2个节点，所以总共的非叶子节点个数是 (n-m)/2+m/2=n/2个，那么最后一个非叶子节点在数组中的序号还是n/2-1

所以我们只需要倒着遍历这些非叶子节点，把大的送到根即可，如果换下来的节点比当前的叶子节点还小，也需要递归更新。

for(i=n/2;i>=0;i--) { //比左右孩子节点是否有比自己大的 // 如果右孩子不越界，并且右孩子大于左孩子 // 用右孩子替换自己，并且递归调整右孩子为大顶堆 // 否则 // 用左孩子替换自己，并且递归调整左孩子为大顶堆 }

代码：

// BigHeap.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;



void BuildBigHeap(vector<int>& v, int root, int len)
{
    if (root >= len)return;
    // 数组如果是从1开始的话，那么左孩子是root*2，右孩子是root*2+1
    // 但这里数组是从0开始的，所以在原来的基础上加1
    int left = root * 2+1, right = root*2+2;
    //比左右孩子节点是否有比自己大的
    //    如果右孩子不越界，并且右孩子大于左孩子
    //        用右孩子替换自己，并且递归调整右孩子为大顶堆
    //    否则
    //        用左孩子替换自己，并且递归调整左孩子为大顶堆

    if ((left<len && v[left]>v[root]) || (right<len && v[right]>v[root]))
    {
        if (right<len && v[left]<v[right])
        {
            swap(v[root], v[right]);
            BuildBigHeap(v, right, len);
        }
        else
        {
            swap(v[root], v[left]);
            BuildBigHeap(v, left, len);
        }
    }
}

void BigHeapSort(vector<int>& v)
{
    for (int i = v.size() / 2-1; i >= 0; i--)
    {
        BuildBigHeap(v, i, v.size());
    }
    swap(v[0], v[v.size() - 1]);
    for (int i = 1; i < v.size(); i++)
    {
        BuildBigHeap(v, 0, v.size() - i);
        swap(v[0], v[v.size() - i-1]);
    }
}

int main()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(3);
    v.push_back(6);
    v.push_back(2);
    v.push_back(4);
    v.push_back(7);
    v.push_back(5);

    BigHeapSort(v);
    for (int i = 0; i != v.size(); i++)
    {
        cout << v[i] << " ";
    }
    cout << endl;
    return 0;
}

10.4 交换排序

冒泡排序

不断从左到右遍历，发现后边的比自己小，就把自己与其交换，直到一轮遍历，一次交换也没有发生

快速排序

假设要排序n个数，取第一个位置的值作为中间值,比这个值大的放右边，比这个值小的放左边。

用两个指针，l和r，先l=0，r=n-1。

先不断将r向左移动，

直到碰到一个比中间值小的值，然后交换l和r的值，swap(v[l], v[r]),这样保证给l一个小于关键值的值，

或着没找到比关键字小的值，此时l==r，可知当前最左边就是最小值了，排序右边即可，

再不断将l向右移动直到碰到一个值大于中间值，把这个大于中间值的数换给r，swap(v[l], v[r]),这样保证换给r一个大于中间值的数值，由于先走r，保证了l的位置不可能是最大值，除非所有数相等，所以l向右走一定能找到比自己大的值，如果l向右走的过程中碰到r，说明r此时的数是全局最大的数，保证了左边的数都小于这个数。

当l==r时，该位置左边全是比中间值小的值，右边全是比中间大的值，这个保证是关键。然后再快排左边，再快排右边。最终就完成了排序。

注意一定得先走r，再走l，不然就破坏了正确性。

正确性：

假设l==r时，r右边还有比当前值小的。 如果是r向左走碰到了l，说明r没找到比关键字更小的值，即l==r的这个位置的右边全是大于等于的数。

如果是l向右走碰到了r，因为我们是先走的r，一定保证给l一个小于关键字的值，所以，说明l这一路走过来没有找到更大的值，所以保证了l==r的这个地方的左边全是小于等于的数。

代码：

// QuickSort.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>

using namespace std;

void QuickSort(vector<int> &v, int s, int e)
{
    if (s >= e)return;
    int l = s, r = e, key=v[s];

    while (l < r)
    {
        while (l < r && v[r] >= key)r--;
        swap(v[l], v[r]);
        while (l < r && v[l] <= key)l++;
        swap(v[l], v[r]);
    }

    QuickSort(v, s, l-1);
    QuickSort(v, r+1, e);
}

int main()
{
    vector<int> v;
    v.push_back(5);
    v.push_back(4);
    v.push_back(3);
    v.push_back(2);
    v.push_back(1);

    QuickSort(v, 0, v.size()-1);
    for (int i = 0; i != v.size(); i++)
    {
        cout << v[i] << " ";
    }
    cout << endl;

    return 0;
}

归并排序

不断的把数组二分成两个数组，分别排好两个数组后，然后合并两个数组到原数组，可知需要占用额外的空间。

// MergeSort.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>

using namespace std;

void MergeSort(vector<int>& v, int s, int e)
{
    if (s >= e)return;
    int mid = (s + e)/2;
    MergeSort(v, s, mid);
    MergeSort(v, mid+1, e);

    vector<int> left, right;
    for (int i = s; i <= mid; i++)
        left.push_back(v[i]);
    for (int i = mid + 1; i <= e; i++)
        right.push_back(v[i]);
    int i = 0, j = 0;
    while (i < left.size() || j < right.size())
    {
        if (i < left.size() && j < right.size())
        {
            if (left[i] < right[j])
            {
                v[s + i + j] = left[i];
                i++;
            }
            else
            {
                v[s + i + j] = right[j];
                j++;
            }
        }
        else
        {
            if (i < left.size())
            {
                v[s + i + j] = left[i];
                i++;
            }
            if (j < right.size())
            {
                v[s + i + j] = right[j];
                j++;
            }
        }
    }
}

int main()
{
    vector<int> v;
    v.push_back(5);
    v.push_back(4);
    v.push_back(3);
    v.push_back(2);
    v.push_back(1);

    MergeSort(v, 0, v.size()-1);

    for (int i = 0; i != v.size(); i++)
    {
        cout << v[i] << " ";
    }
    cout << endl;
    return 0;
}

10.6 基数排序

基数排序又称分配排序，应对排序的规则多的情况

多排序码的排序

元素比较大小要看多种规则，比如扑克牌，数组大于花色，数组相同的时候比较花色

所以可以先安装花色将牌分开，然后排序，然后再合并到一起。

静态链式基数排序

根扑克牌一样，先根据优先级高的规则排序，然后根据优先级低的规则排序。