如何把学校网站建设好,安卓版下载,铁岭市网站建设,重庆市公路建设信息网官网交换排序就是通过比较交换实现排序。分冒泡排序和快速排序两种。
一、冒泡排序#xff1a;
1、简述
顾名思义就是大的就冒头#xff0c;换位置。
通过多次重复比较、交换相邻记录而实现排序#xff1b;每一趟的效果都是将当前键值最大的记录换到最后。
冒泡排序算法的原…交换排序就是通过比较交换实现排序。分冒泡排序和快速排序两种。
一、冒泡排序
1、简述
顾名思义就是大的就冒头换位置。
通过多次重复比较、交换相邻记录而实现排序每一趟的效果都是将当前键值最大的记录换到最后。
冒泡排序算法的原理如下
比较相邻的元素。如果第一个比第二个大就交换他们两个。 对每一对相邻元素做同样的工作从开始第一对到结尾的最后一对。在这一点最后的元素应该会是最大的数。 针对所有的元素重复以上的步骤除了最后一个。 持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较
2、复杂度
时间复杂度O(n²)
空间复杂度O(1) 3、稳定性稳定排序 4、例子
#include iostream
using namespace std;
// 冒泡
int main() {int arr[8] {45, 38, 66, 90, 88, 10, 25, 45};int arrCount sizeof(arr) / sizeof(arr[0]);for (int i 0; i arrCount - 1; i) {for (int j 0; j arrCount - i - 1; j) {if (arr[j] arr[j1]) { // 对比两个值int tmp arr[j];// 交换位置arr[j] arr[j1];arr[j1] tmp;}}couti1次排序后;for (int i 0;i arrCount;i) {cout arr[i] ;}coutendl;}cout最后结果;for (int i 0;i arrCount;i) {cout arr[i] ;}return 0;
} 输出结果 1次排序后38 45 66 88 10 25 45 90
2次排序后38 45 66 10 25 45 88 90
3次排序后38 45 10 25 45 66 88 90
4次排序后38 10 25 45 45 66 88 90
5次排序后10 25 38 45 45 66 88 90
6次排序后10 25 38 45 45 66 88 90
7次排序后10 25 38 45 45 66 88 90
最后结果10 25 38 45 45 66 88 90 二、快速排序 关键词基准值递归算法 1、简述
快速排序Quicksort计算机科学词汇适用领域PascalC等语言是对冒泡排序算法的一种改进。
快速排序算法流程如下
首先设定一个基准值通过该基准值将数组分成左右两部分。 将大于或等于基准值的数据集中到数组右边小于基准值的数据集中到数组的左边。此时左边部分中各元素都小于基准值而右边部分中各元素都大于或等于基准值 。然后左边和右边的数据可以独立排序。对于左侧的数组数据又可以取一个基准值将该部分数据分成左右两部分同样在左边放置较小值右边放置较大值。右侧的数组数据也可以做类似处理。 重复上述过程可以看出这是一个递归定义。通过递归将左侧部分排好序后再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后整个数组的排序也就完成了。 2、复杂度
时间复杂度O() 、最差O(n²) 注快速排序在表基本有序时最不利于其发挥效率即蜕化为冒泡排序,其时间复杂度为O(n²)
空间复杂度O() 3、稳定性不稳定排序
在交换的过程中相同的数值可能会被换到前面去所以是不稳定的。
4、例子 在经历第一趟之后我们将基准值左边和右边分别进行同样的操作。
left和right从原先的0和7更新为对应的数值
第一趟排序之后 [25 38 10] 45 [88 90 66 45] 分别对子序列排序
左边子序列排序 [25 38 10] left 0, right 2, flag 25 [10] 25 [38]
再对25左右两侧进行同样的排序方式得出左边子序列排序后的结果 10 25 38
右边子序列排序 [88 90 66 45] left 4, right 7, flag 88 [45 66] 88 [90]
再对88左右两侧进行同样的排序方式最后得到右边子序列排序后的顺序 45 66 88 90 合并起来就是 [10 25 38 45 45 66 88 90] 由于交换规则一致我们可以用递归来处理。
#include iostream
using namespace std;
/// 交换位置
void swapPosition(int arr[], int x, int y) {arr[x] arr[y]arr[x];arr[y] arr[x] - arr[y];arr[x] arr[x] - arr[y];
}void quickSort(int list[], int begin, int end) {// 将基准值flag定为列表第一个。int left begin, right end, flag list[begin];cout这趟排序的起始位置begin,结束位置end基准值flagendl;// 左右指针未碰头则反复做while (left right) {// 从右边开始// 右边没找到小于 flag 的右指针 继续往左移while (list[right] flag leftright) {--right;}// 右边找到比flag小的数据则将其送到左边并且将左边的指针往右移动if(left right) {// 交换位置swapPosition(list, left, right);left;}// 接着开始左边的循环// 左边没找到大于 flag 的左指针 继续往右移while (list[left] flag leftright) {left;}// 左边找到比flag大的数据则将其送到右边并且将右边的指针往左移动if(left right) {// 交换位置swapPosition(list, left, right);--right;}}cout结果;for (int i 0;i 8;i) {cout list[i] ;}coutendl;if (beginleft-1){cout开始左边的递归:endl;quickSort(list, begin, left-1);}if(right1 end){cout开始右边的递归:endl;quickSort(list, right1, end);}
}
int main() {int arr[8] {45, 38, 66, 90, 88, 10, 25, 45};int arrCount sizeof(arr) / sizeof(arr[0]);quickSort(arr, 0, arrCount - 1);cout最后结果;for (int i 0;i arrCount;i) {cout arr[i] ;}return 0;
}输出结果
这趟排序的起始位置0,结束位置7基准值45
结果25 38 10 45 88 90 66 45
开始左边的递归:
这趟排序的起始位置0,结束位置2基准值25
结果10 25 38 45 88 90 66 45
开始右边的递归:
这趟排序的起始位置4,结束位置7基准值88
结果10 25 38 45 45 66 88 90
开始左边的递归:
这趟排序的起始位置4,结束位置5基准值45
结果10 25 38 45 45 66 88 90
最后结果10 25 38 45 45 66 88 90 参考
百度百科——冒泡排序https://baike.baidu.com/item/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F?fromModulelemma_search-box
百度百科——快速排序https://baike.baidu.com/item/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/369842?frge_ala 生命不息学习不止若有不正确的地方欢迎指正。
