温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

Java排序算法之冒泡排序

发布时间:2020-07-29 22:02:29 来源:网络 阅读:293 作者:专注地一哥 栏目:编程语言

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

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI