数据结构--八大排序

龙里出生的蛋 2024-01-06 原文

1.插入排序

1.1插入排序的思想

插入排序的思想跟摸牌很相似，从我们摸到第二张牌的开始，依次将摸到到牌依次有序的插入到手中，最后手牌变成了有序。

有了大致的思路，接下来就要细分插入排序的细节。
首先考虑某一趟的插入排序。为什么先考虑某一趟呢？因为当需要解决的问题比较复杂时先将问题简单化会有利于问题的解决。
某一趟的插入排序：

整个插入排序：我们回味一下过年打牌的情景，是不是只有从第二张牌开始我们才开始将摸到牌插到手中？所以end是从1开始到n-1结束。
完整代码：

void InsertSort(int* arr, int n)
{
	for (int i = 1; i < n ; i++)
	{
		int end = i;
		int x = arr[end];
		while (end > 0)
		{
			if (arr[end-1] > x)
			{
				//后移
				arr[end] = arr[end - 1];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end] = x;
	}
}

1.2插入排序的特点

特点：

1.元素集合越接近有序，直接插入排序算法的时间效率越高
2.时间复杂度:O(n^2)(情况最差时,即逆序转有序,最好的情况下为O(n));
3.空间复杂度:O(1);
4.稳定

2.希尔排序

2.1希尔排序的思想

希尔排序是1959 年由D.L.Shell 提出来的，希尔排序是继插入排序的一次大幅度的优化。希尔排序又叫缩小增量排序。
基本思想：
先将整个数组分成若干个子数组,通过对子数组进行排序,达到数组"基本有序",再对整个数组进行插入排序,即可达到有序。
实现方法：
1,先分组,间隔为Gap的数据为一组,然后对这组数据进行排序,再分组,再排,直到数组被分完。

2,然后再把Gap减小,继续分组,排序。

3,此时数组基本有序,然后将最后Gap减小为1,即进行直接插入排序,得到有序数组。
图示：

有了大致思想后就可以开始写代码了。还是用化繁琐为简单的思想来写代码。
先考虑gap=某一个值时，代码的实现。
当gap=某一个值时，第一组数据的插入排序。（下图）

当gap=某一个值时，多组数据的插入排序。（下图）

完整代码：

//希尔排序
void ShellSort(int* arr, int n)
{
	//多次预排序（gap>1）+直接插入（gap=1）
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		//对多组数进行插入排序
		for (int j = gap; j < gap*2; j++)
		{
			//对一组数进行插入排序
			for (int i = j; i < n ; i += gap)
			{
				int end = i;
				int x = arr[end];
				while (end >0)
				{
					if (arr[end-gap] > x)
					{
						arr[end] = arr[end-gap];
						end = end - gap;
					}
					else
					{
						break;
					}
				}
				arr[end] = x;
			}
		}
	}
}

2.1希尔排序的特点

特点：

1.希尔排序是对直接插入排序的优化。
2.当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。
3.希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，这里不深究。
4.时间复杂度O(N^1.5)、空间复杂度O(1)。
5.稳定性：不稳定。
希尔排序不稳定说明（图示）：

3.选择排序

3.1选择排序

选择排序是我感觉最简单的排序，理解起来很简单，写起来也很容易。
基本思想：

第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始(末尾)位置，
然后选出次小(或次大)的一个元素，存放在最大(最小)元素的下一个位置，
重复这样的步骤直到全部待排序的数据元素排完。

完整代码：

void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
//选择排序
void SelectSort(int* arr, int sz)
{
	for (int i = 0; i < sz-1; i++)
	{
		int index = i;
		for (int j = i + 1; j < sz; j++)
		{
			if (arr[j] < arr[index])
			{
				index = j ;
			}
		}
		if (index != i)
		{
			Swap(&arr[i], &arr[index]);
		}
	}
}

选择排序的小优化：
基本思想：上面的思路是每一趟确定一个数，那能不能一趟确定两个数呢？

老规矩先考虑某一趟的代码编写：

上面的代码对于大部分情况是可以完成排序的。但是对于一些情况是有问题的。
例如：

为了出现这种情况，所以必须加个判断语句。

完整代码：

