C++实现排序算法_c++从小到大排序

一、冒泡排序

上浮法 ：从数组末尾开始，连续比较相邻两个元素，使其符合排序。比较一个循环后，处于数组前排的元素最先符合（最大 or 最小），不再参与下一个循环的比较。

下沉法：从数组开头开始，连续比较相邻两个元素，使其符合排序。比较一个循环后，处于数组后排的元素最先符合（最大 or 最小），不再参与下一个循环的比较。

冒泡法最优时间复杂度可以达到O(n)，最差可以达到O（n^2）

【注】如果上一次循环已经符合排序，即没有交换过一次，则已经排序完成，得到结果，不需要再进行下一次循环

参考代码  C++实现

//冒泡排序-上浮 从小到大排序
void bubbleSort(vector<int>& nums) 
{
	//i记录参与比较的起始位置
	for (int i = 0; i < nums.size(); ++i) 
	{
		bool isSwap = false;//如果isSwap为true，则循环有交换操作
		for (int j = nums.size()-1; j > i; --j)
		{
			//逆序则交换
			if (nums[j] < nums[j - 1]) {
				swap(nums[j], nums[j - 1]);
				isSwap = true;
			}
		}
		//此轮循环已经有序，不需要再遍历
		if (isSwap == false) {
			break;
		}
	}
}

二、选择排序

个人理解选择排序可以概括为：为指定位置选择合适的值

以从小到大排序为例，具体做法是：以位置作为第一重循环，为第0的位置选入最小的值......以此类推

参考代码  C++实现

//选择排序 从小到大排序
void selectionSort(vector<int>& nums)
{
	//i记录参与比较的起始位置
	//为位置i寻找合适的值
	for (int i = 0; i < nums.size(); ++i)
	{
		int minIdx = i; //保存目前循环中最小的位置
		for (int j = i; j < nums.size(); ++j)
		{
			minIdx = nums[minIdx] > nums[j] ? j : minIdx;
		}
 
		if (minIdx != i) 
		{
			swap(nums[minIdx], nums[i]);
		}
	}
}

三、插入排序

个人理解插入排序可以概括为：把指定的值插入到合适的位置

以从小到大排序为例，具体做法是：从0位置开始遍历数组每个值，设其前面是有序的，将其插入到有序序列中合适位置

参考代码  C++实现

//插入排序 从小到大排序
void insertionSort(vector<int>& nums)
{
	for (int i = 1; i < nums.size(); ++i)
	{
		int temp = nums[i]; //将temp值插入合适位置
		int j = i;
		//向有序序列查找temp的位置
		while (j > 0 && temp < nums[j-1])
		{
			nums[j] = nums[j - 1];
			--j;
		}
		nums[j] = temp;
	}
}

四、归并算法

该算法采用分治法思想。把序列分解成若干子序列，使各子序列有序，并且将子序列有序合并得到最终有序序列。

递归法：自上而下解决问题。从逻辑上讲，递归法是先尝试排序数组，在排序中分解成了子数组进行排序。是1、8分成4，4；2、4分成2，2的过程

迭代法：自下而上解决问题。从逻辑上讲，迭代法是先排序最小子数组，然后合并排序大数组。是1、2，2合为4；4, 4合为8的过程

代码实现 C++ ——递归

vector<int> mergeSort(vector<int>& nums1, vector<int>& nums2)
{
	vector<int> mergeNums;
	//itn1 = nums1迭代器 itn2 = nums2迭代器
	auto itn1 = nums1.begin();
	auto itn2 = nums2.begin();
 
	while (nums1.end() != itn1 || nums2.end() != itn2 )
	{
		//如果nums1已经全部遍历，剩下的nums2全部push进结果数组中
		if (nums1.end() == itn1)
		{
			while (nums2.end() != itn2)
			{
				mergeNums.push_back(*itn2++);
			}
			break;
		}
		//如果nums2已经全部遍历，剩下的nums1全部push进结果数组中
		else if (nums2.end() == itn2)
		{
			while (nums1.end() != itn1)
			{
				mergeNums.push_back(*itn1++);
			}
			break;
		}
		//比较nums1和nums2将最小的成员存入结果数组中
		else
		{
			mergeNums.push_back(*itn2 < *itn1 ? *itn2++ : *itn1++);
		}
	}
	return mergeNums;
}
 
