Java排序算法之冒泡排序

java冒泡排序算法
1.基本思想：
对比相邻的元素值，如果满足条件就交换元素值，把较小的元素移动到数组的前面（从小到大排序），把大的元素移动到数组的后面，即交换两个元素的位置，这样较小的元素就像气泡一样从底部上升到顶部。
2.算法实现：
冒泡算法由双层循环实现，其中外层循环用于控制排序轮数，一般为要排序的数组长度减1，因为最后一次循环只剩下一个数组元素，不需要对比，同时已经完成排序了。内层循环主要是用于对比数组中每个邻近元素的大小，以确定是否交换位置，对比和交换的次数随排序轮数而减少。
3.代码public class maopaopaixu { public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner input=new Scanner(System.in);
int[] array= {10,9,8,7,6,5,4,3,2,1};
System.out.println("排序前数组为：");
for(int i=0;i<array.length;i++)
System.out.print(array[i]+" ");
System.out.println();
BubbleSort(array);
System.out.println("排序后数组为：");
for(int i=0;i<array.length;i++)
System.out.print(array[i]+" ");
}
public static void BubbleSort(int[] array) {
for(int i=1;i<array.length;i++) {
for(int j=0;j<array.length-i;j++) {
int temp;
if(array[j]>array[j+1]) {
temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
}
}}
与选择排序,插入排序一样,冒泡排序也是常规的排序法之一,冒泡排序的思想主要放在"冒泡"二字.
这个冒泡排序算法有点想ThinkMarkets返佣www.kaifx.cn/broker/thinkmarkets.html水中的泡泡往上冒一样,水中的泡泡月往上变得越大,冒泡排序思想跟这个是一样的.
冒泡排序思想:取最后一个元素,往前遍历并与遍历的元素比较,符合交换规则(或大或小),那么交换位置,接着往前遍历,知道遍历到已经排好序的序列为止,那么此时这个元素就是极大/极小值,也就是完成了本次循环的排序:
要排的序列为 int array[] = {12,32,2,4,6,54,34,76,89,32,14};排序为升序排序
(红色代表已排序列,黑色代表待排序列)
第一次: {12,32,2,4,6,54,34,76,89,32,14} -> 14往前冒,14<32,二者交换位置 -> {12,32,2,4,6,54,34,76,89,14,32}
            -> 14<89,二者交换位置-> {12,32,2,4,6,54,34,76,14,89,32}->  ... -> {12,32,2,4,6,14,54,34,76,89,32}
            ->14>6,不交换-> {12,32,2,4,6,14,54,34,76,89,32} ->...-> {12,2,32,4,6,14,54,34,76,89,32}
            -> 2<12,二者交换位置->{2,12,32,4,6,14,54,34,76,89,32}
以上就一轮排序完成,接着那32往前冒,以此类推,最后得到{2, 4, 6, 12, 14, 32, 32, 34, 54, 76, 89}
下边来看代码实现
#include <iostream>
#include <string.h>
#include <errno.h>
#include <stdio.h>
using namespace std;
//需要注意的是,这里的类模板需要放在头文件中去实现,这里为了直观,直接放这里了
template <typename T>
class Sort
{
private:
static void swap(T& nLeft, T& nRight)
{
T tmp = nLeft;
nLeft = nRight;
nRight = tmp;
}
public:
//Min2Max为升序\降序控制
static void Bubble(T nArray, int nLen, bool Min2Max = true)
{
for(int i=0; i<nLen; i++)
{
for(int j=nLen-1; j>i; j--)
{
if( Min2Max ? (nArray[j] < nArray[j-1]):(nArray[j] > nArray[j-1]))
{
//交换位置
swap(nArray[j], nArray[j-1]);
}
}
}
}
};
int main(int argc, char argv[])
{
int array[] = {12,32,2,4,6,54,34,76,89,32,14};
int len = sizeof(array)/sizeof(int);
Sort<int>::Bubble(array, len);
for(int i=0; i<len; i++)
{
cout << array[i] << " ";
}
cout << endl;
return 0;
}
/**

• @program: JavaSpecialityDeep
• @author: Mr.Zerah
• @create: 2018-10-25 22:52
• @description: 冒泡排序
• 冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。
• 如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复n 次，
• 就完成了 n 个数据的排序工作。
  **/
  public class BubbleSort {
  public void bubbleSort(Integer[] arr, int n) {
  if (n <= 1) return; //如果只有一个元素就不用排序了
  for (int i = 0; i < n; ++i) {
  // 提前退出冒泡循环的标志位,即一次比较中没有交换任何元素，这个数组就已经是有序的了
  boolean flag = false;
  for (int j = 0; j < n - i - 1; ++j) { //此处你可能会疑问的j<n-i-1，因为冒泡是把每轮循环中较大的数飘到后面，
  // 数组下标又是从0开始的，i下标后面已经排序的个数就得多减1，总结就是i增多少，j的循环位置减多少
  if (arr[j] > arr[j + 1]) { //即这两个相邻的数是逆序的，交换
  int temp = arr[j];
  arr[j] = arr[j + 1];
  arr[j + 1] = temp;
  flag = true;
  }
  }
  if (!flag) break;//没有数据交换，数组已经有序，退出排序
  }
  }
  public static void main(String[] args) {
  Integer arr[] = {2, 4, 7, 6, 8, 5, 9};
  SortUtil.show(arr);
  BubbleSort bubbleSort = new BubbleSort();
  bubbleSort.bubbleSort(arr, arr.length);
  SortUtil.show(arr);
  }
  }
  冒泡排序的思想是蛮力法。冒泡，顾名思义，每次选择后面一个元素（最大或者最小）冒上来，从而得到一个有序的序列。
  public class BubbleSort {
  public void bubbleSort(int[] array) {
  int len = array.length;
  for(int i = 0; i < len - 1; i++) {
  for(int j = len - 2; j >= i; j--) {
  if(array[j] > array[j + 1]) {
  swap(array, j, j + 1);
  }
  }
  }
  }
  public void swap(int[] array, int i, int j) {
  int temp = array[i];
  array[i] = array[j];
  array[j] = temp;
  }
  }
  对冒泡排序的改进，主要是设置一个标识flag，标记数组是否已经排序完成，不再需要进行剩余的循环了。
  public void bubbleSort(int[] array) {
  boolean flag = true;//设计一个标识，标记数组是否已经完成排序，不再需要进行排序了
  int len = array.length;
  for(int i = 0; (i < len - 1) && flag; i++) {
  flag = false;
  for(int j = len - 2; j >= i; j--) {
  if(array[j] > array[j + 1]) {
  swap(array, j, j + 1);
  flag = true;
  }
  }
  }
  }
  public class Demo {
  public static void main(String[]args){
  int[] array = new int[]{5,8,6,3,9,2,1,7};
  int[] test = new int[]{3,4,2,1,5,6,7,8};
  //aa(array);
  bb(test);
  System.out.println(Arrays.toString(test));
  }
  public static void test(int []array){
  int temp=0;
  for(int i=0;i<array.length;i++){
  for(int j=0;j<array.length-i-1;j++){
  if(array[j]>array[j+1]){
  temp=array[j];
  array[j]=array[j+1];
  array[j+1]=temp;
  }
  }
  }
  }
  //冒泡排序第二版
  public static void aa(int []array){
  int temp=0;
  int s=0;
  for(int i=0;i<array.length;i++){
  boolean is=true;
  for(int j=0;j<array.length-i-1;j++){
  if(array[j]>array[j+1]){
  temp=array[j];
  array[j]=array[j+1];
  array[j+1]=temp;
  is=false;
  }
  }
  if(is){
  break;
  }else{
  s++;
  }
  }
  System.out.println(""+s);
  }
  //冒泡排序第三版
  public static void bb(int[] array){
  int temp=0;
  //记录最后一次交换的位置
  int lastExchangeIndex = 0;
  //无序数列的边界，每次比较只需要比到这里为止
  int sortBorder = array.length - 1;
  //用来统计外层循环几次
  int sum=0;
  for(int i=0;i<array.length;i++){
  //有序标记，每一轮的初始是true
  boolean isSorted = true;
  //用来统计每次内层循环比较的次数
  int num=0;
  for(int j=0;j<sortBorder;j++){
  if(array[j]>array[j+1]){
  temp=array[j];
  array[j]=array[j+1];
  array[j+1]=temp;
  //有元素交换，所以不是有序，标记变为false
  isSorted=false;
  //把无序数列的边界更新为最后一次交换元素的位置
  lastExchangeIndex = j;
  num++;
  }
  }
  System.out.println(""+num);
  sortBorder = lastExchangeIndex;
  if(isSorted){
  break;
  }else {
  sum++;
  }
  }
  System.out.println(""+sum);
  }
  }
  void BubbleSort(int arr[], int len)
  {
  int i, j;
  int tmp;
  int mark = 0;//标志位
  for (i = 0; i < len - 1; ++i)
  {
  mark = 0;
  for (j = 0; j < len - 1 - i; ++j)
  {
  if (arr[j] > arr[j + 1])
  {
  tmp = arr[j];
  arr[j] = arr[j + 1];
  arr[j + 1] = tmp;
  mark = 1;
  }
  }
  /优化 如果已排好序make标志位，直接break/
  printf("%d\n", i);
  if (mark == 0)
  {
  break;
  }
  }
  }
  void BubbleShow(int arr[], int len)
  {
  for (int i = 0; i < len; ++i)
  {
  printf("%d ", arr[i]);
  }
  printf("\n");
  }

int main()
{
int arr[] = { 7, 2, 3, 4, 5, 6, 7, 6 };
int arr1[] = { 56, 1321, 6, 13, 16, 13, 13, 1, 33, 0 };
//0 1 6 13 13 13 16 33 56 1321
int len = sizeof(arr) / sizeof(arr[0]);
BubbleSort(arr,len);
BubbleShow(arr, len);
return 0;
}