八大排序算法合集（C++实现）

原创已于 2022-09-20 10:48:06 修改
· 1k 阅读
4 ·
版权
文章标签：
#数据结构 #排序算法 #c
于 2018-06-12 21:15:40 首次发布
数据结构与算法专栏收录该内容
6 篇文章
订阅专栏
最近重新复习了一下排序算法，深入理解了各个排序算法的基本思想，根据算法基本思想重新写了这八种类型的排序算法，特此总结一下，以便日后忘记时可以重新查看。也给有需要的朋友作参考。
#include <iostream>

#include <vector>
#include <queue>
using namespace std;
/*********************************插入排序算法******************************/
/***********************直接插入排序*********************/
/**
 *基本思想：顺序地把待排序的数据元素按其关键字值的大小插入
 *到已排序数据元素子集合的适当位置
 *子集合的数据元素个数从只有一个数据元素开始，
 *逐次增大，当子集合大小最终和集合大小相同时
 *排序完成
 *直接插入排序是稳定的
 * **/
void InsertionSort(vector<int> &vtArr)
{
    //将数组的第一个元素看做有序序列，从第二个元素开始直到数组的最后一个元素
    //依次插入
    for (unsigned int i=1; i<vtArr.size(); ++i)
    {
        int temp = vtArr[i];
        int j = i - 1;
        //按照从小到大排序，如果当前元素比前一个元素小，就把前一个元素往后移动
        while(j > -1 && temp < vtArr[j])
        {
            vtArr[j + 1] = vtArr[j];
            --j;
        }
        //将比较的元素放到适合的位置
        vtArr[j + 1] = temp;
    }
}

/****************************希尔排序法******************************/
/**
 *基本思想：把待排序的数据元素分成若干个小组，对同一个小组内的数据元素
 *用直接插入法排序；小组的个数逐次减少；当完成了所有数据元素都在一个组
 *内的排序后，排序过程结束。希尔排序又称作缩小增量排序
 *值得注意的是，增量序列的最后一个元素一定是1
 *一般使用增量序列为[n/2, n/4, n/8,...,1]，n为排序数组的元素个数
 */
void ShellSort(vector<int> &vtArr)
{
    // 先根据排序数组的大小确定增量序列
    // 增量序列为[n/2, n/4, n/8,...,1]n为排序数组的元素个数
    vector<int> vtAdd;
    // 如果没有元素或者只有一个元素，不需要排序，返回
    if (vtArr.size() < 2)
    {
        return;
    }
    unsigned int num = 2;
    int nSpan;// 增量值
    while(num <= vtArr.size())
    {
        nSpan = vtArr.size() / num;
        vtAdd.push_back(nSpan);
        num *= 2;
    }
    // 这个分组的思想是按增量span来划分，[j,j+span,j+2span...]其中 j>=0 && j<span
    for (unsigned int i=0; i<vtAdd.size(); ++i)
    {
        nSpan = vtAdd[i];//每次的增量值
        for (int j=0; j<nSpan; ++j)
        {
            for (unsigned int k=j; k<vtArr.size() - nSpan; k += nSpan )
            {
                int temp = vtArr[k + nSpan];
                int m = k;
                while(m > -1 && temp < vtArr[m])
                {
                    vtArr[m + nSpan] = vtArr[m];
                    m -= nSpan;
                }
                vtArr[m + nSpan] = temp;
            }
        }
    }
}

/*********************************选择排序算法******************************/
/***********************直接选择排序算法*********************/
/*基本思想：首先将待排序的数据元素集合的第1个视为最小元素，
 *并记录其下标为small，然后从第2个元素开始找出比下标
 *为small的元素小的元素，并把其下标值存为small，继续往后查找到
 *集合最后一个元素，每次查找到下标比small小的元素
 *就将其下标替换为small。这样就找出了整个集合中最小的元素的下标small，
 *然后将第1个元素与下标为small的元素互换位置。
 *接着将集合的第2个元素视为最小元素，记下下标为small，
 *然后从第3个元素开始按以上方法查找，即找出集合中次小的元素
 *然后将次小元素与第2个元素互换位置。重复以上步骤直到集合中只剩一个元素为止。
 */
