实现冒泡排序算法
试题类型:编程题    难度:中等

使用编程语言实现冒泡排序算法。

冒泡排序算法的原理是比较两个相邻的元素,将值大的元素和值小的元素进行交换。具体实现思路是:依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后。重复第一趟步骤,直至全部排序完成。

例如:给定待排序数列89,23,17,21,101,90,22,30。若按照从小到大排序,从数列左侧第一个数89开始,依次比较相邻的两个数,若89小于后面的数,则比较的两数不进行交换,若89大于后面的数,则比较的两数进行交换。


全部题解
详解冒泡排序算法
子衿

冒泡排序是将一组数字多趟顺序比较,一次比较两个数字,如果他们的顺序错误就把他们交换过来,小数或(大数)逐渐往上冒,当再没有需要交换的数字时,说明该组数已经排序完成。

对下面的一组数用冒泡排序算法,并按照从小到大的顺序排序。

01.png

排序前的一组数,我们称为原始数列,每两个数进行一次比较,称为一轮比较。

02.png

第一轮比较:23与34比较,23小于34,两个数不用交换位置。

03.png

第二轮比较:34与5比较,因为34大于5,因此34和5交换位置。

04.png

05.png

第三轮比较:34与7比较,因为34大于7,因此34与7交换位置。

06.png

07.png

第四轮比较:比较34和56,因为34小于56,两个数不用交换位置。

08.png

在前面的四轮比较中,从数列左侧的第一个数开始,顺序两两比较两个数的大小,如果前面一个数比后面一个数大,就交换两数的位置,直到数列的最后一个数比较完毕。

这四轮比较下来,称为一趟比较。如果在该趟比较中,存在两个数交换位置的情况,就需要进行下一趟比较,直到再没有数字进行交换,算法结束。

因为在第一趟比较中,存在两数的位置交换,因此还需要进行第二趟的比较。

第二趟比较

第二趟比较也是从数列左侧的第一个数开始,顺序两两比较两个数的大小。不过第二趟比较就不需要再比较数列右侧的最后一个数了,因为在第一趟比较的过程中,该数列最大的数已经被交换到数列右侧最后的一个位置了。

09.png

第一轮比较:比较23和5,因为23大于5,因此23和5交换位置。

10.png

11.png

第二轮比较:比较23和7,因为23大于7,因此23和7交换位置。

12.png

13.png

第三轮比较:比较23和24,因为23小于24,两个数不用交换位置。

14.png

至此,第二趟比较完成。最后的一个数56就不用比较了,因为56在第一趟比较中就已经为自己找到了正确的位置。

从第三轮的比较结果来看,排序已经完成,每个数都自己找到了正确的位置。已经不需要再进行第三趟比较了。


python实现冒泡排序
小试牛刀

冒泡排序是一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历列表的工作是重复地进行直到没有再需要交换,也就是说该列表已经排序完成。

下面给出Python实现。

def bubbleSort(arr):
  n = len(arr)
  # 遍历所有数组元素
  for i in range(n):
     for j in range(0, n-i-1):
        if arr[j] > arr[j+1]:
         arr[j], arr[j+1] = arr[j+1], arr[j]
 
arr = [64, 34, 25, 12, 22, 11, 90]
 
bubbleSort(arr)
 
print ("排序后的数组:")
for i in range(len(arr)):
    print ("%d" %arr[i])


实现冒泡排序算法
编程训练营官方题解

用Java语言实现:

程序声明一个整型数组,存储要待排序的数值,然后用for循环语句控制数组的扫描趟数,扫描趟数为待排序数组元素的个数减去1,在每趟扫描中,用for循环遍历待排序数组元素,并进行比较和位置交换,循环范围介于0到排序数组元素的个数减去1再减去外层循环当前执行的扫描趟数,因为i趟排序过程中,已经把i个较大的数交换到数组length-i的数组序号范围,无需再比较和交换。


public class SortSample {
  
    /**
     * @Title: main
     * @Description:Java程序入口main方法
     * @param @param args 参数
     *
     * @return void 返回类型
     * @throws
     */
  
    public static void main(String[] args) {
       /**
        * 声明长度为10的一维数组,
        * 存储待排序的数值 数组类型是int
        */
       int arr[] = new int[10];
       int i;
       Scanner sc = new Scanner(System.in);
       System.out.printf("请输入 %d 个整数", arr.length);
       // 使用for循环,接收用户输入的整数
       for (i = 0; i < arr.length; i++) {
           System.out.printf("\n 请输入第 %d 个整数:", i + 1);
           arr[i] = sc.nextInt();
  
       }
       System.out.print("\n ***开始排序***");
       /**
        * 控制排序趟数
        * 有多少个待排序的数值就扫描数组多少趟
        *  针对每个待排序数值都要和其它数值进行比较
        */
       for (i = 0; i < arr.length - 1; i++) {
           /**
            * 控制每一趟排序多少次
            * 每一趟排序都会把较大的数值移动到数组后面
            * 第i趟排序循环次数为数组长度减去已经排过序的i个元素
            * 如果第j个元素大于第j+1个元素,则交换
            */
           for (int j = 0; j < arr.length - 1 - i; j++) {
              if (arr[j] > arr[j + 1]) {
                  int temp = arr[j];
                  arr[j] = arr[j + 1];
                  arr[j + 1] = temp;
              }
           }
       }
       System.out.print("\n ***排序完成***\n");
       System.out.println("排序后的数组为:");
       for (i = 0; i < arr.length; i++) {
           System.out.print(arr[i] + ",");
       }
  
    }
  
}


  • 备案号:鲁ICP备15001146号
  • @1997-2018 潍坊米粒花网络技术有限公司版权所有