互联网网站商标,武进网站建设好么,入侵织梦网站,北京app软件开发从本文开始#xff0c;通过若干篇文章展开对于数据结构中——排序的介绍。
1. 排序的概念#xff1a; 将一堆杂乱无章的数据#xff0c;通过一定的规律顺序排列起来。即将一个无序序列排列成一个有序序#xff08;由小到大或者由大到小#xff09;的运算。 在数据的排序中…从本文开始通过若干篇文章展开对于数据结构中——排序的介绍。
1. 排序的概念 将一堆杂乱无章的数据通过一定的规律顺序排列起来。即将一个无序序列排列成一个有序序由小到大或者由大到小的运算。 在数据的排序中需要注意如果需要排序的对象同时有多个数据域例如对学生进行排序往往有学号班级等多个数据域排序往往是针对于其中一个数据域进行的。
2. 排序的种类 对于排序本文及下面的文章中将着重介绍下列给出的排序插入排序、希尔排序、选择排序、冒泡排序、快速排序、归并排序、计数排序。 3. 插入排序
3.1 思路分析 对于插入排序其基本思想可以概括为每一步都将待排序的对象按照该对象与已有数据的大小关系插入到前面已经排好序的一组数据的合适的位置中。因此插入排序可以看作一个一边进行插入一边保持已有序列有序的排序。 为了便于理解插入排序的基本思想下面给出一个例子 对于上面给出的例子按照上面插入排序的基本思想来进行排序则需要首先比较待插入元素与数组中已有元素进行比较。直到插入到一个合适的位置。所以对上述的案例进行排序后最终结果为; 对于上面给出的插入排序的过程需要理解并不是真的对数组不断插入新的元素进行排序。而是将数组中的一部分看作插入的部分例如对于下面的数组 将已经有序的序列即数组中的称为有序序列。将后面的数组成的序列称之为无序序列。如果这个序列进行插入排序只是将元素看作待插入元素。通过不断比对待插入元素与数组中元素的大小关系来调整元素至合适的位置。 为了方便后续编写插入排序的代码将有序序列的最后一位的下标记为将待插入元素的下标记为。所以一开始所对应的下标就是数组第一个元素的下标即待插入元素的下标就是即数组中的第二个元素。对比调整后数组中前两个元素会变为有序序列。接着按照上面的步骤循环即令即有序序列的第二个元素或者说数组中的第一个元素。待插入元素的下标等于即数组中的第二个元素。。。。。。。
3.2 代码演示 通过上面给出的思路可以总结出下面代码
void InsertSort(int* a, int n)
{int end 0;for (end 0; end n - 1; end){int tmp a[end 1];while (end 0){if (a[end] tmp){a[end 1] a[end];}else{break;}end--;}a[end 1] tmp;}}
对于插入排序因为没有开辟额外的空间所以插入排序的空间复杂度为,当数组完全逆序时插入排序需要执行的次数可以看作一个等差数列所以插入排序的时间复杂度为
3.3 插入排序测试
测试函数如下
void TestInsertsort()
{int a[] { 2,1,3,4,6,9,5,8 };int size sizeof(a) / sizeof(int);InsertSort(a, size);ArrayPrint(a, size);
}
其中函数是用于打印数组的函数原理过于简单不予解释运行效果如下 4. 希尔排序
4.1 思路分析及代码演示 对于上面给出的插入排序中提到如果插入排序需要排序的数组是逆序的则插入排序的时间复杂度为如果需要排序的数组为顺序的则时间复杂度为为了优化插入排序在排序逆序数组时较大的时间复杂度可以尝试在对数组进行插入排序之间先对数组进行依次预排序让数组中某些元素是顺序的。对于先进行预处理再进行一次插入排序的排序就是文章本部分要介绍的希尔排序。例如下面的数组 对于预排序其步骤如下首先确定一个间隔数这里将这个间隔数命名为通过利用 将数组分为若干个区间。并且对相邻区间的首元素进行一次类插入排序的操作。具体步骤将通过下面的图形进行演示
1. 假设则利用分组后的数组可以表示为 继续利用上面方法对数组中未分组的元素进行分组可以表示为下面的图片图中不同颜色的图形用于区分不同的组 2. 接着对于一组中的元素进行一次类插入排序的操作即比较同一组的不同区间的首元素的大小关系将小的元素放到前面。例如对于红线组中的元素进行上述操作 对于本部分的操作可以利用插入排序的思想来实现依旧定义表示本组第一个元素的下标例如红线组的则表示本组下一个区间的首元素的坐标再创建一个变量用于存储所对应的元素。例如红线组的。由于所对应的元素所对应的元素。所以让代表的元素覆盖到的位置。再让覆盖到位置。该过程可用代码表示为
void ShellSort(int* a, int n)
{int end 0;int gab 3;int tmp a[end gab];if (a[end] tmp){a[end gab] a[end];}a[end] tmp;
} 但是上面的过程并不完整并且只能交换一次加入遇到下面的情景 假设 所对应的元素为所对应的元素为按照上面的代码交换一次后 可以看到这两个元素的大小关系还是不满足。因此并不能向上面仅仅对 的元素的大小关系进行判断还需要对交换后前面的元素的关系重新进行一次判断如果不满足则再次交换。方法为再进行一次交换后令此时对应的元素为对应的元素为对二者再次进行一次交换。 为了满足多次交换的目的需要利用到循环。所以对于循环的结束条件有两条1是2是元素的大小关系不符合。 即使在加上上面的补充后代码也只能用于单个组中一组元素的交换为了完成整租的交换需要让所对应的下标不断向后个位置。所以可以将上述代码优化为
//希尔排序
void ShellSort(int* a, int n)
{int gab 3;for (int end 0; end n - gab; end gab){int tmp a[end gab];while (end 0){if (a[end] tmp){a[end gab] a[end];end - gab;}else{break;}}a[end gab] tmp;}
}
完善后的代码可以一次性完成一组的预排序。但是在预排序的过程中需要对多组数据进行排序。通过对下面图形的观察可以得知当初始值就为时此时进行预排序的就是紫色线条对应的组也就是需要预排序的最后一组。所以可以在将上面的代码进行一次优化让其能够处理多组预排序
并且对于的值也是变化的的值越大数组中大的元素向后移动的距离越长越小移动的距离也越小当数组为有序。 代码如下
//希尔排序
void ShellSort(int* a, int n)
{int gab n;while (gab 1){gab gab / 2;for (int i 0; i gab; i){for (int end i; end n - gab; end gab){int tmp a[end gab];while (end 0){if (a[end] tmp){a[end gab] a[end];end - gab;}else{break;}}a[end gab] tmp;}}}
}
对于预排序部分的代码还有另一种更简洁的部分这里先给出相应代码再进行逻辑分析
//希尔排序
void ShellSort1(int* a, int n)
{int gab n;while (gab 1){gab gab / 2;for (int i 0; i n - gab; i){int end i;int tmp a[end gab];while (end 0){if (a[end] tmp){a[end gab] a[end];end - gab;}else{break;}}a[end gab] tmp;}}
}
观察上面给出的代码可以发现相对于上面给出的预排序这种预排序省略了一个循环。逻辑也不同。对于现在给出的预排序并不是按照严格分组先进行完一组再进行一组。而是在确定了之后直接按照数组下标的顺序进行预排序例如 对于前面一种的预排序是先对进行预排序再对进行预排序再对进行预排序此时红线所对应的组完成了预排序于是再对绿线所对应的组的元素开始预排序顺序为,。
但是对于现在给出的预排序预排序的顺序为, , , ,。。。。。。
由于希尔排序的时间复杂度的计算极其复杂这里直接给出结论希尔排序的时间复杂度大致在左右。空间复杂度为。 4.2 希尔排序测试
测试函数如下
void TestShellSort()
{int b[] { 9,1,2,5,7,4,8,6,3,5 };int size sizeof(b) / sizeof(int);ShellSort(b, size);printf(希尔排序);ArrayPrint(b, size);
}
结果如下 5. 冒泡排序
5.1 代码演示 对于冒泡排序的相关原理可以在文章C语言——冒泡排序和qsort排序-CSDN博客浏览文章在本部分只给出冒泡排序的相关代码以及测试结果对实现原理不做论述。 void BubbleSort(int* a, int n)
{for (int j 0; j n; j){int exchange 0;for (int i 1; i n; i){if (a[i - 1] a[i]){Swap(a[i - 1], a[i]);exchange 1;}}if (exchange 0){break;}}
}
5.2 冒泡排序测试
测试函数如下
//冒泡排序void BubbleSort(int* a, int n)
{for (int j 0; j n; j){int exchange 0;for (int i 1; i n; i){if (a[i - 1] a[i]){Swap(a[i - 1], a[i]);exchange 1;}}if (exchange 0){break;}}
}
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}
结果如下 6. 堆排序
对于堆排序的相关原理及代码实现在之前的文章如何利用堆来模拟堆排序-CSDN博客已经做了详细的解释这里不再进行多余论述。 7. 选择排序
7.1 思路分析以及代码演示 对于选择排序的原理总结下来只有一句话即每次排序时选出数组中最小的值以及最大的值将最小的值换到数组的最左边最大的值换到数组的最右边。 为了达成上述目的可以创建两个变量通过遍历数组将二者选择出来再通过交换函数让两个值在数组中的位置分别达到最左边最右边。
代码如下 void SelectSort(int* a, int n){int begin 0, end n - 1;while (begin end){int mini begin, maxi begin;for (int i begin 1; i end; i){if (a[i] a[maxi]){maxi i;}if (a[i] a[mini]){mini i;}}Swap(a[begin], a[mini]);if (maxi begin){maxi mini;}Swap(a[end], a[maxi]);begin;end--;}}
7.2 选择排序测试
测试函数如下
TestSelectSort()
{int d[] { 7,8,1,4,5,9,2,3,6};int size sizeof(d) / sizeof(int);SelectSort(d, size);printf(选择排序);ArrayPrint(d, size);
} 结果如下 对于选择排序显而易见时间复杂度为空间复杂度为。