//递归法 从小到大排序
vector<int> Sort(vector<int>& nums)
{
	//如果数组数量小于2，则不需要排序，本来就有序
	if (nums.size() < 2)
	{
		return nums;
	}
 
	std::vector<int>::iterator start = nums.begin();
	std::vector<int>::iterator part = nums.begin() + (nums.size() >> 1);//位运算，右移一位相当于/2
	std::vector<int>::iterator end = nums.end();
 
	//把数组分解成2个子数组分别排序
	std::vector<int> nums1(start,part); 
	std::vector<int> nums2(part, end);
 
	nums1 = Sort(nums1);
	nums2 = Sort(nums2);
	return mergeSort(nums1, nums2);
}

代码实现-迭代法

void MergeSort(std::vector<int>& nums, const int start, const int part, const int end)
{
	std::vector<int> meArr;
	int p1 = start;
	int p2 = part;
	while (p1 != part || p2 != end)
	{
		if (p1 == part)
		{
			while (p2 != end)
			{
				meArr.push_back(nums[p2++]);
			}
		}
		else if (p2 == end)
		{
			while (p1 != part)
			{
				meArr.push_back(nums[p1++]);
			}
		}
		else
		{
			meArr.push_back(nums[p1] < nums[p2] ? nums[p1++] : nums[p2++]);
		}
	}
 
	//合并排序后反填充进入原数组
	int pos = start;
	for (auto it : meArr)
	{
		nums[pos++] = it;
	}
}
//迭代法-升序
void Sort(std::vector<int>& nums)
{
	//步长
	for (int i = 0; i < nums.size(); ++i)
	{
		int pos = 0;
		int len = 1 << i;
		while (pos < nums.size())
		{
			int part = pos + len;
			if (part >= nums.size())
			{
				part = nums.size() - 1;
			}
			int end = part + len;
			if (end >= nums.size())
			{
				end = nums.size() - 1;
			}
 
			MergeSort(nums, pos, part, end);
			pos += len*2;
		}
	}
}

五、快速排序

快速排序也是使用分治法的思想，所以在实现时会采用递归的方法。

选取一个基准值（以数组最左位置的值为例），把比基准值小的数值放到其左边，比基准值大的数值放到右边，然后根据基准值的位置分成左右子数组，子数组再使用此方法排序。递归下去，最终获取有序数组。

关于快速排序可以参考下列视频学习 快速排序算法_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1at411T75o

//快速排序 从小到大
int Partition(int A[], int left, int right)
{
	//以最左元素为基准值
	int pivot = A[left];
	while (left < right)
	{
		//交替遍历右项，如果A[high]>=pivot，则继续遍历high指针
		while (left < right && A[right] >= pivot)
		{
			--right;
		}
		//如果A[right]<pivot,把A[right]赋给A[left]，以实现把小于基准值的值放到左侧的目的
		A[left] = A[right];
		//交替遍历left指针
		while (left < right && A[left] <= pivot)
		{
			++left;
		}
		A[right] = A[left];
	}
	A[left] = pivot;
	//最后返回最新的基准值所在位置
	return left;
}
 
void QuickSort(int A[], int left, int right)
{
	if (left < right)
	{
		//获取基准值位置
		int pivot = Partition(A, left, right);
		//根据基准值的位置，分成左右2个子数组，递归下去
		QuickSort(A, left, pivot);
		QuickSort(A, pivot+1, right);
	}
}

六、希尔排序

希尔排序也称递减增量排序算法，是插入排序的更高效版本。

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

void ShellSort(std::vector<int>& arr)
{
    //step即增量
    for (int step = arr.size() / 2; step > 0; step /= 2)
    {
        //执行插入排序
        for (int pos = step; pos < arr.size(); ++pos)
        {
			//先选择需要插入的元素temp 记录此元素应该在的位置i
            int temp = arr[pos];
            int i = pos;
 
			//temp应该往前移动，因为temp比同组前面的元素更小
            while (i - step >= 0 && temp < arr[i - step])
            {
                arr[i] = arr[i - step];
                i -= step;
            }
			//插入temp
            arr[i] = temp;
        }
    }
}

七、堆排序

堆排序是利用堆这种数据结构设计的排序算法，可以看作是利用堆的性质的选择排序。

堆的定义：

堆在逻辑上是完全二叉树的结构；

堆结构要求子节点的键值总是不大于（或不小于）其父节点。

堆的使用：

