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