论坛首页 → 综合技术论坛 →

线性排序的实现

浏览 2622 次
锁定老帖子 主题：线性排序的实现
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
  • sunxboy
  • 等级: 初级会员
  • 性别:
  • 文章: 106
  • 积分: 0
  • 来自: 武汉
   发表时间：2007-10-12  
java 代码
 
  1. /** 
  2.  * 线性表 
  3.  */  
  4. package line;  
  5.   
  6. /** 
  7.  * @author sumbeam 
  8.  *  
  9.  */  
  10. public class LineSort {  
  11.   
  12.     // 数据结构  
  13.     private int data[];  
  14.   
  15.     // 最大容量  
  16.     private int maxSize;  
  17.   
  18.     // 实际容量  
  19.     private int size;  
  20.   
  21.     public LineSort(int maxSize) {  
  22.   
  23.         this.maxSize = maxSize;  
  24.         data = new int[maxSize];  
  25.         size = 0;  
  26.     }  
  27.   
  28.     /** 
  29.      * 查找某数据的位置 
  30.      *  
  31.      * @param data 
  32.      *            数据 
  33.      * @return 位置 
  34.      */  
  35.     public int inStr(int data) {  
  36.         for (int i = 0; i < this.data.length; i++) {  
  37.             if (this.data[i] == data)  
  38.                 return i;  
  39.         }  
  40.         return -1;  
  41.     }  
  42.   
  43.     /** 
  44.      * 判断是否到达最后一位 
  45.      *  
  46.      * @return 是否已满 
  47.      */  
  48.     public boolean isEnd() {  
  49.         return size == maxSize;  
  50.     }  
  51.   
  52.     /** 
  53.      * 判断数据是否为空 
  54.      *  
  55.      * @return 是否为空 
  56.      */  
  57.     public boolean isEmpty() {  
  58.         return size == 0;  
  59.     }  
  60.   
  61.     /** 
  62.      * 在老数据前增加一个新的数据 
  63.      *  
  64.      * @param oldData 
  65.      *            老数据 
  66.      * @param newData 
  67.      *            新数据 
  68.      * @return 是否成功 
  69.      */  
  70.     public boolean add(int oldData, int newData) {  
  71.   
  72.         int p = inStr(oldData);  
  73.         if (p != -1)  
  74.             return insert(newData, p);  
  75.         return false;  
  76.     }  
  77.   
  78.     /** 
  79.      * 将数据插入在第一位 
  80.      *  
  81.      * @param data 
  82.      *            要插入的数据 
  83.      * @return 是否成功 
  84.      */  
  85.     public boolean addFirst(int data) {  
  86.   
  87.         return insert(data, 0);  
  88.     }  
  89.   
  90.     /** 
  91.      * 定义一个插入数据的方法 
  92.      *  
  93.      * @param data 
  94.      *            要插入的数据 
  95.      * @param p 
  96.      *            要插入的位置 
  97.      * @return 是否插入成功 
  98.      */  
  99.     public boolean insert(int data, int p) {  
  100.         if (isEnd()) {  
  101.             System.out.println("数据已满!");  
  102.             return false;  
  103.         }  
  104.         for (int i = (size - 1); i >= p; i--) {  
  105.             this.data[i + 1] = this.data[i];  
  106.         }  
  107.         this.size++;  
  108.         this.data[p] = data;  
  109.         return true;  
  110.     }  
  111.   
  112.     /** 
  113.      * 在最后一位插入一个数据 
  114.      *  
  115.      * @param data 
  116.      *            要插入的数据 
  117.      * @return 是否成功 
  118.      */  
  119.     public boolean addLast(int data) {  
  120.         return insert(data, size);  
  121.     }  
  122.   
  123.     /** 
  124.      * 先移除一个数据 
  125.      *  
  126.      * @param data 
  127.      *            要删除的数据 
  128.      * @return 是否成功 
  129.      */  
  130.     public boolean remove(int data) {  
  131.         if (isEmpty()) {  
  132.             System.out.println("数据是空的!");  
  133.             return false;  
  134.         }  
  135.         int p = inStr(data);  
  136.         if (p != -1) {  
  137.             for (int i = p; i < size; i++) {  
  138.                 this.data[i] = this.data[i + 1];  
  139.             }  
  140.             size--;  
  141.             return true;  
  142.         }  
  143.         return false;  
  144.     }  
  145.   
  146.     /** 
  147.      * 修改数据 
  148.      *  
  149.      * @param olddata 
  150.      *            要被修改的数据 
  151.      * @param newdata 
  152.      *            修改后的数据 
  153.      * @return 是否修改成功 
  154.      */  
  155.     public boolean updata(int olddata, int newdata) {  
  156.         int p = inStr(olddata);  
  157.         if (p != -1) {  
  158.             this.data[p] = newdata;  
  159.             return true;  
  160.         }  
  161.         return false;  
  162.     }  
  163.   
  164.     /** 
  165.      * 显示所有数据 
  166.      */  
  167.     public void display() {  
  168.         for (int i = 0; i < size; i++) {  
  169.             System.out.println(this.data[i]);  
  170.         }  
  171.     }  
  172.   
  173.     /** 
  174.      * 交换位置 
  175.      *  
  176.      * @param i 
  177.      *            位置i 
  178.      * @param j 
  179.      *            位置j 
  180.      */  
  181.     public void swap(int i, int j) {  
  182.         int temp = data[i];  
  183.         data[i] = data[j];  
  184.         data[j] = temp;  
  185.     }  
  186.   
  187.     /** 
  188.      * 选择排序 
  189.      */  
  190.     public void selectSort() {  
  191.         for (int i = 0; i < size - 1; i++) {  
  192.             int k = i;  
  193.             for (int j = i + 1; j < size; j++) {  
  194.                 if (data[k] > data[j])  
  195.                     k = j;  
  196.             }  
  197.             if (k != i)  
  198.                 swap(k, i);  
  199.         }  
  200.     }  
  201.   
  202.     /** 
  203.      * 冒泡排序 
  204.      */  
  205.     public void bubbleSort() {  
  206.         for (int i = 0; i < size - 1; i++) {  
  207.             boolean flag = false;  
  208.             for (int j = 0; j < size - i - 1; j++) {  
  209.                 if (data[j] > data[j + 1]) {  
  210.                     flag = true;  
  211.                     swap(j, j + 1);  
  212.                 }  
  213.             }  
  214.             if (!flag)  
  215.                 break;  
  216.         }  
  217.     }  
  218.   
  219.     /** 
  220.      * 插入排序 
  221.      */  
  222.     public void interSort() {  
  223.         for (int i = 0; i < size; i++) {  
  224.             int temp = data[i];  
  225.             int sort = i;  
  226.             while (sort > 0 && temp < data[sort - 1]) {  
  227.                 data[sort] = data[sort - 1];  
  228.                 sort--;  
  229.             }  
  230.             data[sort] = temp;  
  231.         }  
  232.     }  
  233.   
  234.     public static void main(String[] args) {  
  235.         LineSort line = new LineSort(1000);  
  236.         line.addFirst(1);  
  237.         line.addFirst(-1);  
  238.         line.add(-1, 2);  
  239.         line.add(1, 3);  
  240.         line.addLast(100);  
  241.         line.updata(3, 90);  
  242.         // line.remove(-1);  
  243.         // line.remove(2);  
  244.         // line.remove(100);  
  245.         // line.remove(90);  
  246.         // line.remove(1);  
  247.         // line.selectSort();  
  248.         // line.bubbleSort();  
  249.         line.interSort();  
  250.         line.display();  
  251.     }  
  252. }  
返回顶楼
         
论坛首页 → 综合技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics