投稿
  1. 首页
  2. 随笔

数据结构（C语言）八大排序

qq安全卫士 • 2022-12-15 • 随笔 • 阅读 14

数据结构（C语言）八大排序,第1张

数据结构（C语言）八大排序

排序
1.算法描述
2.代码实现
3.效率分析(时间复杂度,空间复杂度,稳定性)

稳定性:针对关键字相同的数据(相同的数字),排序前如果A在A’的前面,排完序后还能保证A在A’的前面,则算法稳定,否则不稳定
通俗的来讲就是不跳跃的交换数据就是稳定的

目录
  • 1.插入排序
  • 2.希尔排序
  • 3.冒泡排序
  • 4.快速排序
    • 递归写法
    • 非递归写法
  • 5.选择排序
  • 6.堆排序
  • 7.归并排序
  • 8.基数排序/桶排序
  • 第"9"个排序:链表排序
  • 测试

1.插入排序

也叫简单插入排序或者直接插入排序
算法描述:从当前位置开始,从后往前找比当前数字小的,插入到这个小的数字后面;
在找的过程中, 如果发现一个比当前数字大的, 同时将这个数字往后挪动
特点:数据越有序越快,完全有序则为O(n)

//插入排序
void InsertSort(int* arr, int len)//O(n^2),O(1)
{
	//没有跳跃式的交换数据,所以是稳定的
	int tmp;
	int j;
	for (int i = 1; i < len; i++)//i是当前需要处理的数字的下标
	{
		tmp = arr[i];
		for (j = i - 1; j >= 0; j--)//从后往前找位置,找比当前数字小的,同时移动数据
		{
			if (arr[j] > tmp)//该数据需要后移
			{
				arr[j + 1] = arr[j];
			}
			else
			{
				//arr[j + 1] = tmp;
				break;
			}
		}
		arr[j+1] = tmp;
	}
}
2.希尔排序

直接插入排序越有序越快是希尔排序的一个理论基础

算法描述:间隔式分组,利用直接插入排序排序让组内有序;缩小分组再排序;直到缩为1组,完全有序

//一趟希尔排序,gap为组数(间隔)
//不稳定,因为有跳跃式的交换数据
//时间复杂度:O(n^1.3~1.5)  空间复杂度O(1)
static void Shell(int* arr, int len, int gap)
{
	int tmp;
	int j;
	for (int i = gap; i < len; i++)//从"第二个"数据开始
	{
		tmp = arr[i];
		for (j = i - gap; j >= 0; j -= gap)
		{
			if (arr[j] > tmp)
			{
				arr[j + gap] = arr[j];
			}
			else
			{
				break;
			}
		}
		arr[j + gap] = tmp;
	}
}
void ShellSort(int* arr, int len)
{
	int d[] = { 5,3,1 };
	for (int i = 0; i < sizeof(d) / sizeof(d[0]); i++)
	{
		Shell(arr, len, d[i]);
	}
}
3.冒泡排序

算法描述：两两比较(相邻),大的往后走

