常见排序集锦-C语言实现数据结构

这篇具有很好参考价值的文章主要介绍了常见排序集锦-C语言实现数据结构。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

排序的概念

常见排序集锦

     1.直接插入排序

     2.希尔排序

     3.选择排序

     4.堆排序

     5.冒泡排序

     6.快速排序

            hoare 

            挖坑法

            前后指针法

            非递归

     7.归并排序

            非递归

排序实现接口

算法复杂度与稳定性分析


排序的概念
      排序 :所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。
    

常见排序集锦-C语言实现数据结构,数据结构,数据结构,c语言

这里推荐一个网站 数据结构和算法动态可视化 (Chinese) - VisuAlgo

它可以让我们更加清晰的看清楚排序的过程。

排序实现接口

                                                                 sort.h

#include<stdlib.h>
#include<stdio.h>
#include<assert.h>
#include<time.h>

// 插入排序
void InsertSort(int* a, int n);

// 希尔排序
void ShellSort(int* a, int n);

// 选择排序
void SelectSort(int* a, int n);

// 堆排序
void AdjustDwon(int* a, int n, int root);
void HeapSort(int* a, int n);

// 冒泡排序
void BubbleSort(int* a, int n)

// 快速排序递归实现

// 1.快速排序hoare版本
int PartSort1(int* a, int left, int right);

// 2.快速排序挖坑法
int PartSort2(int* a, int left, int right);

// 3.快速排序前后指针法
int PartSort3(int* a, int left, int right);

void QuickSort(int* a, int left, int right);

// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)

// 归并排序递归实现
void MergeSort(int* a, int n)

// 归并排序非递归实现
void MergeSortNonR(int* a, int n)

                                            

1.插入排序

思想:把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列

常见排序集锦-C语言实现数据结构,数据结构,数据结构,c语言

