C++八大排序算法

C++八大排序算法-即刻学术
#include <iostream>
using namespace std;
 
//冒泡排序:从前向后比,每次选出最大的放后面
void Bubble_Sort1(int a[], int n) {
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j<n - 1 - i; j++)
		{
			if (a[j]>a[j + 1]) // 这里是从小到大排序,如果是从大到小排序,只需将“>”换成“<”
			{
				int temp;
				temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
			}
		}
	}	
}
//冒泡排序:从后向前比,每次选出最小的放前面
void Bubble_Sort2(int a[], int n) {
	for (int i = 0; i < n - 1; i++) {
		for (int j = n - 1; j > i; j--)
		{
			if (a[j - 1]>a[j])
			{
				int temp;
				temp = a[j];
				a[j] = a[j - 1];
				a[j - 1] = temp;
			}
		}
	}
}
//快速排序
void Quick_Sort(int a[], int left, int right)
{
	if (left< right)
	{
		int i = left, j = right, temp = a[left];
		while (i < j)
		{
			while (i < j && a[j] >= temp) // 从右向左找第一个小于x的数  
				j--;
			if (i < j) {
				a[i] = a[j];
				i++;
			}	
			while (i < j && a[i]< temp) // 从左向右找第一个大于等于x的数  
				i++;
			if (i < j) {
				a[j] = a[i];
				j--;
			}				
		}
		a[i] = temp;
		Quick_Sort(a, left, i - 1); // 递归调用  
		Quick_Sort(a, i + 1, right);
	}
}
//直接选择排序
void Select_Sort(int a[], int n)
{
	int i, j, min;
	for (i = 0; i < n-1; i++)//i为已排序序列的末尾
	{
		min = i;			//记录最小值的位置
		for (j = i + 1; j < n; j++) {
			if (a[j] < a[min])			//找出未排序序列中的最小值
				min = j;
		}			
		if (min != i)
			swap(a[i], a[min]);		//swap()是在std::标准名词空间中的
	}
}
图解大根堆 排序 https://blog.csdn.net/dream_follower/article/details/105202811
//堆排序:大根堆向下调整
//性质一:索引为i的左孩子的索引是(2 * i + 1);
//性质二:索引为i的右孩子的索引是(2 * i + 2);
//性质三:索引为i的父结点的索引是 floor((i - 1) / 2);
//参数start -- 被下调节点的起始位置(一般为0,表示从第1个开始)
//参数end   -- 截至范围(一般为数组中最后一个元素的索引)
void maxHeapDown(int a[], int start, int end)
{
    int current = start;            // 当前(current)节点的位置
    int left = 2 * current + 1;        // 为左(left)孩子的位置
    int tmp = a[current];            // 当前(current)节点的值
    for (; left <= end; current = left, left = 2 * left + 1)
    {
         // "left"是左孩子,"left+1"是右孩子
         if (left < end && a[left] < a[left + 1])
			 left++;        // 左右两孩子中选择较大者
         if (tmp >= a[left])
             break;        // 调整结束
         else            // 交换值
         {
             a[current] = a[left];
             a[left] = tmp;
         }
    }
}
//堆排序(升序):交换数据,将a[1]和a[n]交换,使a[n]是a[1...n]中的最大值;然后将a[1...n-1]重新调整为最大堆。
void Heap_Sort_Asc(int a[], int n)
{
    int i, tmp;
    for (i = n / 2 - 1; i >= 0; i--)		// 从(n/2-1) --> 0逐次遍历。遍历之后,得到的数组实际上是一个(最大)二叉堆。
        maxHeapDown(a, i, n - 1);
	//交换数据
    for (i = n - 1; i > 0; i--)
    {
        // 交换a[0]和a[i]。交换后,a[i]是a[0...i]中最大的。
        tmp = a[0];
        a[0] = a[i];
        a[i] = tmp;
        // 调整a[0...i-1],使得a[0...i-1]仍然是一个最大堆。
        maxHeapDown(a, 0, i - 1);
    }
}
//堆排序:小根堆向下调整
void minHeapDown(int a[], int start, int end)
{
	int current = start;            // 当前(current)节点的位置
	int left = 2 * current + 1;        // 为左(left)孩子的位置
	int tmp = a[current];            // 当前(current)节点的值
	for (; left <= end; current = left, left = 2 * left + 1)
	{
		// "left"是左孩子,"left+1"是右孩子
		if (left < end && a[left] > a[left + 1])
			left++;        // 左右两孩子中选择较小者
		if (tmp <= a[left])
			break;        // 调整结束
		else            // 交换值
		{
			a[current] = a[left];
			a[left] = tmp;
		}
	}
}
//堆排序(降序):交换数据,将a[1]和a[n]交换,使a[n]是a[1...n]中的最小值;然后将a[1...n-1]重新调整为最小堆。
void Heap_Sort_Desc(int a[], int n)
{
	int i, tmp;
	for (i = n / 2 - 1; i >= 0; i--)		// 从(n/2-1) --> 0逐次遍历。遍历之后,得到的数组实际上是一个(最小)二叉堆。
		minHeapDown(a, i, n - 1);
	//交换数据
	for (i = n - 1; i > 0; i--)
	{
		// 交换a[0]和a[i]。交换后,a[i]是a[0...i]中最小的。
		tmp = a[0];
		a[0] = a[i];
		a[i] = tmp;
		// 调整a[0...i-1],使得a[0...i-1]仍然是一个最小堆。
		minHeapDown(a, 0, i - 1);
	}
}
//希尔排序
void Shell_Sort(int a[], int n)
{
    int i, j, gap;
    // gap为步长,每次减为原来的一半。
    for (gap = n / 2; gap > 0; gap /= 2)
    {
        // 共gap个组,对每一组都执行直接插入排序
        for (i = 0; i < gap; i++)
        {
            for (j = i + gap; j < n; j += gap)
            {
                // 如果a[j] < a[j-gap],则寻找a[j]位置,并将后面数据的位置都后移。
                if (a[j] < a[j - gap])
                {
                    int tmp = a[j];
                    int k = j - gap;
                    while (k >= 0 && a[k] > tmp)
                    {
                        a[k + gap] = a[k];
                        k -= gap;
                    }
                    a[k + gap] = tmp;
                }
            }
        }
    }
}
//直接插入排序
void Insert_Sort(int a[], int n)
{
    int i, j, k;
    for (i = 1; i < n; i++)
    {     
        for (j = i - 1; j >= 0; j--)			 //为a[i]在前面的a[0...i-1]有序区间中找一个合适的位置
            if (a[j] < a[i])
                break;
 
        if (j != i - 1)						 //如找到了一个合适的位置
        {
            
            int temp = a[i];
            for (k = i - 1; k > j; k--)		//将比a[i]大的数据向后移
                a[k + 1] = a[k];
            
            a[k + 1] = temp;			//将a[i]放到正确位置上
        }
    }
}
//归并排序:将两个相邻有序区间合并成一个
void merge(int* a, int start, int mid, int end)
{
    int *tmp = new int[end - start + 1];    // tmp是汇总2个有序区的临时区域
    int i = start;            // 第1个有序区的索引
    int j = mid + 1;        // 第2个有序区的索引
    int k = 0;                // 临时区域的索引
 
    while (i <= mid && j <= end)
    {
        if (a[i] <= a[j])
            tmp[k++] = a[i++];
        else
            tmp[k++] = a[j++];
    }
    while (i <= mid)
        tmp[k++] = a[i++];
 
    while (j <= end)
        tmp[k++] = a[j++];
 
    // 将排序后的元素,全部都整合到数组a中。
    for (i = 0; i < k; i++)
        a[start + i] = tmp[i];
 
    delete[] tmp;
}
//归并排序:从上到下(递归方式)
void Merge_Sort(int* a, int start, int end)
{
    if (a == NULL || start >= end)
        return;
 
    int mid = (end + start) / 2;
	Merge_Sort(a, start, mid);		// 递归排序a[start...mid]
	Merge_Sort(a, mid + 1, end);		// 递归排序a[mid+1...end]
 
    // a[start...mid] 和 a[mid...end]是两个有序空间,
    // 将它们排序成一个有序空间a[start...end]
    merge(a, start, mid, end);
}
//基数排序:计算数组里最大位数,即为进行排序次数
int maxbit(int a[], int n)
{
	int d = 1; //保存最大的位数
	int p = 10;
	for (int i = 0; i < n; i++)
	{
		while (a[i] >= p)
		{
			p *= 10;
			d++;
		}
	}
	return d;
}
//基数排序
void Radix_Sort(int a[], int n) 
{
	int d = maxbit(a,n);
	int *tmp = new int[n];		//int tmp[n]错误定义,数组长度必须是整数常量或整数符号常量,想要用变量设置大小,必须用动态分配 
	int count[10]; //计数器
	int i, j, k;
	int radix = 1;
	for (i = 1; i <= d; i++) //进行d次排序
	{
		for (j = 0; j < 10; j++)
			count[j] = 0; //每次分配前清空计数器
		for (j = 0; j < n; j++)
		{
			k = (a[j] / radix) % 10; //统计每个桶中的记录数
			count[k]++;
		}
		for (j = 1; j < 10; j++)
			count[j] = count[j - 1] + count[j]; //这时count里的值表示在tmp中的位置(减一为tmp里的存储下标)
		for (j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
		{
			k = (a[j] / radix) % 10;
			tmp[count[k] - 1] = a[j];
			count[k]--;			//用于一个桶中有多个数,减一为桶中前一个数在tmp里的位置
		}
		for (j = 0; j < n; j++) //将临时数组的内容复制到data中
			a[j] = tmp[j];
		radix = radix * 10;
	}
	delete[] tmp;
}
 
int main()
{
	int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
	int len = sizeof(arr) / sizeof(*arr);			//int len = (int) sizeof(arr) / sizeof(arr[0]);
	//Bubble_Sort1(arr, len);
	//Bubble_Sort2(arr, len);
	//Quick_Sort(arr, 0, len - 1);
	//Select_Sort(arr, len);
	//Heap_Sort_Asc(arr, len);
	//Heap_Sort_Desc(arr,len);
	//Shell_Sort(arr, len);
	//Insert_Sort(arr, len);
	//Merge_Sort(arr, 0, len - 1);
	Radix_Sort(arr, len);
	cout << "排序后的数组元素:" << endl;
	for (int i = 0; i < len; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
	return 0;	
}

给TA买糖
共{{data.count}}人
人已赞赏
后端/架构建站教程技术活软件工具

OneTypecho - Typecho多端小程序开源!by 即刻学术

2021-5-11 22:40:30

后端/架构技术活

在linux服务器下实现对网站测试压力

2021-9-12 10:52:53

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索