本帖最后由 棉/mg花/x糖 于 2013-5-26 19:17 编辑
数据结构:用数组实现双向冒泡排序算法(已优化)
注意:算法优化不是很理想,希望哪位大神能继续帮着优化!!谢谢^_^
程序源码如下:- package com.yb.ArrayAndString;
- import java.io.BufferedReader;
- import java.io.IOException;
- import java.io.InputStreamReader;
- public class DouBubbleSort {
- static int count = 0; //count记录交换趟数
- void douSort(int arr[]) { //双向冒泡排序方法
- int i = 0,j,temp,countNum; //countNum记录一趟中发生交换的次数
- boolean flag = true; //记录是否发生了交换
- int len = arr.length;
- while(flag) {
- flag = false;
- countNum = 0;
- for(j = len-i-2; j >= i; j--) { //自底向上扫描
- if(arr[j+1] < arr[j]) {
- temp = arr[j];
- arr[j] = arr[j+1];
- arr[j+1]= temp;
- flag = true;
- countNum++;
- }
- }
- for(j = i+2; j <= len-i-1; j++) { //自顶向下扫描
- if(arr[j-1] > arr[j]) {
- temp = arr[j-1];
- arr[j-1] = arr[j];
- arr[j]= temp;
- flag = true;
- countNum++;
- }
- }
- i++;
- if(flag) count++;
- if(countNum <= 1) break;
- }
- }
- public static void main(String[] args) throws IOException {
- // TODO Auto-generated method stub
- BufferedReader keyin = new BufferedReader(new InputStreamReader(System.in));
- String ch;
- int arr[] = new int[8];
- int len = arr.length;
- System.out.println("请从键盘输入8个整数,一行只输入一个数:");
- for(int i = 0; i < len; i++) {
- ch = keyin.readLine(); //用于读取一个字符串
- arr[i] = Integer.parseInt(ch); //将字符串类型ch转换成整数类型
- }
- //打印原始数据
- System.out.println("原始数据:");
- for(int i = 0; i < len; i++) {
- System.out.print(" "+arr[i]);
- }
- System.out.println("\n");
- DouBubbleSort p = new DouBubbleSort();
- p.douSort(arr); //实参为数组名
-
- //打印排序结果
- System.out.println("双向冒泡排序结果:");
- for(int i = 0; i < len; i++) {
- System.out.print(" "+arr[i]);
- }
- System.out.println("\n");
- System.out.println("排序趟数:"+count);
- }
- }
复制代码 运行结果:
|