实现:
void InsertSort(int* arr, int n)
{
	// i< n-1 最后一个位置就是 n-2
	for (int i = 0; i < n - 1; i++)
	{
		//[0,end]的值有序,把end+1位置的值插入,保持有序
		int end = i;
		int tmp = arr[end + 1];

		while (end >= 0)
		{
			if (tmp < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}

		arr[end + 1] = tmp; 
		// why?  end+1 
		//break 跳出 插入 因为上面end--;
        //为什么不在else那里插入?因为极端环境下,假设val = 0,那么end-- 是-1,不进入while , 
        //所以要在外面插入
	}
}

为什么这里 for 循环 i < n-1 ? 如图所示:

常见排序集锦-C语言实现数据结构,数据结构,数据结构,c语言


2.希尔排序

希尔排序又称缩小增量法,思想 :算法先将要排序的一组数按某个增量 gap 分成若干组,每组中记录的下标相差 gap .对每组中全部元素进行排序,然后再用一个较小的增量对它进行分组,在每组中再进行排序。当增量减到1时( == 直接插入排序),整个要排序的数被分成一组,排序完成。

希尔排序可以理解为两个步骤:1.预排序 2.直接插入排序
常见排序集锦-C语言实现数据结构,数据结构,数据结构,c语言
常见排序集锦-C语言实现数据结构,数据结构,数据结构,c语言

如下图:

常见排序集锦-C语言实现数据结构,数据结构,数据结构,c语言

 实现:①

void ShellSort(int* arr, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;  
		//gap = gap / 2;

	for (int j = 0; j < gap; j++)
	{
		for (int i = j; i < n - gap; i = i + gap)
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (tmp < arr[end])
				{
					arr[end + gap] = arr[end];
					end = end - gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}
}

②:在①的基础上进行简单的优化

void ShellSort(int* arr, int n)
{
	//gap > 1 时 ,预排序
	//gap = 1 时,直接插入排序
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;  //加1意味着最后一次一定是1 ,当gap = 1 时,就是直接排序
		//gap = gap / 2;

		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (tmp < arr[end])
				{
					arr[end + gap] = arr[end];
					end = end - gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		 }
	}

}
为什么for循环内,i < n-gap  ?
常见排序集锦-C语言实现数据结构,数据结构,数据结构,c语言

gap的取值?

这里看个人习惯,上述中是gap一开始为n,进入循环后每次 /3 ,之所以+1是为了保证最后一次循环gap一定为1。当然 /2 也是可以的,/2 就可以最后不用+1。

希尔排序的特性总结:

1. 希尔排序是对直接插入排序的优化。
2. gap > 1 时都是预排序,目的是让数组更接近于有序。当 gap == 1 时,数组已经接近有序的了,这样就会很快。这样整体而言,可以达到优化的效果。
3. 希尔排序的时间复杂度不好计算,因为 gap 的取值方法很多,导致很难去计算,希尔排序的时间复杂度都不固定。
4.排升序,gap 越大,大的数更快到后面,小的数可以更快到前面,但是越不接近有序
                  gap越小,越接近有序 ,当gap = 1 时,就是直接插入排序。

3.选择排序

思想:每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完 。

常见排序集锦-C语言实现数据结构,数据结构,数据结构,c语言

实现:这里简单做了一下优化,每次遍历不仅仅选出最小的,也选出最大的。

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void SelectSort(int* arr, int n)
{
	assert(arr);

	int left = 0; //开始位置
	int right = n - 1; //结束位置

	while (left < right)
	{
		int min = left;
		int max = left;

		for (int i = left + 1; i <= right; i++)
		{
			if (arr[i] < arr[min])
				min = i;

			if (arr[i] > arr[max])
				max = i;
		}

		Swap(&arr[left], &arr[min]);

		//如果 left 和 max 重叠 ,那么要修正 max 的位置
		if (left == max)
		{
			max = min;
		}

		Swap(&arr[right], &arr[max]);

		left++;
		right--;

	}

}

4.堆排序

思想:堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆,排降序建小堆。

常见排序集锦-C语言实现数据结构,数据结构,数据结构,c语言

实现:建堆方式有两种,这里采用向下调整方式建堆

typedef int HPDataType;

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void AdjustDown(HPDataType* arr, int size, int parent)//向下调整
{

	int child = parent * 2 + 1;

	while (child < size)
	{
		if (arr[child + 1] > arr[child] && child + 1 < size)
		{
			child++;
		}

		if (arr[child] > arr[parent])
		{
			Swap(&(arr[child]), &(arr[parent]));
			parent = child;
			child = (parent * 2) + 1;
		}
		else
		{
			break;
		}
	}

}


void HeapSort(int* arr, int n)
{
    //建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, n, i);
	}
    
    //排序
	int end = n - 1;
	while (end > 0)
	{
		Swap(&(arr[0]), &(arr[end]));
		AdjustDown(arr, end, 0);
		end--;
	}

}

5.冒泡排序

思想:根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置,冒泡排序的特点是:将键值较大的记录向序列的尾部移动,键值较小的记录向序列的前部移动。

可参考:冒泡

常见排序集锦-C语言实现数据结构,数据结构,数据结构,c语言

实现:

void BubbleSort(int* arr, int n)
{
	assert(arr);

	for (int i = 0; i < n; i++)
	{
		int flag = 1;
		for (int j = 0; j < n - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				Swap(&arr[j], &arr[j + 1]);
				flag = 0;
			}
		}

		//如果没有发生交换,说明有序,直接跳出
		if (flag == 1)
			break;
	}

}

6.快速排序

思想:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止

hoare版本

常见排序集锦-C语言实现数据结构,数据结构,数据结构,c语言常见排序集锦-C语言实现数据结构,数据结构,数据结构,c语言

 方法如下:

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

int PartSort1(int* arr, int begin, int end)
{
	int left = begin;
	int right = end;

	//keyi 意味着保存的是 key 的位置
	int keyi = left;

	while (left < right)
	{
		//右边先走,找小
		while (left < right && arr[right] >= arr[keyi])
		{
			right--;
		}

		//左边再走,找大
		while (left < right && arr[left] <= arr[keyi])
		{
			left++;
		}

		//走到这里意味着,右边的值比 key 小,左边的值比 key 大
		Swap(&arr[left], &arr[right]);
	}

	//走到这里 left 和 right 相遇 
	Swap(&arr[keyi], &arr[left]);

	keyi = left; //需要改变keyi的位置

	return keyi;
}