void SelectSort(vector<int> &vtArr)
{
    for(unsigned int i=0; i<vtArr.size() - 1; ++i)
    {
        unsigned  int small = i;
        for (unsigned int j=i + 1; j<vtArr.size(); ++j)
        {
            if (vtArr[small] > vtArr[j])
            {
                small = j;
            }
        }
        if (small != i)
        {
            int temp = vtArr[i];
            vtArr[i] = vtArr[small];
            vtArr[small] = temp;
        }
    }
}

/*********************************堆排序法******************************/
/* 基本思想：首先把n个元素的数组a初始化为最大堆，
 * 然后循环执行如下过程直到数组为空为止：
 * 1、把堆顶a[0]元素（为最大元素）和当前最大堆的最后一个元素交换
 * 2、最大堆元素个数减1
 * 3、由于第1步后根节点不再满足最大堆的定义，因此调整根节点使之满足最大堆的定义
 */
// 堆排序首先需要定义一个函数，将一颗所有叶节点都满足最大堆的定义，
// 只有根节点没有满足最大堆定义的
// 情况下，调整为最大堆。
// 其中vtArr为堆数组，n为堆的节点个数，nRootIndex为要调整为最大堆的根节点下标
// 已知根节点的下标，则左子树的下标为2*nRootIndex+1,右子树的下标为2*nRootIndex+2
void CreateHeap(vector<int> &vtArr, int n, int nRootIndex)
{
    int i = nRootIndex;
    int j = 2 * i + 1;//左子树的下标
    int tempValue = vtArr[nRootIndex];//保存根节点的值
    bool bFinish = false;//是否调整完成的标志
    while (j < n && !bFinish)
    {
        // 找出左子树和右子树的最大值
        if (j+1 < n && vtArr[j] < vtArr[j+1])
        {
            ++j;//j+1后就变成了右子树的下标了
        }
            
        // 如果根节点大于左右子节点的最大值，说明符合最大堆的定义，调整完成
        if (tempValue > vtArr[j])
        {
            bFinish = true;
        }
        else
        {
            // 否则该子节点上移到根节点
            vtArr[i] = vtArr[j];
            i = j;//原来的子节点的位置成为新的根
            j = 2 * i + 1;//新根的左子树的下标
        }
    }
    // 把原来的根元素放合适的位置
    vtArr[i] = tempValue;
}

// 将需要排序的无序数组初始化成为一个最大堆，
// 需要从最后一个非页节点到根节点a[0],依次调整
// 使其符合最大堆的定义；最后一个非叶节点为(n-2)/2取整，其中n为堆的元素个数
void InitHeap(vector<int> &vtArr)
{
    for (int i=(vtArr.size()-2)/2; i>=0; --i)
    {
        CreateHeap(vtArr, vtArr.size(), i);
    }
}

// 堆排序主函数
// 首先把有n个元素的数组vtArr初始化为最大堆，
// 然后循环执行如下过程直到数组为空为止
// 1、把堆顶元素vtArr[0](为最大元素)和当前最大堆的最后一个元素交换；
// 2、最大堆元素个数减1
// 3、由于第1步后根结点不再满足最大堆定义，因此调整根结点使之满足最大堆的定义
void HeapSort(vector<int> &vtArr)
{
	InitHeap(vtArr);// 将需要排序的数组初始化成为最大堆
    for (int i = vtArr.size()-1; i>0; --i)
    {
        int temp = vtArr[0];
        vtArr[0] = vtArr[i];
        vtArr[i] = temp;
        CreateHeap(vtArr, i, 0);
    }
}

