您的位置:首页 > 游戏 > 游戏 > 冒泡排序

冒泡排序

2024/12/23 16:50:04 来源:https://blog.csdn.net/weixin_62789590/article/details/141636842  浏览:    关键词:冒泡排序

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。

冒泡排序的思想如下:

  1. 比较相邻的元素。如果第一个比第二个大,就交换它们两个;
  2. 对每一对相邻的元素作同样的工作,从开始第一对到结尾的最后一对。经过这一轮后,最后的元素应该会是最大的数;
  3. 针对所有的元素重复以上的步骤,除了最后一个;
  4. 重复步骤1~3,直到排序完成。

冒泡排序的基本思想是通过相邻元素之间的比较和交换来将较大的元素逐步交换到数组的末尾。下面是一个用C语言实现的冒泡排序的示例:

#include <stdio.h>void bubbleSort(int arr[], int size) {for (int i = 0; i < size - 1; i++) {for (int j = 0; j < size - i - 1; j++) {if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}int main() {int arr[] = {64, 34, 25, 12, 22, 11, 90};int size = sizeof(arr) / sizeof(arr[0]);printf("Original array: ");for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}bubbleSort(arr, size);printf("\nSorted array: ");for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}return 0;
}

在上面的代码中,我们首先定义了一个bubbleSort函数,该函数使用冒泡排序算法对给定的数组进行排序。函数中的两个嵌套循环用于比较和交换相邻的元素。在每次外层循环中,内层循环会将当前未排序部分的最大元素移动到该部分的末尾。最终,数组会按升序排列。

main函数中,我们定义了一个用于测试的整型数组arr,并计算了数组的大小。接下来,我们调用bubbleSort函数对数组进行排序,并使用两个for循环分别打印原始数组和排序后的数组。最后,返回0,以表示程序顺利结束。

运行上述代码,输出结果如下:

Original array: 64 34 25 12 22 11 90 
Sorted array: 11 12 22 25 34 64 90 

请注意,冒泡排序是一种简单但效率较低的排序算法,特别是在处理大量数据时。如果需要更高效的排序算法,可以考虑使用其他算法,如快速排序或归并排序。

冒泡排序是一种简单的排序算法,其基本思想是通过相邻元素的比较和交换来将较大的元素逐步向后移动,从而实现排序。下面是汇编语言实现冒泡排序的示例代码:

section .dataarray db 5, 4, 3, 2, 1len equ $ - arraysection .textglobal _start_start:mov ecx, len        ; 循环次数为数组长度outer_loop:mov esi, 0          ; 内层循环起始索引为0inner_loop:mov eax, [array + esi]      ; 获取当前元素cmp eax, [array + esi + 1]  ; 和下一个元素进行比较jg swap                     ; 如果当前元素大于下一个元素,则跳转到交换操作inc esi                     ; 否则,继续比较下一对元素loop inner_loop             ; 循环dec ecx                     ; 外层循环次数减1jnz outer_loop              ; 如果还有未排序的元素,则继续外层循环; 输出排序后的数组mov ecx, lenmov esi, 0print_loop:mov eax, [array + esi]      ; 获取当前元素call print_numberinc esiloop print_loop; 退出程序mov eax, 1xor ebx, ebxint 0x80swap:xchg [array + esi], eax     ; 交换当前元素和下一个元素inc esiloop inner_loop             ; 继续内层循环print_number:; 将数字转换为字符串push ebxpush ecxpush edxmov ebx, 10                 ; 除数为10xor ecx, ecx                ; 初始化商为0xor edx, edx                ; 初始化余数为0div_loop:xor edx, edx            ; 清除余数div ebx                 ; 进行除法运算add dl, '0'             ; 将余数转换为字符push edx                ; 将字符入栈inc ecx                 ; 商加1test eax, eax           ; 检查是否还有商jnz div_loop            ; 如果还有商,则继续循环print_loop:pop edx                 ; 弹出字符mov [result + ecx - 1], dl  ; 将字符存入结果数组loop print_loop         ; 循环; 输出结果数组mov edx, ecx                ; 结果数组长度mov ecx, resultmov eax, 4mov ebx, 1int 0x80; 清空结果数组mov ecx, lenmov esi, 0clear_result:mov byte [result + esi], 0inc esiloop clear_resultpop edxpop ecxpop ebxretsection .bssresult resb 10

上述汇编代码实现了冒泡排序的功能,并将排序结果输出到控制台。需要注意的是,该代码使用了Linux系统的系统调用来进行输入和输出操作。

编写好代码后,可以通过汇编器进行汇编和链接操作,将汇编代码转换为可执行文件。

以下是一个用Python实现的冒泡排序程序:

def bubble_sort(arr):n = len(arr)for i in range(n-1):for j in range(n-1-i):if arr[j] > arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j]return arr# 示例
array = [5, 3, 8, 2, 1, 4]
sorted_array = bubble_sort(array)
print(sorted_array)

该程序通过两个嵌套的循环来实现冒泡排序。外层循环控制需要比较的轮数,内层循环逐个比较相邻的元素并进行交换。在每一轮循环结束后,最大的元素会被冒泡到序列的末尾。最后返回排序后的数组。

上述示例中,输入的数组为[5, 3, 8, 2, 1, 4],经过冒泡排序后,输出的排序结果为[1, 2, 3, 4, 5, 8]

以下是一个用Java编写的冒泡排序程序:

public class BubbleSort {public static void bubbleSort(int[] arr) {int n = arr.length;for (int i = 0; i < n-1; i++) {for (int j = 0; j < n-1-i; j++) {if (arr[j] > arr[j+1]) {int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}}public static void main(String[] args) {int[] array = {5, 3, 8, 2, 1, 4};bubbleSort(array);for (int i = 0; i < array.length; i++) {System.out.print(array[i] + " ");}}
}

该程序也是通过两个嵌套的循环来实现冒泡排序。外层循环控制需要比较的轮数,内层循环逐个比较相邻的元素并进行交换。在每一轮循环结束后,最大的元素会被冒泡到序列的末尾。

上述示例中,输入的数组为{5, 3, 8, 2, 1, 4},经过冒泡排序后,输出的排序结果为1 2 3 4 5 8

以下是用C语言实现的冒泡排序算法:

#include <stdio.h>void bubbleSort(int arr[], int size) {int i, j, temp;for (i = 0; i < size - 1; i++) {for (j = 0; j < size - i - 1; j++) {if (arr[j] > arr[j + 1]) {temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}int main() {int arr[] = {64, 34, 25, 12, 22, 11, 90};int size = sizeof(arr) / sizeof(arr[0]);printf("Original array: ");for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}bubbleSort(arr, size);printf("\nSorted array: ");for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}return 0;
}

在上面的代码中,我们首先定义了一个bubbleSort函数,该函数使用冒泡排序算法对给定的数组进行排序。然后,在main函数中定义了一个用于测试的整型数组arr,并计算了数组的大小。接下来,我们调用bubbleSort函数对数组进行排序,并使用两个for循环分别打印原始数组和排序后的数组。最后,我们返回0,以表示程序顺利结束。

运行上述代码,输出结果如下:

Original array: 64 34 25 12 22 11 90 
Sorted array: 11 12 22 25 34 64 90 

冒泡排序的时间复杂度是O(n^2),其中n是要排序的元素个数。

复杂度比选择排序好一些

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com