网站查icp备案查询系统,手机浏览器,有区域名和主机怎么做网站,wordpress 分割线排序的概念
排序#xff1a;所谓排序#xff0c;就是将一份数据#xff0c;通过某个或者某些关键字的大小#xff0c;进行递增或者递减排序的操作。
稳定性#xff1a;假定在待排序的数据组中#xff0c;存在多个相同的元素#xff0c;若经过排序#xff0c;这些数据…排序的概念
排序所谓排序就是将一份数据通过某个或者某些关键字的大小进行递增或者递减排序的操作。
稳定性假定在待排序的数据组中存在多个相同的元素若经过排序这些数据之间的相对位置应保持不变。例如在原数组中a[i]a[j]并且a[i]的位置在a[j]之前如果这个数组被进行了排序操作且a[i]仍然在a[j]之前a[i]和a[j]的位置可能会被改变但是他们之间的位置关系不会改变那么这个排序算法就是稳定的反之就是不稳定。
内部排序数据元素全部在内存中的排序。
外部排序由于数据元素太多不能同时放在内存中根据排序过程的需求不断地在内外存之间移动数据的排序。
常见的算法排序 插入排序算法的实现
基本思想
直接插入排序是一种简单的插入排序法其基本思想是把待排序的元素根据其元素的大小逐个插入到一个已经排好序的有序序列中所有元素插入完为止这样就得到一个新的有序序列。
就是将待排序元素之前的数组当作已经有序的数组再将待排元素与数组内的元素进行比较。
在我们玩扑克牌的时候就在无意中使用了插入排序的思想
直接插入排序
当插入第i(i1)个元素时前面的array[0],array[1],…,array[i-1]已经排好序了这时候用array[i]与array[i-1],array[i-2],…进行比较找到插入位置就将array[i]插入原来位置上的元素顺序后移如图 直接插入排序的总结
元素集合越接近有序直接插入排序算法就越快时间复杂度为 O ( N 2 ) O(N^2) O(N2)空间复杂度为 O ( 1 ) O(1) O(1)它是一种稳定的排序算法
代码
#includestdio.hvoid InsertSort(int* a, int n)
{for (int i 0; i n - 1; i){//[0, end]有序将end1位置的值插入到[0, end]里面去并保持有序int end i;int tmp a[end 1];while (end 0){if (tmp a[end]){a[end 1] a[end];end--;}else{break;}}//这个代码在这里可以同时解决俩个情况// 情况一tmp在遍历的时候发现了比他更小的值// 情况二遍历了一边数组并没有发现比tmp更小的数(end 0)a[end 1] tmp;}
}void PrintArray(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}void TestInsertSort()
{int a[] { 9,8,6,4,2,1,0,5,7,3 };InsertSort(a,sizeof(a)/sizeof(a[0]));PrintArray(a, sizeof(a) / sizeof(a[0]));} 直接插入排序遇到逆序数组就会很慢了这时就有个叫希尔的人对直接插入排序进行了优化这使得排序效率大大提升了。
希尔排序
希尔排序在排序之前会进行预排序让数组接近有序然后再使用直接插入排序。 上图为案例
我将数据分割成多个组间隙为gap个并不是在物理上分成多个数组而是逻辑上将他们分组。
假设gap为3那么在分组中元素9的下一个元素为5再下一个元素为8最后一个元素为5逻辑上这个数组就为[9,5,8,5]。 逻辑上以1开头的数组为[1,7,6]以2开头的数组为[2,4,3] 但是他们实际位置并没有改变我们也没有开辟新空间来存放数据 我们分好组后对每组元素进行插入排序就是分别对[9,5,8,5]、[1,7,6]、2,4,3进行内部的插入排序 经过预排序后原数组[9,1,2,5,7,4,8,6,3,5]变成了[5,1,2,5,6,3,8,7,4,9]。
预排序并没有将整个数组变成有序而是将每个间隙为gap的数组变成了有序我们使用还是直接插入排序只不过元素与元素之间的间隔不是 1而是gap。
虽然预排序没有直接的将整个数组排好序但是他能很快速的将较大的元素往后放把较小的数据往前放案例数组经过预排序后最后的三个数据就是每组最大的元素
单组排序
我们先来红色这一组[9,5,8,5]
void ShellSort(int* a, int n)
{int gap 3;for (int i 0; i n - gap; i gap){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}
}排序后正如我们所想的一样[9,5,8,5]这一组已经有序了。
接下来就是从单组排序拓展到多组排序了
单组排序到多组排序
有两种方法
在外面再套一层循环每组分开排序
void ShellSort(int* a, int n)
{int gap 3;for (int j 0; j gap; j)//j确定起始位置{for (int i 0; i n - gap; i gap){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}}效果
多组并在一起排序 改动也很简答将for (int i 0; i n - gap; i gap)改成for (int i 0; i n - gap; i)
void ShellSort(int* a, int n)
{int gap 3;for (int i 0; i n - gap; i){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}效果
他们的效率是一样只不过第二种方法更美观。
接下来就是改变gap的大小了。
改变gap并完成排序
gap大与小的区别
gap越大大的数可以越快的跳到后面小的数可以越小的跳到前面但是预排序完了也越不接近有序。gap越小跳的越慢但是也越接近有序当gap等于1就相当于直接插入排序了。
当gap等于1那么这个数组就有序了。
那么这个gap该怎么变呢其实到现在都没有一个准确的最优方法。
我们当前最合适的方法是 gap/3但是为了避免gap0我们在后面1也就是gap gap / 3 1;
当gap1时是预排序当gap1时是直接插入排序并不是先通过一个函数完成预排序再通过另一个函数完成直接插入排序。
void ShellSort(int* a, int n)
{int gap n;while (gap 1){gap gap / 3 1;for (int i 0; i n - gap; i){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}}完整代码
void ShellSort(int* a, int n)
{int gap n;while (gap 1){gap gap / 3 1;for (int i 0; i n - gap; i){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}printf(gap%2d:-, gap);PrintArray(a, n);}}
void TestShellSort()
{int a[] { 9,1,2,5,7,4,8,6,3,5 };printf(排序前);PrintArray(a, sizeof(a) / sizeof(a[0]));ShellSort(a, sizeof(a) / sizeof(a[0]));printf(排序后);PrintArray(a, sizeof(a) / sizeof(a[0]));
}int main()
{TestShellSort();return 0;
}结语
最后感谢您能阅读完此片文章如果有任何建议或纠正欢迎在评论区留言也可以前往我的主页看更多好文哦(点击此处跳转到主页)。 如果您认为这篇文章对您有所收获点一个小小的赞就是我创作的巨大动力谢谢