/*********************************交换排序******************************/
/*******************冒泡排序法**********************/
/*基本思想：设数组vtArr中存放了n个数据元素，循环进行n-1趟如下的排序过程：
 * 第一趟时，依次比较相邻两个数据元素vtArr[j]和vtArr[j+1](j=0,1,2...,n-2),
 * 如果vtArr[j]>vtArr[j+1]
 * 则交换两个数据元素，否则不交换，这样数值最大的数据元素将被放置在vtArr[n-1]中；
 * 第二趟时，数据元素个数减1，即数据元素个数为n-1,操作方法和第一趟类似，这样整个
 * n个数据元素集合中数值次大的数据元素将被放置在vtArr[n-2]中；当第n-1趟结束时，整个n
 * 个数据元素集合中次小的数据元素将被放置在vtArr[1]中，vtArr[0]中放置了
 * 最小的数据元素
 */ 
void BubbleSort(vector<int> &vtArr)
{
    bool bOrder = false;
    for (int i = vtArr.size() - 1; i > 0 && !bOrder; --i)
    {   
        bOrder = true;
        for (int j=0; j<i; ++j)
        {
            if (vtArr[j] > vtArr[j+1])
            {
                int temp = vtArr[j];
                vtArr[j] = vtArr[j+1];
                vtArr[j+1] = temp;
                bOrder = false;//有交换说明还没有序
            }
        }
    }
}

/*********************************快速排序法******************************/
/*基本思想：快速排序是一种二叉树结构的交换排序方法。设数组a中存放了n个数据元素，
 * low为数组的低端下标，
 * hight为数组的高端下标，从数组a中任取一个元素（通常取a[low]）作为标准，
 * 调整数组a中各个元素的位置，使
 * 排在标准元素前面的元素均小于标准元素，排在标准元素后面的元素均大于
 * 或等于标准元素的关键字。这样一次过
 * 程结束后，一方面将标准元素放在未来排好序的数组中该标准元素应在的位置，
 * 另一方面将数组中的元素以标准元
 * 素为中心分成了两个子数组，位于标准元素左边的元素均小于标准元素，
 * 位于标准元素右边的元素均大于标准元素
 * 然后，对这两个子数组中的元素分别再进行方法类同的递归快速排序。
 * 递归算法的结束条件是hight<=low,即上界
 * 下标小于或等于下界下标
 */
void QuickSort(vector<int> &vtArr, int low, int hight)
{
    int i = low;    // 左边扫描起始位置
    int j = hight;  // 右边扫描起始位置
    int temp = vtArr[i];// 取下标最低位置的元素作为标准元素，并保存到临时变量
    while (i < j)
    {
        // 因为以下标最低位置元素为标准元素，因此开始扫描必须从数组右侧进行扫描
        while (i < j && temp < vtArr[j])
		{
			--j;
		}
		if (i < j)
		{
			// 当从右向左找到第一个小于temp元素的元素时，交换两个元素的位置
			vtArr[i] = vtArr[j];
			++i;
		}
		// 然后从左向右扫描查找
		while (i < j && temp > vtArr[i])
		{
			++i;
		}
		if (i < j)
		{
			// 当从左向右找到第一个大于temp元素的元素时，交换两个元素的位置
			vtArr[j] = vtArr[i];
			--j;
		}
    }
	// 把标准元素放在最终适合的位置,此时i==j
	vtArr[i] = temp;
	// 以位置i为分割点，将数组分割成左右两个数组，再对左右两个数组进行递归排序
	if (low < i)
	{
		QuickSort(vtArr, low, i-1);
	}
	if (i < hight)
	{
		QuickSort(vtArr, i+1,hight);
	}
}

/*********************************归并排序******************************/
/* 归并排序主要是二路归并排序。
 * 二路归并排序算法的基本思想：设数组vtArr中存放了n个数据元素，
 * 初始时把它们看成n个长度为1的有序
 * 子数组，然后从第一个有序子数组开始，把相邻的有序子数组两两合并，
 * 得到n/2（此处向上取整）个长度
 * 为2的新的有序子数组（当n为奇数时，最后一个新的有序子数组的长度为1）。
 * 对这些新的有序子数组再进行
 * 两两归并。如此重复，直到得到一个长度为n的有序数组为止。
 * 算法中，需要初始化一个新的数组，以存放归并后的数据
 */ 