挖坑法

 方法如下:

int PartSort2(int* arr, int begin, int end)
{
	int key = arr[begin];

	int piti = begin;

	while (begin < end)
	{
		//右边先走,找小,填到左边的坑里去,这个位置形成新的坑
		while (begin < end && arr[end] >= key)
		{
			end--;
		}

		arr[piti] = arr[end];
		piti = end;

		//左边再走,找大
		while (begin < end && arr[begin] <= key)
		{
			begin++;
		}

		arr[piti] = arr[begin];
		piti = begin;
	}

	//相遇一定是在坑位
	arr[piti] = key;
	return piti;

}

前后指针法

常见排序集锦-C语言实现数据结构,数据结构,数据结构,c语言 方法如下:

int PartSort3(int* arr, int begin, int end)
{
	int key = begin;

	int prev = begin;

	int cur = begin + 1;

	//优化-三数取中
	int midi = GetMidIndex(arr, begin, end);
	Swap(&arr[key], &arr[midi]);

	while (cur <= end)
	{
		if (arr[cur] < arr[key] && prev != cur )
		{
			prev++;
			Swap(&arr[prev], &arr[cur]);
		}

		cur++;
	}

	Swap(&arr[key], &arr[prev]);
	key = prev;

	return key;
}

实现:以上三种方法都是采用函数的方式实现,这样方便调用。另外,以上方法都是单趟排序,如果要实现完整的排序还是要采用递归的方法,类似于二叉树的前序遍历

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void QuickSort(int* arr, int begin,int end)
{

	//当区间不存在或者区间只要一个值,递归返回条件
	if (begin >= end)
	{
		return;
	}

	if (end - begin > 20) //小区间优化一般在十几
	{
		//int keyi = PartSort1(arr, begin, end);
        //int keyi = PartSort2(arr, begin, end);
        int keyi = PartSort3(arr, begin, end);

		//[begin , keyi - 1] keyi [keyi + 1 , end]
		//如果 keyi 的左区间有序 ,右区间有序,那么整体就有序

		QuickSort(arr, begin, keyi - 1);
		QuickSort(arr, keyi + 1, end);
	}
	else
	{
		InsertSort(arr + begin, end - begin + 1);//为什么+begin,因为排序不仅仅排序左子树,还有右子树
		                                         //为什么+1 ,因为这个区间是左闭右闭的区间.例:0-9 是10个数 所以+1
	}
}

优化:

