C++实现排序算法

C++实现排序算法 插入排序 基本思想

每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。即边插入边排序，保证子序列中随时都是排好序的。

基本 *** 作

• 在有序序列中插入一个元素，保持序列有序，有序长度不断增加。
• 起初，a[0]是长度为1的子序列。然后逐一将a[1]至a[n-1]插入到有序子序列中。
• 在插入a[i]前，数组a的前半段（a[0]-a[i-1]）是有序段，后半段（a[i]-a[n-1]）是停留与输入次序的 “无序段”。
• 插入a[i]使a[0]-a[i-1]有序，也就是要为a[i]找到有序位置j（）,将a[i]插入在a[j]的位置上。

插入排序的种类

• 直接插入排序：顺序法定位插入位置。
• 二分插入排序：二分法定位插入位置。
• 希尔排序：缩小增量多遍插入排序。

 直接插入排序

1. 复制插入元素，temp = a[i];
2. 记录后移，查找插入位置。
3. 插入到正确的位置。

直接插入排序代码实现

// 直接插入排序(0号位置设置为哨兵)
void directSort(int a[], int len)
{
    int i,j;
    for(i = 2; i < len; i++) // 0号位置为哨兵，1号位置默认有序，所以从2号位置开始。
    {
        if(a[i] < a[i - 1])
        {
            a[0] = a[i];     // 复制为哨兵~
            for(j = i - 1; a[j] > a[0]; j--)
            {
                a[j + 1] = a[j];         
            }
            a[j + 1] = a[0];
        }
    }   
} 

直接插入排序性能分析

实现直接插入排序的基本 *** 作有两个：

1. “比较”序列中两个关键字的大小；
2. “移动”记录；

最好的情况：关键字在记录序列中已经顺序有序。那么只会执行比较 *** 作，不会执行移动 *** 作，并且比较次数为 n - 1 次；

最坏的情况：关键字在记录序列中逆序有序。每个元素都要与其前面所以元素进行比较，同时每个元素都要移动到最前面；所以比较的次数为：，移动的次数为。

平均的情况：比较次数：
                      移动次数：

复杂度结论

• 原始数据越接近有序，排序速度越快；
• 最坏的情况下（输入序列是逆有序的）：
• 平均情况下，耗时差不多是最坏情况的一般：
• 如果想提高查找速度
  • 减少元素的比较次数
  • 减少元素的移动次数
• 空间复杂度：只需要一个哨兵的，。

二分插入排序

 直接插入排序在查找插入位置时，是从后向前依次进行比较。但是我们已知在前半段是有序的，故在查找插入位置时可以使用二分查找法，由此诞生了二分插入排序。和直接插入排序的主要区别就是在查找插入位置的时候，一个使用顺序查找的方法，一个使用二分查找的方法。

二分插入排序代码实现

// 二分插入排序（折半插入排序）
void binInertSort(int a[], int len)
{
    int left, right, mid;
    for(int i = 2; i < len; i++)
    {
        a[0] = a[i]; // 将当前元素插入到哨兵位置
        left = 1, right = i - 1;
        while(left <= right) // while循环结束之后 right + 1 的位置即为要插入的元素位置
        {
            mid = (left + right) / 2;
            if(a[mid] > a[0])
            {
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
            }
        }
        // 找到要插入的位置之后，将此位置之后的元素都向后移动一个位置
        for(int j = i; j != right; j--)
        {
            a[j] = a[j - 1];
        }
        a[right + 1] = a[0];
    }
}

二分插入排序性能分析

• 二分查找比顺序查找快，所以二分插入排序的就平均性能来说比直接插入排序要快；
• 它所需要的关键码比较次数与待排序对象序列的初始排列无关，仅依赖于对象个数。在插入第 个对象时，需要经过  次关键码比较，才能确定它应插入的位置；
  • 当  较大时，总关键码比较次数比直接插入排序的最坏情况要好的多，但比最好情况要差；
  • 在对象的初始排列已经按关键码排好序或接近有序时，直接插入排序比二分插入排序执行的关键码比较次数要少；