1）对于一个完全二叉树，使用广度优先方式为堆的节点进行编号（见下图红色序号）。如果父节点的序号为k，则左孩子节点的序号为2k+1（如果存在左孩子），右孩子节点的序号为2k+2（如果存在右孩子）。由此可以推出，如果一个节点的序号为k，则父节点的序号为(k-1)/2；

2）堆的常用存储结构是数组，因为1）的性质，使用数组即节省内存，对于堆的各种操作也十分方便。

堆的分类：

大顶堆：父节点的值大于或等于其子节点，用于从小到大的升序排序；

小顶堆：父节点的值小于或等于其子节点，用于降序排序。

堆排序的步骤（请结合代码理解）：

首先假设输入数组为arr，待排序数组长度为len，可见，一开始len=arr.size

1）创建堆：将待排序的数组中的元素按照堆的要求进行调整，使其符合大顶堆的性质，此时root位置的值即为剩余未排序元素的最大值；

2）将1）中root位置的值arr[0]与数组未排序部分末尾数值arr[len]进行交换；

3）经过2），arr[len]已经成为已排序部分，使len--，继续重复1）2），直到len==0为止。

参考代码C++

//从pos位置往下调整,使其符合大根堆
void Max_Heapify(vector<int>&arr,int pos,int len)
{
	int child = (pos << 1) + 1;
	while (child < len)
	{
		//获取孩子中最大的
		//如果右孩子存在并且比左孩子大，则使用child代表右孩子
		if (child+1 < len && arr[child + 1] > arr[child])
		{
			child = child + 1;
		}
 
		//父节点和child孩子节点比较
		if (arr[pos] >= arr[child])
		{
			return;
		}
 
		swap(arr[pos], arr[child]);
		pos = child;
		child = (pos << 1) + 1;
	}
	return;
}
 
//堆排序
void HeapSort(vector<int>&arr)
{
 
    //此处len=arr.size()时即是步骤1）,即使未排序元素符合大根堆
	for (int len = arr.size(); len > 0; --len)
	{
		//从最后一个有孩子的节点开始调整，创建大根堆
		for (int i = (len - 2) >> 1; i >= 0; --i)
		{
			Max_Heapify(arr, i, len);
		}
		//此时，由于是大根堆，arr[0]一定是最大值，则放到数组len位置
		//len---arr.size()位置是已经排好序的部分
		swap(arr[0], arr[len-1]);
	}
}

八、计数排序

计数排序不是基于比较的排序，即不是基于对元素比较大小调整元素位置的比较方法。

计数排序的中心思想是开辟一个新的计数数组，然后：

1）把原数组的数值映射为计数数组的键值；等反向填充后，由于键值自带大小排序，所以排序问题解决；

2）把原数组的数值个数作为计数数组的数值；等反向填充后，就可以根据数值还原每个键值得个数；

结合1）2）就可以用O(N)的复杂度完成排序，因为只需要遍历一遍原数组，遍历一遍 计数数组并反向填充即可。

但是由于计数数组取决于数组中的最大值和最小值的差值。所以并不是适用于所有数据。

例如{1,6,66666，2333}这个数组，如果使用计数排序法，则需要额外开辟计数数组的大小为 66666-1=66665，是不合适的。

void CountSort(std::vector<int>& arr)
{
    //排除无效和有序数组
    if (arr.size() <= 1)
    {
        return;
    }
 
    int min = arr[0], max = arr[0];
 
    //遍历数组，获取最大值和最小值，用来确认计数数组的大小
    for (auto it : arr)
    {
        min = min > it ? it : min;
        max = max < it ? it : max;
    }
 
    //计数数组，共初始化max - min + 1个，初始计数为0
    std::vector<int> countArr(max - min + 1, 0);
 
    //再次遍历arr，保存计数结果
    for (auto it : arr)
    {
        int offset = it - min; //偏移量
        ++countArr[offset];
    }
 
    //反向填充有序结果
    int pos = 0;
 
    for (int i = 0; i < countArr.size(); ++i)
    {
        while (countArr[i]-- != 0)
        {
            arr[pos++] = i + min;
        }
    }
}

九、桶排序

桶排序是快速排序的升级版，同样是不基于比较的排序。

桶排序是使用某个函数，将待排数组中的值映射到不同的容器中，这些容器称作桶。

例如：为数组{29，25，3，49，9，37，21，43}排序。我们设置映射函数 bucket_Id = data / 10   ，则每个桶中数据的分布情况如下：

           

然后，我们为每个桶排序，使桶内有序。最后依次弹出，完成排序。

              