1. 三数取中法选key
2. 递归到小的子区间时,可以考虑使用插入排序(已在实现中使用)
int GetMidIndex(int* arr, int begin, int end)
{
	//begin   mid    end

	int mid = (begin + end) / 2;
	if (arr[begin] < arr[mid])
	{
		if (arr[mid] < arr[end])
		{
			return mid;
		}
		else if(arr[begin] < arr[end])  //走到这里说明 mid 是最大的
		{
			return end;
		}
		else
		{
			return begin;
		}
	}
	else // arr[begin] > arr[mid]
	{

		if (arr[mid] > arr[end])
		{
			return mid;
		}
		else if (arr[begin] < arr[end])  // 走到这里就是 begin end 都大于 mid
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
}

非递归版本

非递归版本需要用到栈,这里是用c语言实现,所以需要手动实现一个栈

如果使用c++的话,可以直接引用栈。

这里栈的实现暂时省略,后期会给出链接。这里暂时知道一下就行。

 简图:

常见排序集锦-C语言实现数据结构,数据结构,数据结构,c语言

//非递归
//递归问题:极端场景下,深度太深,会出现栈溢出
//1.直接改成循环--例:斐波那契数列、归并排序
//2.用数据结构栈模拟递归过程
void QuickSortNonR(int* arr, int begin, int end)
{
	ST st;
	StackInit(&st);

	StackPush(&st, end);
	StackPush(&st, begin);

	while (!StackEmpty(&st))
	{
		int left = StackTop(&st);
		StackPop(&st);

		int right = StackTop(&st);
		StackPop(&st);

		int keyi = PartSort3(arr, left, right);

		//[left , keyi - 1]   keyi    [keyi + 1 , right]

		if (keyi + 1 < right)
		{
			StackPush(&st, right);
			StackPush(&st, keyi + 1);
		}

		if (left < keyi - 1)
		{
			StackPush(&st, keyi - 1);
			StackPush(&st, left);
		}

	}

	StackDestory(&st);
}

7.归并排序

思想:归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。 归并排序核心步骤:

 实现常见排序集锦-C语言实现数据结构,数据结构,数据结构,c语言

void _MergeSort(int* arr, int begin, int end, int* tmp)
{
	if (begin >= end)
		return;

	int mid = (begin + end) / 2;

	//[begin mid]  [mid+1,end]

	//递归
	_MergeSort(arr, begin, mid, tmp);
	_MergeSort(arr, mid + 1, end, tmp);

	//归并[begin mid]  [mid+1,end]
	int left1 = begin;
	int right1 = mid;

	int left2 = mid + 1;
	int right2 = end;

	int i = begin;//这里之所以等于begin 而不是等于0 是因为可能是右子树而不是左子树 i为tmp数组下标

	while (left1 <= right1 && left2 <= right2)
	{
		if (arr[left1] < arr[left2])
		{
			tmp[i++] = arr[left1++];
		}
		else
		{
			tmp[i++] = arr[left2++];
		}

	}

	//假如一个区间已经结束,另一个区间直接拿下来
	while (left1 <= right1)
	{
		tmp[i++] = arr[left1++];
	}

	while (left2 <= right2)
	{
		tmp[i++] = arr[left2++];
	}


	//把归并的数据拷贝回原数组 [begin mid]  [mid+1,end]
	// +begin 是因为可能是右子树    例:[2,3][4,5]
	//+1 是因为是左闭右闭的区间 0-9 是10个数据
	memcpy(arr + begin, tmp + begin, (end - begin + 1) * sizeof(int));

}

void MergeSort(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc");
		exit(-1);
	}

	_MergeSort(arr, 0, n - 1, tmp);

	free(tmp);
}

非递归版本:

思想:这里不能使用栈或者队列,因为栈或者队列适合前序遍历的替换,但是归并排序的思想属于后序遍历,栈和队列的特性导致后期可能无法使用前面的空间。

        这里因为是循环,所以可以设计一个变量 gap,当gap= 1 ,就一一进行归并,当gap = 2时,就两两进行归并,gap 每次 *2 。

如图:

常见排序集锦-C语言实现数据结构,数据结构,数据结构,c语言

 代码如下:

void MergeSortNonR(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc");
		exit(-1);
	}

	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			//[i , i + gap-1]  [i + gap , i + 2*gap-1]
			int left1 = i;
			int right1 = i + gap - 1;

			int left2 = i + gap;
			int right2 = i + 2 * gap - 1;

			int j = left1;

			while (left1 <= right1 && left2 <= right2)
			{
				if (arr[left1] < arr[left2])
				{
					tmp[j++] = arr[left1++];
				}
				else
				{
					tmp[j++] = arr[left2++];
				}

			}

			while (left1 <= right1)
			{
				tmp[j++] = arr[left1++];
			}

			while (left2 <= right2)
			{
				tmp[j++] = arr[left2++];
			}

		}

		memcpy(arr, tmp, sizeof(int) * n);

		gap *= 2;
	}

	free(tmp);
}

       但是上述代码涉及到一个问题,因为假设要排序的数据不是2的次方倍就会产生问题(和数据的奇偶无关),就会越界

例:

常见排序集锦-C语言实现数据结构,数据结构,数据结构,c语言

 所以我们需要对代码进行优化, 优化可以从两个方面进行:    

