算法之冒泡排序
-
一：基本概念
冒泡排序(Bubble Sort)，又被称为气泡排序或泡沫排序；它是一种比较简单的排序算法，按待排序序列的先后顺序，依次比较相邻的两个数，将小数放在前面，大数放在后面。（若二者是升序，则不做任何操作，否则交换两数即可）
二：图文说明
冒泡排序示意图.png
我们先分析第一趟排序：
1. 依次从前往后走，a[0]>a[1],则进行交换，交换之后的结果为a[0]=1,a[1]=5；
2. 接着继续进行比较，a[1]<a[2],则不进行交换；
3. 接着继续进行比较，a[2]>a[3],则进行交换，交换之后的结果为a[2]=-2,a[3]=12；
4. 接着继续进行比较，a[3]>a[4],则进行交换，交换之后的结果为a[3]=-1,a[4]=12；
于是，第一趟排序完成之后，数列{5,1,12,-2,-1}变成了{1,5,-2,-1,12},此时，数列末尾的数最大。
根据这种方法，对数列依次进行排序，即得排序完之后的升序结果！
-
三：代码实现
- C语言实现
#include <stdio.h> /* 冒泡排序 */ void show(int arr[],int len);//打印出数组 void swap(int arr[],int i,int j); //交换数组中的两个位置 void bubbleSort(int arr[],int len);//冒泡排序算法 int main(void) { int arr[] = {5, 1, 12, -2, -1}; int len = sizeof(arr)/sizeof(*arr); printf("待排序数组为:\n"); show(arr,len); bubbleSort(arr,len); printf("排序之后的数组为:\n"); show(arr,len); return 0; } void show(int arr[],int len) { int i; for(i=0;i<len;i++) { printf("%d ",arr[i]); } printf("\n"); } void swap(int arr[],int i,int j) { int temp; temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } void bubbleSort(int arr[],int len) { int i = 0; int j = 0; int change = 1; for(i=0; (i<len) && change; i++) { change = 0; for(j=len-1; j>i; j--) { if( arr[j] < arr[j-1] ) { swap(arr, j, j-1); change = 1; } } } }2.JAVA实现
package com.data; import java.util.Arrays; /** * @author mxf * 冒泡排序 */ public class BubbleSort { public static void main(String[] args) { int[] arr = {5, 1, 12, -2, -1}; //输出排序前的数组 System.out.println("排序前的数组为:"+Arrays.toString(arr)); int swapped = 1; //排序 for(int i=0;i<arr.length-1 &&swapped!=0;i++){//外层循环控制排序趟数 for(int j=0;j<arr.length-1-i;j++){//内层循环控制每一趟中的排序次数 swapped = 0; if(arr[j]>arr[j+1]){//如果前面的数大于后面的数则进行交换 int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; swapped = 1; } } } //输出排序后的数组 System.out.println("排序后的数组为:"+Arrays.toString(arr)); } } -
四：冒泡排序的时间复杂度和稳定性
- 冒泡排序的时间复杂度
- 冒泡排序的时间复杂度是O(NN)。
假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历多少次呢？N-1次！因此，冒泡排序的时间复杂度是O(NN)。
- 冒泡排序稳定性
- 冒泡排序是稳定的算法，它满足稳定算法的定义。冒泡排序就是把小的元素往前调（或者把大的元素往后调）。注意是相邻的两个元素进行比较，而且是否需要交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把它们俩再交换一下。如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个元素相邻起来，最终也不会交换它俩的位置，所以相同元素经过排序后顺序并没有改变。