// 归并函数
// vtOrder 待归并的部分有序的数组
// vtMerge 存放归并后的数组
// nLen 分组的长度
void Merge(vector<int> &vtOrder, vector<int> &vtMerge, int nLen)
{
    int l1 = 0;//第一个归并组的下标从0开始
    int l2;// 第二个归并组的起始下标
    int h1;// 第一个归并组的最后下标
    int h2;// 第二个归并组的最后下标
	int m = 0;//vtMerge数组的下标
    while (l1 + nLen  < (int)vtOrder.size())
    {
        h1 = l1 + nLen -1;//第一组的上限
        l2 = l1 + nLen;//第二组的开始
        h2 = min(l2 + nLen -1, (int)vtOrder.size() - 1);
		// 归并过程
		int i=l1;
		int j=l2;
		for (; i<=h1 && j <=h2; ++m)
		{
			if (vtOrder[i] <= vtOrder[j])
			{
				vtMerge[m] = vtOrder[i];
				++i;
			}
			else
			{
				vtMerge[m] = vtOrder[j];
				++j;
			}
		}
		// 归并完后，有可能有其中一组没有全部放到vtMerge
		// 将第一组剩下的元素放到vtMerge
		while (i <= h1)
		{
			vtMerge[m] = vtOrder[i];
			++i;
			++m;
		}
		// 将第二组剩下的元素放到vtMerge
		while (j <= h2)
		{
			vtMerge[m] = vtOrder[j];
			++j;
			++m;
		}
        l1 = h2 +1;//重新设置第一组的开始位置
    }
	// 如果根据分组的长度分出奇个组，则最后一个组没有与其他组归并，还放在数组的最后
	while (l1 < (int)vtOrder.size())
	{
		vtMerge[m++] = vtOrder[l1++];
	}
}

// 归并排序函数
void MergeSort(vector<int> &vtArr)
{
	int nLen = 1;//归并组的长度
	vector<int> vtMerge;//存放归并后的数组
	vtMerge.resize(vtArr.size());
	while (nLen < (int)vtArr.size())
	{
		Merge(vtArr, vtMerge, nLen);
		vtArr = vtMerge;// 将归并后的数组复制到原数组
		nLen *= 2;//二路归并，每次归并长度加倍
	}
}

// 归并排序也可以使用递归的方法，代码看起来更简洁，但是递归这种算法天然有劣势，就是
// 因为递归需要保存递归函数的局部变量等信息，需要额外的栈空间，如果递归
// 深度太深会导致栈溢出,而且大量的函数调用在效率上也会降低程序性能，所以其实如果
// 不是必须使用，一般不建议使用递归算法

// nStart数组的开始下标位置，nEnd数组的结束下标位置
void MergeSortUseRecursion(vector<int> &vt, int nStart, int nEnd)
{
    int mid = (nEnd + nStart) / 2;
    if (nEnd - nStart > 2)
    {
        // 需要递归,把数组分成两部分分别递归，让两部分子数组从无序变成有序
        MergeSortUseRecursion(vt, nStart, mid);
        MergeSortUseRecursion(vt, mid + 1, nEnd);
    }

    // 经过上面的递归后，需要归并的两部分数据已经变成有序的
    // 此时对两个有序数组进行归并
    int l1 = nStart;
    int l2 = mid + 1;

    vector<int> vtTmp(nEnd - nStart + 1, 0);
    int nIndex = 0;
    while (l1 <= mid && l2 <= nEnd)
    {
        if (vt[l1] <= vt[l2])
        {
            vtTmp[nIndex++] = vt[l1++];
        }
        else
        {
            vtTmp[nIndex++] = vt[l2++];
        }
    }

    while (l1 <= mid)
    {
        vtTmp[nIndex++] = vt[l1++];
    }

    while (l2 <= nEnd)
    {
        vtTmp[nIndex++] = vt[l2++];
    }

    // 把归并好的数组复制回原来的数组
    for (auto item : vtTmp)
    {
        vt[nStart++] = item;
    }
}