//1.归并完成全部拷贝回原数组
//采用修正边界的方法
//例:如果是9个数据 最后一个数据也要继续进行归并
//因为如果不归并的话,最后一次会全部拷贝回原数组,也就意味着9个数据,前8个归并,拷贝回去的最后一个数据因为没有进行归并而产生随机值。

//如果越界,就修正边界,继续进行归并

代码如下:

void MergeSortNonR(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc");
		exit(-1);
	}

	int gap = 1;
	while (gap < n)
	{
		//printf("gap=%d->", gap);

		for (int i = 0; i < n; i += 2 * gap)
		{
			//[i , i + gap-1]  [i + gap , i + 2*gap-1]
			int left1 = i;
			int right1 = i + gap - 1;

			int left2 = i + gap;
			int right2 = i + 2 * gap - 1;

			//监测是否出现越界
			//printf("[%d,%d][%d,%d]---", left1, right1, left2, right2);

			//修正边界
			if (right1 >= n)
			{
				right1 = n - 1;
				//[left2 , right2] 修正为一个不存在的区间
				left2 = n;
				right2 = n - 1;
			}
			else if (left2 >= n)
			{
				left2 = n;
				right2 = n - 1;
			}
			else if (right2 >= n)
			{
				right2 = n - 1;
			}

			//printf("[%d,%d][%d,%d]---", left1, right1, left2, right2);

			int j = left1;

			while (left1 <= right1 && left2 <= right2)
			{
				if (arr[left1] < arr[left2])
				{
					tmp[j++] = arr[left1++];
				}
				else
				{
					tmp[j++] = arr[left2++];
				}

			}

			while (left1 <= right1)
			{
				tmp[j++] = arr[left1++];
			}

			while (left2 <= right2)
			{
				tmp[j++] = arr[left2++];
			}

		}

		//printf("\n");

		memcpy(arr, tmp, sizeof(int) * n);

		gap *= 2;
	}

	free(tmp);
}

2.归并一组数据就拷贝一组数据回原数组

这样,如果越界就直接break跳出循环,后面的数据不进行归并。

void MergeSortNonR_2(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc");
		exit(-1);
	}

	int gap = 1;
	while (gap < n)
	{

		for (int i = 0; i < n; i += 2 * gap)
		{
			//[i , i + gap-1]  [i + gap , i + 2*gap-1]
			int left1 = i;
			int right1 = i + gap - 1;

			int left2 = i + gap;
			int right2 = i + 2 * gap - 1;

			//right1 越界 或者 left2 越界,则不进行归并
			if (right1 >= n || left2 > n)
			{
				break;
			}
			else if (right2 >= n)
			{
				right2 = n - 1;
			}

			int m = right2 - left1 + 1;//实际归并个数

			int j = left1;

			while (left1 <= right1 && left2 <= right2)
			{
				if (arr[left1] < arr[left2])
				{
					tmp[j++] = arr[left1++];
				}
				else
				{
					tmp[j++] = arr[left2++];
				}

			}

			while (left1 <= right1)
			{
				tmp[j++] = arr[left1++];
			}

			while (left2 <= right2)
			{
				tmp[j++] = arr[left2++];
			}

			memcpy(arr+i, tmp+i, sizeof(int) * m);

		}

		gap *= 2;
	}

	free(tmp);
}

以上两种方式的代码皆可,具体重要的还是思想。


算法复杂度与稳定性分析

       稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次 序保持不变,即在原序列中,r[i]=r[j],且r[i]r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排 序算法是稳定的;否则称为不稳定的。

常见排序集锦-C语言实现数据结构,数据结构,数据结构,c语言

 常见排序集锦-C语言实现数据结构,数据结构,数据结构,c语言文章来源地址https://www.toymoban.com/news/detail-659823.html

