深圳网络做网站,dedecms 关闭网站,网站备案文件吗,wordpress插件ssh1.插入排序
思路#xff1a;插入排序将一个数插入一个有序的数组里面#xff0c;将这个数和数组元素挨着比较#xff0c;直到他插入到合适的位置。 动画演示#xff1a; 步骤#xff1a;1.定义一个变量tmp保存要插入的数据 2.在循环中用tmp和有序数组中的元素比较#…1.插入排序
思路插入排序将一个数插入一个有序的数组里面将这个数和数组元素挨着比较直到他插入到合适的位置。 动画演示 步骤1.定义一个变量tmp保存要插入的数据 2.在循环中用tmp和有序数组中的元素比较比方说要和a[end]比较如果tmpa[end]的话就将a[end]右移动到a[end1],如果tmpa[end]的话就直接结束循环因为已经找到了自己的位置就是a[end1]. 3.当循环结束则表明已经找到了tmp的位置下标为end1,将tmp赋值给a[end1]即可。 代码实现 void InsertSort(int* a, int n)
{for (int i 0; i n-1; i){int end i;int tmp a[end 1];while (end 0){if (tmp a[end]){a[end 1] a[end];end--;}else{break;}}a[end 1] tmp;}}直接插入排序的特性总结 元素集合越接近有序直接插入排序算法的时间效率越高时间复杂度O(N^2)空间复杂度O(1)它是一种稳定的排序算法稳定性稳定 2.希尔排序
希尔排序( 缩小增量排序 ) 希尔排序法又称缩小增量法。希尔排序法的基本思想是先选定一个整数把待排序文件中所有记录分成个组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到达1时所有记录在统一组内排好序。相当于分组的插入排序。 步骤 1.将要排列的数据分为几组 2.每一组内进行插入排序。 3.缩小组数当组数为1时相当于直接插入排序。 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;}}上面代码为单组的排序只有一组。
void ShellSort(int* a, int n)
{int gap 3;for (int j 0; j gap; j){for (int i j; 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;}}}加了循环将每组都排好序但是整体没有有序。当gap!1时属于预排序。每次循环减小gap的值。说明分组在变然后在每一组里面继续排序当gap等于1时相当于插入排序。
void ShellSort(int* a, int n)
{int gap 3;while (gap 1){gap / 2;for (int j 0; j gap; j){for (int i j; 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;}}}}上面这种是一组排会多套一层循环。如果使用下面的代码是一组没排完就进行排下一组一组中先把前两个元素排好在排第二组的前两个元素当排完每一组的前两个元素又回到第一组排第一组的前三个元素排好前三个元素接着排第二组的前三个元素依次类推。 时间复杂度平均O(N^1.3) 空间复杂度O(1) 3.选择排序
基本思想 每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的 数据元素排完 。 步骤1.定义两个变量maxi,mini分别记录要排序数据的最大值和最小值的下标。初始将·maxi,mini等于起始下标。 2.循环遍历要排序的数据更新下标如果有数据大于a[maxi],maxi更新为当前的i;如果有数据小于a[mini],mini更新为当前的i; 3.交换此时最小值和第一个数据的位置最大值和最后一个数据的位置已经保证了两个数据到他该有的位置。起始位置下标结束位置下标– 4.然后就要排除已经排好的两个元素现在maxi与mini起始下标就为第二个元素下标了。 5.循环条件起始位置下标小于结束位置下标。
动画演示 代码实现
void SelectSort(int* a, int n)
{int begin 0;int end n - 1;while (begin end){int maxi begin;int mini 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]);swap(a[end], a[maxi]);begin;end--;}}如果你要排序的数据里面最大的数据不是第一个的话上面的代码你会觉得是正确的如果第一个数据是最大的排序就不对了到底是为什么呢我们可以调试调试 修改代码为
void SelectSort(int* a, int n)
{int begin 0;int end n - 1;while (begin end){int maxi begin;int mini 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--;}}直接选择排序的特性总结 时间复杂度O(N^2) 空间复杂度O(1) 4.堆排序
堆排序是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆。
void AdjustDwon(int* a, int n, int root)//向下调整建立大堆。
{int child root * 2 1;while (child n){if (child1n a[child] a[child 1]){child child 1;}if (a[child] a[root]){swap(a[child], a[root]);root child;child root * 2 1;}else{break;}}}上图为建立的大堆。 堆排序演示 5.冒泡排序
思路 左边大于右边交换一趟排下来最大的在右边 代码实现
void BubbleSort(int* a, int n)
{for (int i 0; i n-1; i){for (int j 0; j n - i-1; j){if (a[j 1] a[j]){swap(a[j], a[j 1]);}}}}时间复杂度O(N^2) 空间复杂度O(1)