/*********************************基数排序（桶排序）******************************/
/* 基数排序是针对关键字为整数类型时的排序方法，是一种很高效的排序方法
 * 基数排序算法的基本思想：设待排序的数据元素是m位d进制
 * 整数（不足m位的关键字在高位补0），设置d个桶
 * 令其编号分别为0,1,...d-1.首先按关键字最低的数组依次把各数据
 * 元素放到相应的桶中，然后按照桶号从小
 * 到大和进入桶中数据元素的先后顺序收集分配在各桶中的数据元素，
 * 这样就形成了数据元素集合的一个新的排
 * 列，称这样的一次排序过程为一次基数排序；再对一次基数排序
 * 得到的数据元素序列按关键字次低位的数值依
 * 次把各数据放到相应的桶中，然后按照桶号从小到大和进入桶中
 * 数据元素的先后顺序收集分配在各桶中的数据
 * 元素；这样的过程重复进行，当完成了第m次基数排序后，
 * 就得到了排好序的数据元素序列。
 */ 
//对十进制正整数进行排序
void RadixSort(vector<int> &vtArr)
{
	// 找出数组中的最大值
	int nMax = 0;
	for (int i=0; i<(int)vtArr.size(); ++i)
	{
		if (vtArr[i] > nMax)
		{
			nMax = vtArr[i];
		}
	}
	// 计算最大值有几位数
	int m = 0;//位数
	while (nMax != 0)
	{
		++m;
        nMax /= 10;
	}
	//初始化10个桶
	queue<int> buck[10];
	int q = 1;
	// 进行m次排序
	for (int i=0; i<m; ++i)
	{
		for (int j=0; j<(int)vtArr.size(); ++j)
		{
			// 提取第m位
			int w = (vtArr[j] / q) % 10;
			// 放到第w个桶
			buck[w].push(vtArr[j]);
		}
		// 取出桶中的元素
		for (int k=0, n=0; k<10; ++k)
		{
			while (!buck[k].empty())
			{
				vtArr[n++] = buck[k].front();
				buck[k].pop();//从队列中删除取出的数据
			}
		}
		q *= 10;
	}
}

void Display(vector<int> &vtArr)
{
    for (unsigned int i=0; i<vtArr.size(); ++i)
    {
        cout << vtArr[i] << " ";
    }
    cout << endl;
}

int main()
{
    vector<int> vtArr;
    vtArr.push_back(3);
    vtArr.push_back(9);
    //vtArr.push_back(-4);
    vtArr.push_back(100);
    vtArr.push_back(3);
   // vtArr.push_back(-40);
    vtArr.push_back(0);
    vtArr.push_back(7);
    vtArr.push_back(12);
    vtArr.push_back(92);
    vtArr.push_back(182);
    vtArr.push_back(123);
    
    vector<int> vtArr1 = vtArr;
    vector<int> vtArr2 = vtArr;
    vector<int> vtArr3 = vtArr;
    vector<int> vtArr4 = vtArr;
    vector<int> vtArr5 = vtArr;
    vector<int> vtArr6 = vtArr;
    vector<int> vtArr7 = vtArr;
    cout << "*******没有排序*****" << endl;
    Display(vtArr);

    cout << "*******直接插入排序法*****" << endl;
    InsertionSort(vtArr1);
    Display(vtArr1);

    cout << "*******希尔排序法*****" << endl;
    ShellSort(vtArr2);
    Display(vtArr2);

    cout << "*******直接选择排序法*****" << endl;
    SelectSort(vtArr3);
    Display(vtArr3);

    cout << "*******堆排序法*****" << endl;
    HeapSort(vtArr4);
    Display(vtArr4);

    cout << "*******冒泡排序法*****" << endl;
    BubbleSort(vtArr);
    Display(vtArr);

    cout << "*******快速排序法*****" << endl;
    QuickSort(vtArr5, 0, vtArr.size() - 1);
    Display(vtArr5);

    cout << "*******归并排序法*****" << endl;
    MergeSort(vtArr6);
    Display(vtArr6);

    cout << "*******基数排序法*****" << endl;
    RadixSort(vtArr7);
    Display(vtArr7);
}
各种算法的时间复杂度和稳定性：