//选择排序
void SelectSort(int* arr, int n)
{
	int beg = 0, end = n - 1;
	while (beg < end)
	{
		//找出最大、最小的下标
		int maxi = beg;
		int mini = beg;
		for (int i = beg; i <= end; i++)
		{
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
		}
		Swap(&arr[beg], &arr[mini]);
		if (maxi == beg)
		{
			maxi = mini;
		}
		Swap(&arr[end], &arr[maxi]);
		beg++;
		end--;
	}
}

3.2选择排序的特点

选择排序的特点：

1.选择排序思考非常好理解，但是效率不是很好(不论数组是否有序都会执行原步骤)。实际中很少使用
2.时间复杂度：O(N^2)（最好和最坏的情况下时间复杂度都是一样）
3.空间复杂度：O(1)
4.稳定性：不稳定

4.冒泡排序

4.1冒泡排序的思想

基本思想：
一趟过程中，前后两个数依次比较，将较大的数字往后推，下一次只需要比较剩下的n-1个数，如此往复。

动态图展示：

怎么编写冒泡排序的代码呢？咱们还是先把问题简单化，先考虑一趟冒泡排序的代码编写。
第一趟冒泡排序的编写：

怎么进行多趟的冒泡排序呢？
只需要控制i的最终大小即可。
当一趟循环下来i=n-2时，可以保证arr[n-1]的值是最大的；
当一趟循环下来i=n-3时，可以保证arr[n-2]的值是次大的；
当一趟循环下来i=n-4时，可以保证arr[n-3]的值是次次大的；
…
所以只需要在嵌套一层循环即可。

完整代码：

//冒泡排序
void BubbleSort(int* arr, int n)
{
	for (int j = 0; j < n-1 ; j++)
	{
		for (int i = 0; i < n -1- j; i++)
		{
			if (arr[i] > arr[i+1])
			{
				Swap(&arr[i], &arr[i+1]);
			}
		}
	}
}

小伙伴到这是不是以为冒泡排序结束了？嘿嘿，其实还没有。不知道大家考虑过这样的情况过吗？
如下图：

答案是还要进行。这就是上面的冒泡排序缺点。
冒泡排序的小优化：
基本思想：
为了让冒泡排序知道数组数组是否有序，可以定义一个变量flag。当flag=1时，默认数组是无序的。当flag=0时，认为数组是有序的。

优化后的完整代码：

//冒泡排序
void BubbleSort(int* arr, int n)
{
	int flag = 1;
	for (int j = 0; j < n&&flag==1; j++)
	{
		flag = 0;
		for (int i = 1; i < n-j; i++)
		{
			if (arr[i-1] > arr[i])
			{
				Swap(&arr[i - 1], &arr[i]);
				flag = 1;
			}
		}
	}
}

4.2冒泡排序的特点

特点：

非常容易理解的排序
时间复杂度:O(N^2)
空间复杂度:O(1)
稳定性：稳定

5.快速排序

5.1快速排序的思想

5.1快速排序（递归）

基本思想：
乍一看这个排序写起来毫无思路，所以我们一步一步看问题，一步一步解决问题。
先考虑第一个问题：将数组中第一个数放在正确的位置。

5.1.1快速排序（递归-Hoare）

第一个问题的基本思想：

第一个问题的基本步骤：
1、选出一个keyi，一般是最左边或是最右边的。
2、定义一个L和一个R，L从左向右走，R从右向左走。（需要注意的是：若选择最左边的数据作为key，则需要R先走；若选择最右边的数据作为keyi，则需要L先走）。
3、在走的过程中，若R遇到小于arr[keyi]的数，则停下，L开始走，直到L遇到一个大于arr[keyi]的数时，将L和R的内容交换，R再次开始走，如此进行下去，直到L和R最终相遇，此时将相遇点的内容与arr[keyi]交换即可。（选取最左边的值作为keyi）
经过一次单趟排序，最终使得key左边的数据全部都小于arr[keyi]，key右边的数据全部都大于arr[keyi]。
为什么要注意谁先走呢？以左值为keyi举例说明：

第一个问题的动态图演示（Hoare）：

代码(Hoare)：

