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;
}
