浏览 2268 次
锁定老帖子 主题:java数据结构之简单排序
该帖已经被评为新手帖
|
|
---|---|
作者 | 正文 |
发表时间:2008-05-05
1,冒泡排序;2,选择排序;3,插入排序 这里的排序针对都是简单类型的数组进行排序,他们的比较次数都为O(n^2),但是相对来说,插入排序的交换次数是最少的,大概为冒泡排序的一半,其选择排序所用的交换次数也要少。这三个排序都是稳定的排序算法。 1,冒泡排序: 执行该程序,对于1000000个元素的数组排序,其算法所需时间大概为212ms package pku.ss.datastructure.Sort; public class BubbleSort { public static void main(String[] args) { int max = 1000000; ArrayBubble arr = new ArrayBubble(max); long startTime = System.currentTimeMillis(); for (int j = 0; j < max; j++) { double element = (double) (java.lang.Math.random() * (max - 1)); arr.insert(element); } long endTime = System.currentTimeMillis(); System.out.println("Sort time: " + (endTime - startTime) + " ms"); } } class ArrayBubble { private int nElement; private double[] array; ArrayBubble(int max) { array = new double[max]; nElement = 0; } public void insert(double x) { // if (array.length == 10) { // System.out.println("[ERROR]Out of memory!"); // System.out.println("[INFO]Atempt to insert into a full array"); // System.exit(0); // } else { array[nElement] = x; nElement++; // } } public void display() { for (int i = 0; i < nElement; i++) { System.out.print(array[i] + " "); } System.out.println(); System.out.println(); } public void bubbleSort() { int outer; for (outer = nElement - 1; outer > 0; outer--) for (int j = 0; j < outer; j++) { if (array[j] > array[j + 1]) { swap(j, j + 1); } } } private void swap(int x, int y) { double temp; temp = array[x]; array[x] = array[y]; array[y] = temp; } } 2,选择排序 执行该程序,对于1000000个元素的数组排序,其算法所需时间大概为216ms package pku.ss.datastructure.Sort; public class SelectSort { public static void main(String[] args) { int max = 1000000; ArraySel arr = new ArraySel(max); long startTime = System.currentTimeMillis(); for (int j = 0; j < max; j++) { double element = (double) (java.lang.Math.random() * (max - 1)); arr.insert(element); } long endTime = System.currentTimeMillis(); System.out.println("Sort time: " + (endTime - startTime) + " ms"); } } /** ***************************************** */ class ArraySel { private double[] a; private int nElement; //-------------------------------------------------------- public ArraySel(int max) { a = new double[max]; nElement = 0; } //-------------------------------------------------------- public void insert(double element) { a[nElement] = element; nElement++; } //-------------------------------------------------------- public void display() { for (int i = 0; i < nElement; i++) System.out.print(a[i] + " "); System.out.println(); } //-------------------------------------------------------- public void selectSort() { int out, in, min; for (out = 0; out < nElement - 1; out++) { min = out; for (in = out + 1; in < nElement; in++) { if (a[in] < a[min]) { min = in; } } if(min!=out) swap(min, out); } } //-------------------------------------------------------- private void swap(int x, int y) { double temp; temp = a[x]; a[x] = a[y]; a[y] = temp; } } 3,插入排序 执行该程序,对于1000000个元素的数组排序,其算法所需时间大概为214ms package pku.ss.datastructure.Sort; public class InsertionSort { public static void main(String[] args) { int max = 1000000; ArrayIns arr = new ArrayIns(max); long startTime = System.currentTimeMillis(); for (int j = 0; j < max; j++) { double element = (double) (java.lang.Math.random() * (max - 1)); arr.insert(element); } long endTime = System.currentTimeMillis(); System.out.println("Sort time: " + (endTime - startTime) + " ms"); } } class ArrayIns { private double[] a; private int nElement; // -------------------------------------------------------- public ArrayIns(int max) { a = new double[max]; nElement = 0; } // -------------------------------------------------------- public void insert(double element) { a[nElement] = element; nElement++; } // -------------------------------------------------------- public void display() { for (int i = 0; i < nElement; i++) System.out.print(a[i] + " "); System.out.println(); } // -------------------------------------------------------- public void insertionSort() { int out, in; for (out = 1; out < nElement; out++) { double temp = a[out]; in = out; while (in > 0 && a[in - 1] >= temp) { a[in] = a[in - 1]; in--; } a[in] = temp; } } // -------------------------------------------------------- } 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |
发表时间:2008-05-05
数据结构很有用。。学习了~~~
|
|
返回顶楼 | |