• 二分插入排序的对象移动次数与直接插入排序相同，依赖于对象的初始排列。
  • 减少了比较次数，但是没有减少移动次数；
  • 平均性能优于直接插入排序。
• 时间复杂度仍然为，空间复杂度为。

希尔排序 基本思想

先将整个待排序记录序列分割成若干子序列，分别进行直接插入排序，待整个序列中的序列基本有序时，再对全体记录进行以此直接插入排序。因此希尔排序算法的做法为：缩小增量，多遍插入排序。

希尔排序思路

1. 定义增量序列  D_{M-1}>dots>D_1 = 1" src="https://latex.codecogs.com/gif.latex?D_k%3AD_M%3ED_%7BM-1%7D%3E%5Cdots%3ED_1%20%3D%201" />;
2. 对每个  进行“间隔”插入排序  ;

希尔排序特点

• 一次移动，移动位置较大，跳跃式地接近排序后的最终位置；
• 最后一次只需要少量移动；
• 增量序列必须时递减的，最后一个必须是1；
• 增量序列应该是互质的。

希尔排序代码实现

// 希尔排序
void shellInsertSort(int a[], int len_a, int dk)
{
    //对数组a进行一次增量为dk的shell排序，dk为步长因子。
    int i, j;
    for(i = dk + 1; i < len_a; i++)
    {
        if(a[i] < a[i - dk])
        {
            a[0] = a[i];     // 复制为哨兵~
            for(j = i - dk; a[j] > a[0]; j = j - dk)
            {
                a[j + dk] = a[j];         
            }
            a[j + dk] = a[0];
        }
    }
}

void shellInsertSort(int a[], int len_a, int delta[], int len_delta)
{
    // 按增量序列 delta[0] - delta[len_delta]对数组 a 作希尔排序
    for(int i = 0; i < len_delta; i++)
    {
        shellInsertSort(a, len_a, delta[i]);
    }
}

希尔排序性能分析

希尔排序的算法效率与增量序列的取值有关；

• Hibbard增量序列
  •  --------  相邻元素互质
  • 最坏情况：
  • 猜想：
• 希尔排序算法是一种 不稳定 的排序算法；
  • 如何选取最佳的增量序列，目前尚未解决；
  • 最后一个增量值必须为1，其他增量值除1之外无公因子；
  • 不宜在链式存储结构上实现。
• 时间复杂度是经验公式：，空间复杂度为。

交换排序 基本思想

两两比较，如果发生逆序则交换，知道所有记录都排好序为止。

常见的交换排序方法

• 冒泡排序：
• 快速排序：

冒泡排序

相邻两个数两两比较，每轮选出一个最大或者最小的值，在下一轮中不再参与比较。

• 优点：每轮结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；
• 如何提高效率：一旦某一轮没有出现交换记录时，说明已经排好序了，就可以结束本算法了；

冒泡排序代码实现

// 冒泡排序
void bubbleSort(int a[], int len)
{
    bool flag = true; // 增加一个标志位，判断是否在某一轮没有发生交换，那么算法提前结束
    for(int i = 0; i < len - 1 && flag; i++)
    {
        flag = false;
        for(int j = 0; j < len - i - 1; j++)
        {
            if(a[j] > a[j + 1])
            {
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
                flag = true;
            }

        }
    }
}

冒泡排序复杂度分析

• 时间复杂度
  • 最好情况（正序）：
    • 比较次数：n - 1
    • 移动次数：0
  • 最坏情况（逆序）：
    • 比较次数：
    • 移动次数：与比较次数相同。

冒泡排序的算法评价

• 冒泡排序最好的时间复杂度是
• 冒泡排序最坏的时间复杂度为
• 冒泡排序平均的时间复杂度为
• 冒泡排序算法中增加一个辅助空间 temp，空间复杂度为
• 冒泡排序是稳定的