//一趟快速排序
int Partion(int* arr, int left, int right)
{
	assert(arr);
	int keyi = left;

	while (left < right)
	{
		//左边是key值，让右边先走
		//右边找小
		while (left < right && arr[right] >= arr[keyi])
		{
			right--;
		}

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

		Swap(&arr[left], &arr[right]);
	}
	Swap(&arr[left], &arr[keyi]);
	return left;
}

5.1.2快速排序（递归-挖坑法）

第一个问题的动态图演示（挖坑法）：

代码(挖坑法)：

//一趟快速排序(挖坑法)
int Partion2(int* arr, int left, int right)
{
	int key = arr[left];
	int pivot = left;
	while (left < right)
	{
		//右边先走，找小
		while (left < right && arr[right] >= key)
		{
			right--;
		}
		arr[pivot] = arr[right];
		pivot = right;

		//左边再走，找大
		while (left < right && arr[left] <= key)
		{
			left++;
		}
		arr[pivot] = arr[left];
		pivot = left;
	}
	arr[pivot] = key;
	return pivot;
}

5.1.3快速排序（递归-前后指针）

第一个问题的动态图演示（前后指针）：

代码（前后指针）：

//一趟快速排序(前后指针)
int Partion3(int* arr, int left, int right)
{
	assert(arr);

	int pre = left;
	int cur = pre + 1;
	int keyi = left;
	while (cur <= right)
	{
		if (arr[cur] < arr[keyi])
		{
			Swap(&arr[cur], &arr[++pre]);
		}
		cur++;
	}
	Swap(&arr[pre], &arr[keyi]);
	return pre;

}

第二个问题与第三个问题：

快速排序递归版代码（Hoare）：

//一趟快速排序
int Partion(int* arr, int left, int right)
{
	assert(arr);
	int keyi = left;

	while (left < right)
	{
		//左边是key值，让右边先走
		//右边找小
		while (left < right && arr[right] >= arr[keyi])
		{
			right--;
		}

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

		Swap(&arr[left], &arr[right]);
	}
	Swap(&arr[left], &arr[keyi]);
	return left;
}


//快速排序
void QuickSort(int* arr, int left, int right)
{
	assert(arr);

	if (left >= right)
	{
		return;
	}

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

	QuickSort(arr, left, keyi - 1);
	QuickSort(arr, keyi+1, right);

}

当待排序的数组内的值都是同一个值且数量很多时递归版快速排序容易出现栈溢出的情况，为了优化这一现象就有了非递归版快速排序。
快速排序的非递归算法基本思路：
1、先将待排序列的第一个元素的下标和最后一个元素的下标入栈。
2、当栈不为空时，读取栈中的信息（一次读取两个：一个是L，另一个是R），然后调用某一版本的单趟排序，排完后获得了key的下标，然后判断key的左序列和右序列是否还需要排序，若还需要排序，就将相应序列的L和R入栈；若不需排序了（序列只有一个元素或是不存在），就不需要将该序列的信息入栈。
3、反复执行步骤2，直到栈为空为止。
图示：

5.2快速排序（非递归）

快速排序非递归代码：

/快速排序（非递归）
void QuickSortNonR(int* arr, int left, int right)
{
	assert(arr);

	Stack ST;
	Init_Stack(&ST);
	Push_Stack(&ST, left);
	Push_Stack(&ST, right);
	while (!IsEmpty(&ST))
	{
		int end = Top_Stack(&ST);
		Pop_Stack(&ST);

		int begin = Top_Stack(&ST);
		Pop_Stack(&ST);

		//[begin,keyi-1] keyi [keyi+1,end]
		int keyi=Partion1(arr, begin, end);

		if (keyi + 1 < end)
		{
			Push_Stack(&ST, keyi + 1);
			Push_Stack(&ST, end);
		}

		if (begin < keyi - 1)
		{
			Push_Stack(&ST, begin);
			Push_Stack(&ST, keyi - 1);
		}
	}
	Destroy_Stack(&ST);
}

5.3快速排序的特点

1.快速排序很怪，为什么呢？这个排序排乱序的数组贼快，但是排有序数组慢的离谱。
比如：

为了避免最坏情况的发生，做了个三数取中的小优化
优化代码：