到了这里,关于常见排序集锦-C语言实现数据结构的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】—从冒泡排序丝滑过度快速排序(含C语言实现)

                                            食用指南:本文在有C基础的情况下食用更佳                                          🔥 这就不得不推荐此专栏了: C语言                                        ♈️ 今日夜电波:靴の花火—ヨルシカ            

    2024年02月08日
    浏览(39)
  • 【数据结构】—超级详细的归并排序(含C语言实现)

    ​                                         食用指南:本文在有C基础的情况下食用更佳                                          🔥 这就不得不推荐此专栏了: C语言                                        ♈️ 今日夜电波:斜陽—ヨルシカ            

    2024年02月08日
    浏览(44)
  • 数据结构__<八大排序> __插入排序 |希尔排序 |选择排序 |堆排序 |快速排序 |归并排序(C语言实现)

    目录 插入排序  希尔排序 选择排序 堆排序 冒泡排序 快速排序 hoare法 挖坑法 前后指针法 快排特性总结 三数取中优化 小区间优化 快排非递归 归并排序 归并排序非递归 计数排序 总结 OJ测试 1、元素集合越接近有序,直接插入排序算法的时间效率越高 2、时间复杂度:O(N^2

    2023年04月09日
    浏览(87)
  • 【数据结构】—从直接插入排序升级到希尔排序究极详解(含C语言实现)

                                            食用指南:本文在有C基础的情况下食用更佳                                          🔥 这就不得不推荐此专栏了: C语言                                         ♈️ 今日夜电波:透明で透き通って何にでもなれそ

    2024年02月08日
    浏览(51)
  • 【数据结构】常见排序算法——常见排序介绍、插入排序、直接插入排序、希尔排序

      在计算机科学中,排序是将一组数据按照指定的顺序排列的过程。排序算法由于执行效率的不同可以分为多种不同的算法。   通常情况下,排序算法可以分为两类,即 内部排序和外部排序 。内部排序是指数据全部加载到内存中进行排序,适用于数据量较小的情况,而

    2024年02月08日
    浏览(63)
  • 【数据结构】常见排序算法——常见排序介绍、选择排序(直接选择排序、堆排序)交换排序(冒泡排序)

      选择排序是一种简单但不高效的排序算法,其基本思想是从待排序的数据中选择最小(或最大)的元素放到已排序的数据末尾。具体操作步骤如下: (1)找到数据中最小的元素,并把它交换到第一个位置; (2)在剩下未排序的元素中找到最小的元素,并把它交换到已排

    2024年02月04日
    浏览(56)
  • 【数据结构】常见的排序算法

    常见的七大排序算法: 最好的情况是O(n),数组为升序 最坏的情况是O(n 2 ),数组为降序 元素集合越接近有序,直接插入排序算法的时间效率越高 时间复杂度:O(N^2) 空间复杂度:O(1),它是一种稳定的排序算法 稳定性:稳定 针对直接插入排序中,当数组属于降序时,时间复杂

    2024年02月14日
    浏览(39)
  • 数据结构-常见的排序算法

    目录 排序的概念及其运用 排序的概念 常见的排序算法 常见排序算法的实现 插入排序 插入排序 希尔排序(缩小增量排序) 选择排序 直接选择排序 堆排序 交换排序 冒泡排序 快速排序 归并排序 非比较排序 排序算法复杂度及稳定性分析 排序 :所谓排序,就是按照某个或者某

    2024年03月12日
    浏览(49)
  • 数据结构之常见排序算法

    排序:就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性:假设一组序列中,有两个相同的元素,在排序之后,两个相同元素的前后顺序颠倒了,说明这个排序算法是不稳定的,反之。 思路:把待排序的记录按其关键码值的大小

    2024年02月11日
    浏览(34)
  • 数据结构排序——详解快排及其优化和冒泡排序(c语言实现、附有图片与动图示意)

    上次讲了选择排序和堆排序:数据结构排序——选择排序与堆排序 今天就来快排和冒泡 快速排序(Quick Sort)是一种常用的排序算法,它是由英国计算机科学家Tony Hoare于1959年发明的。快速排序的基本思想是通过分治的策略将一个数组分成两个子数组,然后分别对这两个子数

    2024年01月25日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包