快速排序

改进的交换排序，基本思想：

• 任取一个元素（如：第一个）为中心；
• 所以比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表；
• 对各子表重新选择中心元素并依此规则调整； // 递归思想
• 直到每个子表的元素只剩一个；
• 通过一轮排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字比均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序；

快速排序特点

• 每一轮的子表的形成是采用从两头向中间交替式逼近法；
• 由于每轮中对各子表的 *** 作都相似，可采用递归算法；

快速排序代码实现

// 快速排序
int partition(int a[], int low, int high)
{
    a[0] = a[low];
    while(low < high)
    {
        while(low < high && a[high] > a[0])
        {
            high--;
        }
        a[low] = a[high];
        while(low < high && a[low] < a[0])
        {
            low++;
        }
        a[high] = a[low];
    }
    a[low] = a[0];
    return low;
}

void quickSort(int a[], int low, int high)
{
    if(low < high)
    {
        int pivotlocated = partition(a, low, high);
        quickSort(a, low, pivotlocated - 1);
        quickSort(a, pivotlocated + 1, high);
    }
}

快速排序性能分析

• 时间复杂度
  • 可以证明，平均计算时间是,
  • 实验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个。
• 空间复杂度
  • 快速排序不是原地排序，由于程序中使用了递归，需要递归调用栈的支持，而栈的长度取决于递归调用的深度。（即使不用递归，也需要用用户栈）；
  • 在平均情况下：需要的栈空间；
  • 最坏情况下：栈空间可达；
• 稳定性：快速排序是一种 不稳定 的排序方法。
• 快速排序不适于对原本有序或基本有序的记录序列进行排序。

选择排序 基本思想

在待排序的数据中选出最大（小）的元素放在其最终的位置。

基本 *** 作

1. 首先通过 n - 1 次关键字比较，从 n 个记录中找出关键字最小的记录，将他与第一个记录交换。
2. 再通过 n - 2 次比较，从剩余的 n - 1 个记录中找出关键字次小的记录，将它与第二个记录交换。
3. 重复上述 *** 作，共进行 n - 1 轮排序后，排序结束。

简单选择排序（直接选择排序） 代码实现

// 简单选择排序
void selectSort(int a[], int len)
{
    for(int i = 0; i < len - 1; i++)
    {
        int min_index = i;
        for(int j = i + 1; j < len; j++)
        {
            if(a[j] < a[min_index])
            {
                min_index = j;
            }
        }
        if(min_index != i)
        {
            int temp = a[i];
            a[i] = a[min_index];
            a[min_index] = temp;
        }
    }
}

简单选择排序性能分析

• 时间复杂度
  • 记录移动次数
    • 最好情况：0
    • 最坏情况：3(n - 1)
  • 比较次数：无论待排序列处于什么状态，选择排序所需要进行的“比较”次数都相同：
• 算法稳定性：简答选择排序是不稳定排序
• 空间复杂度：, 只是在交换时需要一个临时的 temp 空间。

堆排序 堆的定义

若 n 个元素的序列  满足：  或 , 则分别称该序列为 小根堆 和 大根堆。

从堆的定义可以看出，堆实质是满足如下性质的完全二叉树：二叉树中的任一非叶子结点均小于（大于）他的孩子结点。

堆排序

若在输出堆顶的最小值（最大值）后，使得剩余 n - 1 个元素的序列重新又建成一个堆，则得到 n 个元素的次小值（次大值），如此反复，便能得到一个有序序列，这个过程称之为 堆排序。

• 实现堆排序需要解决两个问题
  • 如何由一个无序序列建成一个堆？
  • 如何在输出堆顶元素后，调整剩余元素为一个新的堆？

如何在输出堆顶元素后，调整剩余元素为一个新的堆?

• 小根堆（大根堆）

1. 输出堆顶元素之后，以堆中最后一个元素替代之;