//三数取中
int GetMidIndex(int* arr, int left, int right)
{
	//int mid = (left + right) / 2;
	int mid = left + (right - left) / 2;
	if (arr[left] < arr[mid])
	{
		if (arr[mid] < arr[right])
		{
			return mid;
		}
		//arr[left]<arr[mid]   arr[mid]>arr[right]
		else if (arr[right] < arr[left])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	//arr[left] > arr[mid]
	else
	{
		if (arr[mid] > arr[right])
		{
			return mid;
		}
		///arr[left] > arr[mid]  arr[mid] < arr[right]
		else if (arr[left]>arr[right])
		{
			return right;
		}
		else
		{
			return left;
		}
	}
	return 1;
}
//一趟快速排序(Hoare)
int Partion1(int* arr, int left, int right)
{
	assert(arr);
	int keyi = left;

	while (left < right)
	{
		//左边是key值，让右边先走
		//右边找小
		while (left < right && arr[right] >= arr[keyi])
		{
			right--;
		}

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

		Swap(&arr[left], &arr[right]);
	}
	Swap(&arr[left], &arr[keyi]);
	return left;
}
//快速排序
void QuickSort(int* arr, int left, int right)
{
	assert(arr);
	int midi = GetMidIndex(arr, left, right);
	Swap(&arr[midi], &arr[left]);

	if (left >= right)
	{
		return;
	}

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

	QuickSort(arr, left, keyi - 1);
	QuickSort(arr, keyi+1, right);
}

通过这样的优化如果快速排序遇到最坏情况，那么最坏情况直接变成最好情况。

快排的时间复杂度： O(N*logN)
空间复杂度： O(logN)
稳定性：不稳定
快速排序不稳定说明（图示）：

6.堆排序

6.1堆排序的思想

基本思想：

上面排序的思想已经大致清楚了，那么怎么建堆呢？怎么把一个数组建成堆呢？
思路1：将数组中从第二个元素开始利用向上调整函数建堆。

向上调整代码：

//向上调整
void AjustUp(HeapDateType* arr, int child)
{
	assert(arr);
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		//大于号是大堆，小于号是小堆
		if (arr[child] > arr[parent])
		{
			Swap(&arr[parent], &arr[child]);

			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//构建大堆
//方法1
for (int i = 1; i < n; i++)
{
	AjustUp(a, i);
}

思路2：将数组中从倒数第一个非叶子节点开始利用向下调整函数建堆。

向下调整代码：

//向下调整
void AjustDown(HeapDateType* arr, int len, int parent)
{
	assert(arr);
	int child = parent * 2 + 1;

	while (child < len)
	{
		//大于号是大堆，小于号是小堆
		if (child + 1 < len && arr[child + 1] > arr[child])
		{
			child++;
		}

		//大于号是大堆，小于号是小堆
		if (arr[child] > arr[parent])
		{
			Swap(&arr[parent], &arr[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
//方法2
//n-1是最后一个叶子节点  (n-1-1)/2是最后一个叶子节点的父亲节点
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
	AjustDown(a, n, i);
}

堆排序代码：

void HeapSort(int* a, int n)
{
	assert(a);
	//构建大堆
	//方法1
	//for (int i = 1; i < n; i++)
	//{
	//	AjustUp(a, i);
	//}	//方法2
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AjustDown(a, n, i);
	}
	for (int end = n - 1; end > 0; end--)
	{
		Swap(&a[end], &a[0]);
		AjustDown(a, end, 0);
	}
}

6.2堆排序的特点

时间复杂度：O（N*logN）
空间复杂度：O(1)
稳定性：不稳定

7.归并排序

7.1归并排序（递归）

归并排序（递归）的思想
归并排序是采用分治法的一个非常典型的应用。其基本思想是：将已有序的子序合并，从而得到完全有序的序列，即先使每个子序有序，再使子序列段间有序。

将两个有序的数组归并成一个有序数组动态图：

递归版归并排序：
上面的图示其实已经可以看出有了写递归的影子了。想要对一个数组进行排序，就需要两个有序的子数组来归并，而这两个子数组想要有序也需要其自身的两个有序子数组来归并,就这样套娃模式就开始了，对付套娃还得是递归才行。
递归版归并排序写代码前分析：

递归版归并排序代码：

void _MergeSort(int* arr, int left, int right, int* temp)
{

	if (left >= right)
	{
		return;
	}
	int mid = (left + right) / 2;

	//递归
	_MergeSort(arr, left, mid, temp);
	_MergeSort(arr, mid+1, right, temp);

	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int i = left;

	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
		{
			temp[i++] = arr[begin1++];
		}
		else
		{
			temp[i++] = arr[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		temp[i++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		temp[i++] = arr[begin2++];
	}

	for (int i = left; i <= right; i++)
	{
		arr[i] = temp[i];
	}
}

//归并排序
void MergeSort(int* arr, int n)
{
	assert(arr);

	int* temp = (int*)malloc(sizeof(int) * n);
	if (temp == NULL)
	{
		perror("MergeSort::malloc");
		return;
	}
	_MergeSort(arr, 0, n - 1, temp);

	free(temp);
	temp = NULL;
}

7.2归并排序（非递归）

在上面我们知道快速排序有递归版与非递归版，那么归并排序有非递归吗？因为递归的缺点还是很明显的，在有非递归下最好还是使用非递归。其实是有非递归的归并排序的。但是这个写法需要注意的东西很多，直接上代码很容易看懵，所以且让我慢慢道来。
归并排序（非递归）的基本思想（图示）：

理想情况下的代码：

//归并排序（非递归）
void MergeSortNonR(int* arr, int n)
{
	assert(arr);
	int gap = 1;
	int* temp = (int*)malloc(sizeof(int) * n);
	while (gap < n)
	{
		for (int i = 0; i <= n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;

			int j = begin1;
			

			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] < arr[begin2])
				{
					temp[j++] = arr[begin1++];
				}
				else
				{
					temp[j++] = arr[begin2++];
				}
			}
			while (begin1<=end1)
			{
				temp[j++] = arr[begin1++];
			}
			while (begin2<=end2)
			{
				temp[j++] = arr[begin2++];
			}
		}
		
		for (int j = 0; j <n; j++)
		{
			arr[j] = temp[j];
		}
		gap *= 2;
	}
	free(temp);
	   
}

那怎在非理想进行非递归归并排序呢？首先就要考虑非理想情况下与理想情况下的差别有哪些。
我们仔细观察会发现理想情况下的begin1、end1、begin2、end2是不会出现越界的，而非理想情况下end1、begin2、end2是会出现越界的。

所以只需要对这三种情况分别处理下就好了
第一种修正方式图示：

非递归归并排序代码（第一种）：

/归并排序（非递归）
void MergeSortNonR(int* arr, int n)
{
	assert(arr);
	int gap = 1;
	int* temp = (int*)malloc(sizeof(int) * n);
	while (gap < n)
	{
		for (int i = 0; i <= n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;

			int j = begin1;
			//printf("[%d,%d] [%d,%d] ", begin1, end1, begin2, end2);
			
			//end1、begin2、end2越界
			if (end1 >= n)
			{
				end1 = n - 1;
			}
			//begin2、end2越界不进行归并
			if (begin2 >= n)
			{
				begin2 = n;
				end2 = n - 1;
			}
			if (end2 >= n)
			{
				end2 = n - 1;
			}

			//printf("[%d,%d] [%d,%d] ", begin1, end1, begin2, end2);

			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] < arr[begin2])
				{
					temp[j++] = arr[begin1++];
				}
				else
				{
					temp[j++] = arr[begin2++];
				}
			}
			while (begin1<=end1)
			{
				temp[j++] = arr[begin1++];
			}
			while (begin2<=end2)
			{
				temp[j++] = arr[begin2++];

			}
		}
		for (int j = 0; j <n; j++)
		{
			arr[j] = temp[j];
		}
		gap *= 2;
		//printf("\n");
	}

	free(temp);
	   
}

第二种修正方式：

非递归归并排序代码（第二种）：

//归并排序（非递归）法2
void MergeSortNonR(int* arr, int n)
{
	assert(arr);
	int gap = 1;
	int* temp = (int*)malloc(sizeof(int) * n);
	while (gap < n)
	{
		for (int i = 0; i <= n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;

			int j = begin1;

			//end1或者begin2越界
			if (end1 >= n||begin2>=n)
			{
				break;
			}
			//end2越界
			if (end2 >= n)
			{
				end2 = n - 1;
			}

			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] < arr[begin2])
				{
					temp[j++] = arr[begin1++];
				}
				else
				{
					temp[j++] = arr[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				temp[j++] = arr[begin1++];
			}
			while (begin2 <= end2)
			{
				temp[j++] = arr[begin2++];

			}
			for (int j = i; j <=end2; j++)
			{
				arr[j] = temp[j];
			}
		}
	
		gap *= 2;
	}

	free(temp);

}

7.2归并排序的特点

1.时间复杂度：O(N*logN)
2.空间复杂度：O(N)
3.稳定性：不稳定

8.计数排序

8.1计数排序的思想

图示：

//计数排序
void CountSort(int* arr,int n)
{
	assert(arr);

	int max = arr[0], min = arr[0];
	//找出最大、最小数
	for (int i = 0; i < n; i++)
	{
		arr[i] = arr[i];
		if (arr[i] < min)
		{
			min = arr[i];
		}
		if (arr[i] > max)
		{
			max = arr[i];
		}
	}
	int rang = max - min + 1;
	int* temp = (int*)malloc(sizeof(int) * rang);
	//初始化temp数组
	memset(temp, 0, sizeof(int) * rang);

	//开始在temp数组里计数
	for (int i = 0; i < n; i++)
	{
		temp[arr[i] - min]++;
	}

	//排序arr
	int j = 0;
	for (int i = 0; i < rang; i++)
	{
		while (temp[i])
		{
			arr[j++] = i + min;
			temp[i]--;
		}
	}
	free(temp);
}

8.2计数排序的特点

1.计数排序只适用于数据范围较集中的序列的排序，若待排序列的数据较分散，则会造成空间浪费，并且计数排序只适用于整型排序，不适用与浮点型排序。
2.时间复杂度：O(N+range)
3.空间复杂度：O(range)
4.稳定性：不稳定

数据结构数据 span class token 排序算法算法

有关数据结构--八大排序的更多相关文章

ruby - 使用 ruby 将 HTML 转换为纯文本并维护结构/格式 - 2
我想将html转换为纯文本。不过，我不想只删除标签，我想智能地保留尽可能多的格式。为插入换行符标签，检测段落并格式化它们等。输入非常简单，通常是格式良好的html(不是整个文档，只是一堆内容，通常没有anchor或图像)。我可以将几个正则表达式放在一起，让我达到80%，但我认为可能有一些现有的解决方案更智能。最佳答案首先，不要尝试为此使用正则表达式。很有可能你会想出一个脆弱/脆弱的解决方案，它会随着HTML的变化而崩溃，或者很难管理和维护。您可以使用Nokogiri快速解析HTML并提取文本:require'nokogiri'h
ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2
我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i
ruby - Ruby 有 `Pair` 数据类型吗？ - 2
有时我需要处理键/值数据。我不喜欢使用数组，因为它们在大小上没有限制(很容易不小心添加超过2个项目，而且您最终需要稍后验证大小)。此外，0和1的索引变成了魔数(MagicNumber)，并且在传达含义方面做得很差(“当我说0时，我的意思是head...”)。散列也不合适，因为可能会不小心添加额外的条目。我写了下面的类来解决这个问题:classPairattr_accessor:head,:taildefinitialize(h,t)@head,@tail=h,tendend它工作得很好并且解决了问题，但我很想知道:Ruby标准库是否已经带有这样一个类？最佳
ruby - 是否有用于序列化和反序列化各种格式的对象层次结构的模式？ - 2
给定一个复杂的对象层次结构，幸运的是它不包含循环引用，我如何实现支持各种格式的序列化？我不是来讨论实际实现的。相反，我正在寻找可能会派上用场的设计模式提示。更准确地说:我正在使用Ruby，我想解析XML和JSON数据以构建复杂的对象层次结构。此外，应该可以将该层次结构序列化为JSON、XML和可能的HTML。我可以为此使用Builder模式吗？在任何提到的情况下，我都有某种结构化数据-无论是在内存中还是文本中-我想用它来构建其他东西。我认为将序列化逻辑与实际业务逻辑分开会很好，这样我以后就可以轻松支持多种XML格式。最佳答案我最
ruby - 我如何添加二进制数据来遏制 POST - 2
我正在尝试使用Curbgem执行以下POST以解析云curl-XPOST\-H"X-Parse-Application-Id:PARSE_APP_ID"\-H"X-Parse-REST-API-Key:PARSE_API_KEY"\-H"Content-Type:image/jpeg"\--data-binary'@myPicture.jpg'\https://api.parse.com/1/files/pic.jpg用这个:curl=Curl::Easy.new("https://api.parse.com/1/files/lion.jpg")curl.multipart_form_
世界前沿3D开发引擎HOOPS全面讲解——集3D数据读取、3D图形渲染、3D数据发布于一体的全新3D应用开发工具 - 2
无论您是想搭建桌面端、WEB端或者移动端APP应用，HOOPSPlatform组件都可以为您提供弹性的3D集成架构，同时，由工业领域3D技术专家组成的HOOPS技术团队也能为您提供技术支持服务。如果您的客户期望有一种在多个平台（桌面/WEB/APP，而且某些客户端是“瘦”客户端）快速、方便地将数据接入到3D应用系统的解决方案，并且当访问数据时，在各个平台上的性能和用户体验保持一致，HOOPSPlatform将帮助您完成。利用HOOPSPlatform，您可以开发在任何环境下的3D基础应用架构。HOOPSPlatform可以帮您打造3D创新型产品，HOOPSSDK包含的技术有：快速且准确的CAD
FOHEART H1数据手套驱动Optitrack光学动捕双手运动(Unity3D) - 2
本教程将在Unity3D中混合Optitrack与数据手套的数据流，在人体运动的基础上，添加双手手指部分的运动。双手手背的角度仍由Optitrack提供，数据手套提供双手手指的角度。 01 客户端软件分别安装MotiveBody与MotionVenus并校准人体与数据手套。MotiveBodyMotionVenus数据手套使用、校准流程参照：https://gitee.com/foheart_1/foheart-h1-data-summary.git02 数据转发打开MotiveBody软件的Streaming，开始向Unity3D广播数据；MotionVenus中设置->选项选择Unit
使用canal同步MySQL数据到ES - 2
文章目录一、概述简介原理模块二、配置Mysql使用版本环境要求1.操作系统2.mysql要求三、配置canal-server离线下载在线下载上传解压修改配置单机配置集群配置分库分表配置1.修改全局配置2.实例配置垂直分库水平分库3.修改group-instance.xml4.启动监听四、配置canal-adapter1修改启动配置2配置映射文件3启动ES数据同步查询所有订阅同步数据同步开关启动4.验证五、配置canal-admin一、概述简介canal是Alibaba旗下的一款开源项目，Java开发。基于数据库增量日志解析，提供增量数据订阅&消费。Git地址：https://github.co
ruby-on-rails - 创建 ruby 数据库时惰性符号绑定(bind)失败 - 2
我正在尝试在Rails上安装ruby，到目前为止一切都已安装，但是当我尝试使用rakedb:create创建数据库时，我收到一个奇怪的错误:dyld:lazysymbolbindingfailed:Symbolnotfound:_mysql_get_client_infoReferencedfrom:/Library/Ruby/Gems/1.8/gems/mysql2-0.3.11/lib/mysql2/mysql2.bundleExpectedin:flatnamespacedyld:Symbolnotfound:_mysql_get_client_infoReferencedf
STM32读取串口传感器数据（颗粒物传感器，主动上传） - 2
文章目录1.开发板选择*用到的资源2.串口通信（个人理解）3.代码分析（注释比较详细）1.主函数2.串口1配置3.串口2配置以及中断函数4.注意问题5.源码链接1.开发板选择我用的是STM32F103RCT6的板子，不过代码大概在F103系列的板子上都可以运行，我试过在野火103的霸道板上也可以，主要看一下串口对应的引脚一不一样就行了，不一样的就更改一下。*用到的资源keil5软件这里用到了两个串口资源，采集数据一个，串口通信一个，板子对应引脚如下：串口1，TX：PA9，RX：PA10串口2，TX：PA2，RX：PA32.串口通信（个人理解）我就从串口采集传感器数据这个过程说一下我自己的理解，