招商网站如何做推广,wordpress更改域名 后台,曲靖房地产网站开发,南昌网站seo外包一、冒泡排序
冒泡排序的原理是#xff1a;从左到右#xff0c;相邻元素进行比较。每次比较一轮#xff0c;就会找到序列中最大的一个或最小的一个。这个数就会从序列的最右边冒出来。
以从小到大排序为例#xff0c;第一轮比较后#xff0c;所有数中最大的那个数就会浮…一、冒泡排序
冒泡排序的原理是从左到右相邻元素进行比较。每次比较一轮就会找到序列中最大的一个或最小的一个。这个数就会从序列的最右边冒出来。
以从小到大排序为例第一轮比较后所有数中最大的那个数就会浮到最右边第二轮比较后所有数中第二大的那个数就会浮到倒数第二个位置……就这样一轮一轮地比较最后实现从小到大排序。 代码如下
void BubbleSort(int* a, int n)
{for (size_t j 0; j n; j){int exchange 0;for (size_t i 1; i n-j; i){if (a[i - 1] a[i]){Swap(a[i - 1], a[i]);exchange 1;}}if (exchange 0){break;}}
}
冒泡排序时间复杂度 如果待排序序列的初始状态恰好是我们希望的排序结果(如升序或降序)一趟扫描即可完成排序。 所需的关键字比较次数C和记录移动次数M均达到最小值 冒泡排序最好的时间复杂度为O(n)。 如果待排序序列是反序(如我们希望的结果是升序待排序序列是降序)的需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1)且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下比较和移动次数均达到最大值 冒泡排序的最坏时间复杂度为O(N^2) 综上因此冒泡排序总的平均时间复杂度为O(N^2) 冒泡排序是稳定的排序 二、选择排序
选择排序的工作原理是第一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置然后再从剩余的未排序元素中寻找到最小大元素继续放在起始位置知道未排序元素个数为0。
选择排序的步骤
1首先在未排序序列中找到最小大元素存放到排序序列的起始位置。
2再从剩余未排序元素中继续寻找最小大元素然后放到未排序序列的起始位置。
3重复第二步直到所有元素均排序完毕。 选择排序代码实现
//交换两个数据
void Swap(int* a, int* b)
{int temp *a;*a *b;*b temp;
}//选择排序
void SelectSort(int* arr, int size)
{int i 0;for (i 0; i size-1; i){int min i;int j 0;for (j i1; j size; j){if (arr[j] arr[min]){min j;}}Swap(arr[i], arr[min]);}
}思路优化
以上算法是每次找出最小的放在指定位置一共要找n-1次如果我们每次不但找到最小的还找到最大的将最小的与左端交换最大的与右端交换那么就少了一半的遍历次数从而提高效率。 变量begin和变量end是数组的两端min和max分别找小和大的下标先交换min与begin位置的数值再交换max与end位置的数值begin右移end左移继续找大找小继续交换重复上述操作直到遍历完所有数组 排序优化后问题
若是max的位置与begin重合则begin先与min的位置交换此时max位置的最大值被交换走导致end与max交换的数值是错误的。
问题解决
当max与begin重合时begin与min交换后导致max指向的不再是最大值所以当我们对begin交换后就要对max进行一个修正让max指向最大值然后完成end的交换 1、max与begin重合并且begin此时完成了交换此时最大值已经交换到了min所指向的位置 2、对max进行修正并完成与end的交换 优化后代码:
//交换两个数据
void Swap(int* a, int* b)
{int temp *a;*a *b;*b temp;
}//选择排序
void SelectSort(int* arr, int size)
{int begin 0;int end size - 1;while (begin end){int max begin;int min begin;int i 0;for (i begin1; i end; i){if (arr[i] arr[min]){min i;}if (arr[i] arr[max]){max i;}}Swap(arr[begin], arr[min]);if (begin max) //修正max{max min;}Swap(arr[end], arr[max]);begin;end--;}
}选择排序时间复杂度 时间复杂度O(n^2) 空间复杂度O ( 1 ) 选择排序是不稳定的排序 三、插入排序
直接插入排序是一种简单的插入排序法对数组进行一个遍历每次都对待排的数据按照大小顺序插入到一个有序数组中的特定位置直到所有的数据全部插入完毕就得到一个有序数列。
插入排序的算法非常简单依次对每一个元素进行单趟排序就行了由于要前一个数比较则只需要从1开始遍历n-1次 当插入第i(i1)个元素时前面的array[0],array[1],…,array[i-1]已经排好序此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较找到插入位置即将array[i]插入原来位置上的
元素顺序后移 插入排序代码
void InsertSort(int* arr, int size)
{int i 0;for (i 1; i size; i){int end i;int temp arr[end]; //记录待排数值while (end 0){if (arr[end-1] temp) //若前一个数大于待排数值则后移一位{arr[end] arr[end-1];end--;}else{break;}}// arr[end-1] temp;是之前的错误现已修正arr[end] temp; //将数据放入插入位置}
}插入排序的时间复杂度 1. 元素集合越接近有序直接插入排序算法的时间效率越高 2. 时间复杂度O(N^2) 3. 空间复杂度O(1)它是一种稳定的排序算法 4. 稳定性稳定 四、希尔排序
希尔排序法又称缩小增量法。希尔排序法的基本思想是先选定一个整数把待排序文件中所有记录分成个组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到达1时所有记录在统一组内排好序。 1. 希尔排序是对直接插入排序的优化。
2. 当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些树中给出的 希尔排序代码实现
void ShellSort(int* arr, int size)
{int gap size;while (gap 1){gap gap / 2; //调整希尔增量int i 0;for (i 0; i size - gap; i) //从0遍历到size-gap-1{int end i;int temp arr[end gap];while (end 0){if (arr[end] temp){arr[end gap] arr[end];end - gap;}else{break;}}arr[end gap] temp; //以 endgap 作为插入位置}}
}希尔排序的时间复杂度 希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些书中给出的希尔排序的时间复杂度都不固定 时间复杂度On^1.3 稳定性不稳定