2. 然后将根节点值与左、右子树的根节点值进行比较，并与其中小者（大者）进行交换；
3. 重复上述 *** 作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子结点的调整过程为“筛选”;

如何由一个无序序列建成一个堆？

• 显然，单结点的二叉树是堆；
• 在完全二叉树中所有以叶子结点（序号 n/2" src="https://latex.codecogs.com/gif.latex?i%20%3En/2" />）为根的子树是堆；
• 这样我们只需要以此将序号为  的结点为根的子树调整为堆即可

堆排序代码实现

// 堆排序
void heapAdjust(int a[], int s, int m)
{
    int temp = a[s];
    for(int j = 2*s+1; j <= m; j = 2*j+1) // 考虑到数组编号是从 0 开始的，所以这里根结点的左孩子编号稍有改动
    {
        if(j < m && a[j] < a[j+1])
        {
            j++;
        }
        if(temp >= a[j])
        {
            break;
        }
        a[s] = a[j];
        s = j;
    }
    a[s] = temp;
}

void heapSort(int a[], int len)
{
    for(int i = (len-2) / 2; i >=0; i--) // 同理，这里 parents 结点的编号也稍有改动
    {
        heapAdjust(a, i, len-1);
    }
    for(int i = len - 1; i > 0; i--)
    {
        int temp = a[0];
        a[0] = a[i];
        a[i] = temp;
        heapAdjust(a, 0, i - 1);
    }
}

归并排序 基本思想

将两个或两个以上的有序子序列“归并”成一个有序序列。

• 在内部排序中，通常采用的是 2-路归并排序 。
  • 将两个位置相邻的有序子序列归和并为一个有序序列.

归并排序算法分析

• 时间效率：
• 空间效率：，因为需要一个与原始序列同样大小的辅助序列，这正是此算法的缺点。（那我用链表是不是会好一点呢？？？）
• 稳定性：稳定。

基数排序 基本思想

分配 + 收集，也叫桶排序或箱排序：设置若干个箱子，将关键字为  的记录放入第  个箱子，然后再按序号将非空的连接。

数字是有范围的，均由 0 - 9 这是个数字组成，则只需设置十个箱子，相继按 个、十、百...  进行排序。

基数排序算法分析

• 时间效率：, ：关键字个数；：关键字取值范围为  个值；
• 空间复杂度：；
• 稳定性：稳定； 

各种排序方法的综合比较 时间性能

• 按平均的时间性能来分，有三类排序方法
  • 时间复杂度为  的方法有：
    • 快速排序、堆排序和归并排序，其中以快速排序为最好；
  • 时间复杂度为 的有：
    • 直接插入排序、冒泡排序和简单选择排序，其中以直接插入排序为最好；
    • 特别是对那些关键字近似有序的记录序列尤为如此；
  • 时间复杂度为 的排序方法只有：基数排序；
• 当待排序记录按关键字顺序有序时，直接插入排序和冒泡排序能达到  的时间复杂度； 而对于快速排序而言，这是最不好的情况，此时的时间性能退化为 ，因此是应该尽量避免的情况。
• 简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变；

空间性能

• 所以的简单排序方法（包括：直接插入排序、冒泡和简单选择排序）和堆排序的空间复杂度为；
• 快速排序为 ，为栈所需要的辅助空间；
• 归并排序所需要辅助空间最多，其空间复杂度为 ；
• 链式基数排序需附设队列首尾指针，则空间复杂度为;

排序方法的稳定性

• 稳定的怕排序方法指的是，对于两个关键字相等的记录，他们在序列中的相对位置，在排序前后不会发生改变；
• 当对多关键字的记录序列进行 LSD 方法排序时，必须采用稳定的排序方法。
• 对于不稳定的排序方法，只要能举出一个实例说明即可。
• 快速排序和堆排序是不稳定的排序方法。（简单选择排序也是不稳定的）