桶排序需要做什么：

1、选择合适的映射函数，使待排序数组合理分布在桶中；

2、为桶内排序选取合适的排序算法，尽量减小时间复杂度；

桶排序注意事项：

        根据上述桶排序原理，我们可以看出桶排序的基本思想是使用桶序完成一部分排序工作（记作工作A）；使用桶内排序完成另一部分排序工作（记作工作B）。

        如果我们映射函数选取不够好，使大量数据都处于同一桶中，则工作A对时间的节省效果会完全体现不出来，整体变成了基于比较的排序工作。

        所有使用桶排序算法，我们最好使输入的数据可以均匀的分配到每一个桶中，在额外空间充足的情况下，尽量增大桶的数量，这要求我们选取合适的映射函数。

参考代码C++

void BucketSort(vector<int>& arr)
{
    //获取最大值确认桶的规模
    int temp = arr[0];
 
    for (int it : arr)
    {
        temp = temp < it ? it : temp;
    }
 
    temp = temp / 10;
    vector<vector<int>> buckets(temp + 1);
 
    //进行桶排序
    for (int it : arr)
    {
        buckets[it / 10].push_back(it);
    }
 
    //桶内排序
    for (int i = 0; i < buckets.size(); ++i)
    {
        sort(buckets[i].begin(), buckets[i].end());
    }
 
    //反向填充
    temp = 0;
 
    for (auto itbut : buckets)
    {
        for (auto it : itbut)
        {
            arr[temp++] = it;
        }
    }
}

十、基数排序

基数排序也是一种基于桶的，非比较排序算法。

基数排序的基本思想是根据数组中每个元素各个数位上的数据分次排序。

例如：数组arr {29，25，3，49，9，37，21，43}

步骤：

1）因为数组arr中的元素为十进制数，所以先声明10个桶；

2）先根据个位数的数字把各元素放入桶中，即个位数字为0的元素放入0号桶，个位数字是5的元素放入5号桶，以此类推；

3）从0号桶开始遍历，依据桶内先入先出的原则将所有元素依次弹出，反填充入原数组；

4）经过2）3），arr中的所有元素依据个位数字从小到大的顺序排列了。再根据十位上的数字，把arr中各个元素放入桶中，即重复2）3）步骤，直到最大值的最高位数都遍历完成；

参考代码

void CardinalitySort(vector<int>& arr)
{
    // 分析数据：数组中是十进制数，所以定义10个桶
    vector<vector<int>> buckets(10);
 
    // 获取最大值，确认排序次数。排序次数为最大值的位数
    int temp = arr[0];
 
    for (int it : arr)
    {
        temp = it > temp ? it : temp;
    }
 
    temp = log10(temp);
 
    // 从个位数字开始（当i=0,代表遍历个位数字），依据每位上的数字入桶，然后依据先入先出的规则出桶
    for (int i = 0; i <= temp; ++i)
    {
        //入桶
        for (int it : arr)
        {
            //获取第i位的数:i=0 个位;i=1 十位; i 第10^i位
            int idx = pow(10, i + 1);
            idx = it % idx;
            idx = idx / pow(10, i);
            
            //入桶保存
            buckets[idx].push_back(it);
        }
 
        //出桶
        int indx = 0;
 
        for (int in = 0; in < buckets.size(); ++in)
        {
            for (int num : buckets[in])
            {
                arr[indx++] = num;
            }
 
            buckets[in].clear();
        }
    }
}

另外，基数排序的另外一种实现方法见博客：

基数排序的词频表方法_星星典典的博客-CSDN博客基数排序是非比较排序方法中比较重要的排序。一般情况下，我们都是基于FIFO桶对其实现。基于桶的方法见下面文章：(2条消息) C++实现排序算法_星星典典的博客-CSDN博客https://blog.csdn.net/ymhdt/article/details/123293536本文采用另外一种方式，基于词频表的实现。这里说的词频表可以理解为在数组中某一类数字出现的次数。在基数排序中，我们定义一张表，使用count数组作为容器，用于记录数组 “某位置...https://blog.csdn.net/ymhdt/article/details/124227995

总结

1、一般基于比较的排序算法适用范围较广；而不基于比较的排序都要求有特定的数据状况；

2、基数排序、计数排序和桶排序这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

• 基数排序：根据键值的每位数字来分配桶；
• 计数排序：每个桶只存储单一键值；
• 桶排序：每个桶存储一定范围的数值；