void BubbleSort(int* arr, int len)//O(n^2),O(1),稳定
{
	int tmp;
	for (int i = 0; i < len - 1; i++)
	{
		for (int j = 0; j + 1 < len - i; j++)//小心j+1越界
		{
			if (arr[j] > arr[j + 1])
			{
				tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}
4.快速排序

找到一个基准(第一个数据)
1.从后往前找比基准小的数据往前移动
2.从前往后找比基准大的数据往后移动,
3.重复1、2直到找到基准.
最大的缺点:
越有序越慢,完全有序O(n^2).
空间复杂度大,是O(long n)
不稳定

递归写法 
//快速排序(考试重点)

//一次划分,考试的重点
int Partition(int* arr, int low, int high)//O(n),O(1),不稳定
{
	int tmp = arr[low];//基准
	while (low < high)
	{
		while (low= tmp)
			high--;
		arr[low] = arr[high];
		while (low < high && arr[low] <= tmp)
			low++;
		arr[high] = arr[low];
	}
	arr[low] = tmp;
	return low;
}

void Quick(int* arr, int low, int high)
{
	int par = Partition(arr, low,high);
	if(low < par-1)//保证前面至少有两个数字
	{
		Quick(arr, low, par - 1);
	}
	if (par + 1 < high)
	{
		Quick(arr,par+1,high);
	}
}

//快速排序
void QuickSort(int* arr, int len)//O(nlogn),O(logn),不稳定,越有序越慢
{
	Quick(arr,0,len-1);
}
非递归写法 
//非递归的快速排序
void QuickSort1(int* arr, int len) 
{
	//创建一个栈,用于存放每个划分段的起始和结尾下标
	int* index = (int*)malloc(len*sizeof(int));//不好,可以使用STL中的stack
	assert(index != NULL);
	int top = 0;//栈顶指针,当前可以存放数据的下标
	int low;//起始下标
	int high;//结尾下标
	//先入起始下标,再如结尾下标
	index[top++] = 0;
	index[top++] = len - 1;
	while (top > 0)//栈不空
	{
		//先出结尾下标,再出起始下标
		high = index[--top];
		low = index[--top];
		int par = Partition(arr,low,high);
		//如果左边超过一个数据,需要继续入栈
		if (low < par - 1)//先入起始下标,再如结尾下标
		{
			index[top++] = low;
			index[top++] = par-1;
		}
		//如果右边超过一个数据,需要继续入栈
		if (par + 1 < high)
		{
			index[top++] = par + 1;
			index[top++] = high;
		}
	}
	free(index);
}
5.选择排序

每次都从待排序中找到最小值和待排序的第一个交换

void SelectSort(int* arr, int len)//O(n^2),O(1),不稳定
{
	int tmp;
	int minIndex;//最小值的下标
	for (int i = 0; i < len - 1; i++)
	{
		minIndex = i;
		for (int j = i + 1; j < len; j++)
		{
			if (arr[minIndex] > arr[j])
			{
				minIndex = j;
			}
		}
		if (minIndex != i)
		{
			tmp = arr[minIndex];
			arr[minIndex] = arr[i];
			arr[i] = tmp;
		}
	}
}
6.堆排序 
//父-->子:i--->2*i+1,2*i+2
//子-->父:i--->(i-1)/2
//堆调整
void HeapAdjust(int* arr, int start, int end)//O(log n)
{
	int tmp = arr[start];
	for (int i = 2 * start + 1; i <= end;i=2*i+1)
	{
		if (i < end && arr[i] < arr[i + 1])//有右孩子,并且左孩子的值小于右孩子的值
		{
			i++;
		}//i一定是左右孩子的最大值
		if (arr[i] > tmp)
		{
			arr[start] = arr[i];
			start = i;
		}
		else
		{
			break;
		}
	}
	arr[start] = tmp;
}
//堆排序
void HeapSort(int* arr, int len)//O(nlogn),O(1),不稳定
{
	int i;
	//建立大根堆,从后往前,多次调整
	for ( i = (len - 1 - 1) / 2; i >= 0; i--)//O(nlogn)
	{
		HeapAdjust(arr, i, len - 1);
	}
	//每次都将根和待排序的最后一个交换,然后再调整
	int tmp;
	for (i = 0; i < len - 1; i++)//O(nlogn)
	{
		//交换
		tmp = arr[0];
		arr[0] = arr[len - 1 - i];
		arr[len - 1 - i] = tmp;

		HeapAdjust(arr, 0, len - 1 - i - 1);
	}
}
7.归并排序

将两段有序的数据合并成一段有序的数据,直到所有的数据有序(2路归并)

//一次归并,gap为归并段的长度
static void Merge(int* arr, int len, int gap)//O(n),一次归并的时间复杂度
{
	int low1 = 0;
	int high1 = low1 + gap - 1;
	int low2 = high1 + 1;
	int high2 = low2 + gap  < len?low2+gap-1:len-1;

	int* brr = (int*)malloc(len * sizeof(int));
	assert(brr != NULL);

	int i = 0;//brr的下标
	//有两个归并段
	while (low2 
8.基数排序/桶排序 

带头文件"lqueue.h"
 

static int GetFigur(int* arr, int len)
{
	int max = arr[0];
	for (int i = 0; i < len; i++)
	{
		if (max < arr[i])
		{
			max = arr[i];
		}
	}
	int count = 0;
	while (max != 0)
	{
		count++;
		max /= 10;
	}
	return count;
}

//获取十进制整数右数第figur位的数字,figur从0开始
//例如(123,0)-->3  (123,1)-->2  (123,2)-->1  (123,3)-->0
static int GetNum(int n, int figur)
{
	for (int i = 0; i < figur; i++)
	{
		n /= 10;
	}
	return n % 10;
}
//基数排序
void RadixSort(int* arr, int len)//O(d*n),O(n),稳定
{
	HNode queArr[10];
	for (int i = 0; i < 10; i++)
	{
		InitQueue(&queArr[i]);
	}
	//得到最大数字的位数,确定进队和出队的趟数
	int count = GetFigur(arr, len);
	int index;
	for (int i = 0; i < count; i++)//处理每个数字从右往左的第i个数
	{
		for (int j = 0; j < len; j++)//遍历数组并入队
		{
			index = GetNum(arr[j], i);
			Push(&queArr[index], arr[j]);//将数字放入到对应的队列
		}
		//依次出队
		int j = 0;
		for (int k = 0; k < 10; k++)
		{
			while (!IsEmpty(&queArr[k]))
			{
				Pop(&queArr[k], &arr[j++]);
			}
		}
	}

	for (int i = 0; i < 10; i++)
	{
		Destroy(&queArr[i]);
	}
}

 
第"9"个排序:链表排序 

1.单链表存放数据时我们用什么排序?(冒泡,选择排序)
 2.双向链表存放数据我们用什么排序?(快速排序,STL中的list为双向链表)
 
测试 

void Show(int* arr, int len)
{
	for (int i = 0; i < len; i++)
	{
		printf("%d ", arr[i]);
	}
}
int main()
{
	int arr[] = { 34,2,0,15,78,90,45,67,1234 };
	//SelectSort(arr, sizeof(arr) / sizeof(arr[0]));
	//HeapSort(arr, sizeof(arr) / sizeof(arr[0]));
	MergeSort(arr, sizeof(arr) / sizeof(arr[0]));
	//int count = GetFigur(arr, sizeof(arr) / sizeof(arr[0]));
	//printf("count==%dn", count);
	//RadixSort(arr, sizeof(arr) / sizeof(arr[0]));
	Show(arr, sizeof(arr) / sizeof(arr[0]));
	return 0;
}

					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5612589.html
赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
qq安全卫士 qq安全卫士 一级用户组
0 0
上一篇 2022-12-15
下一篇 2022-12-15

发表评论

登录后才能评论

评论列表（0条）

保存