主要参考:



交换

std::swap()可以直接使用,也可以自己实现:

template <class T>
void swap(const T& a, T const& b)
{
	T temp = a;
	a = b;
	b = temp;
}

关于const,值得说明的是:

  • const T x; 定义一个常量x,其值不可修改

  • const T* p; 定义一个指针变量p,其指向对象*p不可修改,指针p可修改
  • T const* p; 与上等同
  • T* const p = &var; 定义一个指针变量p,其指向对象*p可修改,指针p不可修改
  • const T* const p = &var; 定义一个指针变量p,其指向对象*p和指针p都不可修改

  • const T& a = var 定义一个引用变量a,其值不可修改
  • T const& a = var 与上等同
  • T& const a = var 无意义

  • bool empty() const; const修饰表明该成员函数不修改数据成员

冒泡排序

比较n-1趟,每趟比较n-i-1次,每次从头开始,大数逐次移到末尾. 下图是每次将小数移至最前端。

template<class T>
void BubbleSort(T* a, int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < n - i - 1; j++)
        {
            if (a[j] > a[j + 1])
                swap(a[j], a[j + 1]);
        }
    }
}

选择排序

减少交换次数,只操作下标

template<class T>
void selectSort(T* a, int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < n; j++)
        {
            if (a[min] > a[j])
                min = j;
        }
        if (min != i)
            swap(a[i], a[min]);
    }
}

插入排序

在要排序的一组数中,假定前n-1个数已经排好序,现在将第n个数插到前面的有序数列中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。

template<class T>
void insertSort(T* a, int n)
{
    for (int right = 1; right < n; right++)
    {
        int left = right - 1;
        T temp = a[right];
        while (temp < a[left] and left >= 0)
        {
            a[left + 1] = a[left];
            left--;
        }
        int middle = left + 1;
        a[middle] = temp;
    }
}

快速排序 ★★★

递归的排序算法,平均时间 O ( n l o g n ) \mathcal{O}(nlogn) O(nlogn) 性能是目前最好的,应用最广泛; 但需要工作栈存放递归调用的执行环境,平均栈深 O ( l o g n ) \mathcal{O}(logn) O(logn),是一种不稳定的排序算法.

快速排序 的思想----分治法非常实用,因此很多软件公司的笔试面试,包括像腾讯,微软等知名IT公司都喜欢考这个,还有大大小的程序方面的考试如软考,考研中也常常出现快速排序的身影。

基本思想:(分治)

  • 先从数列中取出一个数作为key值;
  • 将比这个数小的数全部放在它的左边,大于或等于它的数全部放在它的右边;
  • 对左右两个小数列重复第二步,直至各区间只有1个数。
template<class T>
void quickSort(T* a, const int left, const int right)
{
    if (left >= right) return;  // 待排序数列只有一个元素时,结束递归
    else
    {
        // 选枢轴
        if (right - left == 1);
        else
        {   // 中值放在左侧
            int middle = (left + right) / 2;
            if (a[left] > a[middle])
                swap(a[middle], a[left]);
            if (a[middle] > a[right])
                swap(a[middle], a[right]);
            if (a[left] < a[middle])
                swap(a[middle], a[left]);
        }
        int pivot = left;

        // 一次划分
        int i{ left }, j{ right + 1 };
        while (i < j)
        {
            do i++; while (a[i] < a[pivot]);    // 从左扫描
            do j--; while (a[j] > a[pivot]);    // 从右扫描
            if (i < j) swap(a[i], a[j]);
        }
        swap(a[pivot], a[j]);                   // 最左侧为初始枢轴
        pivot = j;

        // 递归
        quickSort(a, left, pivot - 1);
        quickSort(a, pivot + 1, right);
    }
}

归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。

首先考虑引子:如何将2个有序数列合并?这个非常简单,只要从比较2个数列的第一个数,谁小就先取谁,取了后就比较下一个数,如果有数列为空,那直接将另一个数列的数据依次取出即可。

引子
以下是两个有序数组a[ ], b[ ]的归并排序(最简单)

解决了上面的合并有序数列问题,再来看归并排序,其的基本思路是:将数组分成2组A,B,如果这2组组内的数据都是有序的,那么就可以很方便的将这2组数据进行排序。如何让这2组组内数据有序了?可以将A,B组各自再分成2组。依次类推,当分出来的小组只有1个数据时,可以认为这个小组组内已经达到了有序,然后再合并相邻的2个小组就可以了。这样通过先 递归 的分解数列,再合并数列就完成了归并排序。

  • 递归式
// 一次归并排序, 输入为已排序数组 a[l,...,m] a[m+1,...,n]
template <class T>
void merge(T* a, const int l, const int m, const int n)
{
    // 申请辅助空间
    int length = n - l + 1;
    assert(length > 1);   // 消除C6386警告
    T* temp = new T[length];
    // 遍历等长元素 
    int i = l, j = m + 1, k = 0; 
    while (i <= m and j <= n)
    {
        if (a[i] <= a[j])
        {
            temp[k++] = a[i++];
        }
        else
        {
            temp[k++] = a[j++];
        }
    }
    // 复制其余元素
    copy(a + i, a + m + 1, temp + k);
    copy(a + j, a + n + 1, temp + k);
    // 释放辅助空间
    copy(temp, temp + length, a + l);
    delete[] temp;
}

