公司建网站制作平台,珠海网站建设网络公司怎么样,太原最新建设,网上银行入口一、冒泡排序
1、定义
冒泡排序#xff08;英语#xff1a;Bubble Sort#xff09;是一种简单的排序算法。它重复地走访过要排序的数列#xff0c;一次比较两个元素#xff0c;如果他们的顺序#xff08;如从大到小、首字母从A到Z#xff09;错误就把他们交换过来。
…一、冒泡排序
1、定义
冒泡排序英语Bubble Sort是一种简单的排序算法。它重复地走访过要排序的数列一次比较两个元素如果他们的顺序如从大到小、首字母从A到Z错误就把他们交换过来。
冒泡排序是所有排序算法中最简单、最易实现的算法有时也称为起泡排序算法。 使用冒泡排序算法对 n 个数据进行排序实现思路是从待排序序列中找出一个最大值或最小值这样的操作执行 n-1 次最终就可以得到一个有序序列。
2、过程分析
举个例子对 {14, 33, 27, 35, 10} 序列进行升序排序由小到大排序冒泡排序算法的实现过程是
从 {14, 33, 27, 35, 10} 中找到最大值 35从 {14,33,27,10} 中找到最大值 33从 {14, 27, 10} 中找到最大值 27从 {14, 10} 中找到最大值 14。
由此我们就得到了一个有序序列 {10, 14, 27, 33, 35}。 那么如何从待排序序列中找到最大或最小的值呢以找最大值为例遍历待排序序列过程中不断地比较相邻两个元素的值如果后者比前者的值小就交换它们的位置。遍历完成后最后一个元素就是当前待排序序列中最大的。 例如从 {14, 33, 27, 35, 10} 中找到最大值 35 的过程如下 1) 比较 14 和 33 的大小显然后者更大不需要交换它们的位置序列不发生改变。 2) 比较 33 和 27 的大小前者大于后者交换它们的位置新的序列如下图所示。 3) 比较 33 和 35 的大小后者更大不需要交换它们的位置序列不发生改变。 4) 比较 35 和 10 的大小前者大于后者交换它们的位置新的序列如下图所示。 可以看到序列中值最大的元素 35 被移动到了序列的末尾。整个查找最大值的过程中最大的元素就像水里的气泡一样一点一点地“冒”了出来这也是将该算法命名为冒泡排序算法的原因。
采用同样的方法我们可以很轻松地从 {14, 27, 33, 10} 中找到最大值 33。找到 33 后的新序列为 从 {14, 27, 10} 中找到最大值 27 后新的序列如下图所示 从 {14, 10} 中找到最大值 14 后新的序列如下图所示 所有比 10 大的数都被一一找到所以 10 必然是最小的数这也是为什么“对 n 个数据进行排序找最大值的过程只重复 n-1 次”的原因。 3、代码实现
如下是用冒泡排序算法对 { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70} 完成升序排序的C语言程序
#include stdio.h
//函数声明
void Bubble_sort(int arr[], int len);int main(void)
{int arr[] { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };//定义一个数组int len sizeof(arr)/ sizeof(arr[0]);//计算数组长度 数组总字节数/每个元素的字节数Bubble_sort(arr, len);for (int i 0; i len; i){printf(%d , arr[i]);}return 0;
}void Bubble_sort(int arr[], int len)
{for (int i 0; i len - 1; i)//循环次数n - 1{for (int j 0; j len - i - 1; j){//每次循环的两两比较元素if (arr[j] arr[j 1])//如果前一个数大于后一个就把大的给往后放{int temp arr[j];arr[j] arr[j 1];arr[j 1] temp;}}}
}
如下是用冒泡排序算法对 {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70} 完成升序排序的 Python 程序
#待排序序列
list [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70]
def Bubble_sort():#序列中有 n 个元素就遍历 n-1 遍for i in range(len(list-1)):#从第 1 个元素开始遍历比那里至 len(list)-1-ifor j in range(len(list)-1-i):#比较两个相邻元素的大小if list[j] list[j1]:#交换 2 个元素的位置list[j],list[j1] list[j1],list[j]
Bubble_sort()
for i in list:print(i,end )
二、双向冒泡排序
1、通过冒泡排序进阶
先回忆一下普通的冒泡排序算法比如对 {14, 33, 27, 35, 10} 进行升序排序过程如下图所示 图 1 普通的冒泡排序 从待排序序列的第一个元素开始比较相邻元素的大小找到最大或最小的元素并移动到序列的末尾。重复整个过程最终就可以得到一个有序的序列。 双向冒泡排序算法对图 1 的排序过程进行了优化接下来仍以 {14, 33, 27, 35, 10} 进行升序排序为例带大家了解双向冒泡排序。 1) 最初的待排序序列是 {14, 33, 27, 35, 10}和普通的冒泡排序一样从第一个元素 14 向后查找通过相邻元素的比较找到最大的元素并移动到序列的末尾过程如下图所示 图 2 第一轮从前向后冒泡 在图 2 的基础上待排序序列变成了 {14, 27, 33, 10}。接下来从末尾元素 10 开始向前查找通过相邻元素的比较找到最小的元素并移动到序列的开头。 图 3 第一轮从后往前冒泡 经过了第 1 步从元素 14 向后查找找到了最大值 35再从元素 10 向前查找找到了最小值 10。最终待排序序列变成了 {14, 27, 33}。 2) 采用和第 1 步相同的方法从 {14, 27, 33} 中的第一个元素 14 开始向后查找通过相邻元素的对比最终可以找到最大值 33 并移动到序列的末尾待排序序列变成了 {14, 27}。 图 4 第二轮从前往后冒泡 继续从 {14, 27} 中最后一个元素 27 开始向前查找可以找到最小值 14 并移动到序列的开头待排序序列变成了 {27}。 图 5 第二轮从后往前冒泡
3) 由于待排序序列 {27} 只有 1 个元素不再需要冒泡排序此时整个序列 {10, 14, 27, 33, 35} 就是一个升序序列。
2、代码实现
下面是使用双向冒泡排序对 { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 } 完成升序排序的C语言程序
#include stdio.h// 函数声明
void bubble_sort(int arr[], int len);int main() {int arr[] { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };int len sizeof(arr) / sizeof(arr[0]); // 计算数组长度//insertion_sort(arr, len); // 调用插入排序函数bubble_sort(arr, len); // 调用插入排序函数// 打印排序后的数组for (int i 0; i len; i) {printf(%d , arr[i]);}return 0;
}void bubble_sort(int arr[], int len)
{int i, temp;int low 0, high len -1;while (low high){for (i low; i high;i){if (arr[i] arr[i 1]){temp arr[i];arr[i] arr[i 1];arr[i 1] temp;}}high--;for (i high; i low; i--){if (arr[i] arr[i - 1]){temp arr[i];arr[i] arr[i - 1];arr[i - 1] temp;}}low;}}
下面是使用双向冒泡排序对{ 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 } 完成升序排序的 Python 程序
list [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70] # 定义并初始化一个列表list
def Bubble_sort():temp,i 0,0low, high 0,len(list) -1while lowhigh:for i in range (low,high):if list[i] list[i1]:list[i],list[i1] list[i1],list[i]high-1for i in range (high,low,-1):if list[i] list[i-1]:list[i], list[i-1] list[i-1],list[i]low1Bubble_sort()
for i in list:print(i,end )