template <class T>
void mergeSort(T* a, int left, int right)
{
    if (left >= right)
        return;
    int mid = (left + right) / 2;
    mergeSort(a, left, mid);
    mergeSort(a, mid + 1, right);
    merge(a, left, mid, right);
}
  • 迭代式

以下代码的缺点:频繁申请/释放内存

// 一次归并排序, 输入为已排序数组 a[l,...,m] a[m+1,...,n]
template <class T>
void merge(T* a, const int l, const int m, const int n)
{
    // 申请辅助空间
    int length = n - l + 1;
    assert(length > 1);   // 消除C6386警告
    T* temp = new T[length];
    // 遍历等长元素 
    int i = l, j = m + 1, k = 0; 
    while (i <= m and j <= n)
    {
        if (a[i] <= a[j])
        {
            temp[k++] = a[i++];
        }
        else
        {
            temp[k++] = a[j++];
        }
    }
    // 复制其余元素
    copy(a + i, a + m + 1, temp + k);
    copy(a + j, a + n + 1, temp + k);
    // 释放辅助空间
    copy(temp, temp + length, a + l);
    delete[] temp;
}

// 一趟归并排序
template <class T>
void mergePass(T* a, int n, int h)
{
    int i= 1;
    while (n - i + 1 >= 2 * h)
    {
        merge(a, i, i + h - 1, i + 2 * h - 1);
        i += 2 * h;
    }
    if (n - i + 1 > h)
        merge(a, i, i + h - 1, n);
    else
        ;// do nothing
}

// 归并排序(迭代式)
template <class T>
void mergeSort(T* a, int n)
{
    if (a == nullptr or n <= 0) return;
    // 最初归并长度为1
    for (int h = 1; h < n; h *= 2)
    {
        mergePass(a, n, h);
    }
}

改进:只申请一次内存

// 一次归并排序, 输入为已排序数组 a[l,...,m] a[m+1,...,n]
template <class T>
void merge(T* a, T* result, const int l, const int m, const int n)
{
    // 遍历等长元素
    int i = l, j = m + 1, k = l;
    while (i <= m and j <= n)
    {
        if (a[i] <= a[j])
        {
            result[k++] = a[i++];
        }
        else
        {
            result[k++] = a[j++];
        }
    }
    // 复制其余元素
    copy(a + i, a + m + 1, result + k);
    copy(a + j, a + n + 1, result + k);
}

// 一趟归并排序
template <class T>
void mergePass(T* a, T* result, int n, int h)
{
    int i = 1;   
    while (n - i + 1 >= 2 * h)
    {
        merge(a, result, i, i + h - 1, i + 2 * h - 1);
        i += 2 * h;
    }
    if (n - i + 1 > h)
        merge(a, result, i, i + h - 1, n);
    else
        copy(a + i, a + n + 1, result + i);
}

// 归并排序(迭代式)
template <class T>
void mergeSort(T* a, int n)
{
    if (a == nullptr or n <= 0) return;
    T* temp = new T[n + 1];
    int h = 1;  // 最初归并长度为1
    while (h < n)
    {
        mergePass(a, temp, n, h);
        h *= 2;
        mergePass(temp, a, n, h);
        h *= 2;
    }
    delete[] temp;
}

基数排序(桶、箱)

基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶排序”(bucket sort)或“箱排序”(bin sort),顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法属于稳定性的排序,其时间复杂度为O (nlog®m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。

基数排序是建立在“箱排序”的基础上的。箱排序是创建数组A[MaxValue];然后将每个数放到相应的位置上(例如17放在下标17的数组位置);最后遍历数组,即为排序后的结果。
.
存在的问题: 当序列中存在较大值时,BinSort 的排序方***浪费大量的空间开销。

基数排序是在BinSort的基础上,通过基数的限制来减少空间的开销。所谓基数,是指进制,十进制数列的基数为10,二进制为2,八进制为8.

可以用链表或者数组来构造“箱”,这里使用STL中的链表完成:

template<class T>
int maxdigit(const T a, int n)
{
    int digits{ 1 }, ratio{ 10 };
    for (int i = 0; i < n; ++i)
    {
        while (a[i] > ratio)
        {
            ++digits;
            ratio *= 10;
        }
    }
    return digits;
}

template<class T>
void radixSort(T* a, int n)
{
    std::list<T> bins[10];  // 十进制需要十个箱
    int digits = maxdigit(a, n);
    for (int d = 0, radix = 1; d < digits; ++d, radix *= 10)
    {
        // 将每个数放入对应箱中
        for (int i = 0; i < n; ++i)
        {
            int index = (a[i] / radix) % 10;
            bins[index].push_back(a[i]);
        }

        // 从10个箱中按顺序取出,每取一个就删除一个
        for (int i = 0, j = 0; i < 10; ++i)
        {
            while (not bins[i].empty())
            {
                a[j++] = bins[i].front();
                bins[i].pop_front();
            }
        }
    }
}