class ArrayBub {
private long[] arr;
private int nElement;
public ArrayBub(int size) {
arr = new long[size];
nElement = 0;
}
@Override
public String toString() {
if (nElement == 0)
return "[]";
StringBuilder sb = new StringBuilder();
sb.append("[");
for (int i = 0; i < nElement; i++) {
sb.append(arr[i] + ",");
}
sb.deleteCharAt(sb.length() - 1);
sb.append("]");
return sb.toString();
}
public void display() {
System.out.println(toString());
}
public void insert(long value) {
if (nElement == arr.length) {
System.out.println("数组已满，插入终止");
return;
}
arr[nElement] = value;
nElement++;
}
/**
* 冒泡排序 思想：将小得数据项放在数组的最开始（下标为0）；并将最大的数据项放在最后（下标为nElement-1）.
*
* 外层for循环i从数组的最后开始，即i等于nElement-1,每经过一次循环减一。下标大于i的数据项都已经排好序。
* 变量i在每完成一次内部循环后就左移一位，因此不在处理那些已经排好序的数据了。
*
* 内层for循环计数器j从数组最开始起，即j=0,每完成一次内部循环加一，当等于i的时候结束一次循环。
* 在内层循环体中，下标为j和j+1的两个元素进行比较，如果前面的大就交换。
*
* 冒泡中的不变性：外层循环i右边的所有元素都有序，在整个运行过程中这个条件始终为真。 （第一趟开始前，因为i右边没有元素，所以起始时为真）
* 效率：交换和比较操作的复杂度都是O(n^2)
*/
public void bubbleSort() {
for (int i = nElement - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
swap(j, j + 1);
System.out.print("发生了交换:");
display();
}
}
System.out.print("第" + (nElement - i + 1) + "遍排序结果:");
display();
}
}
/**
* 选择排序：改进了冒泡排序，交换次数从O(n^2)减少到O(n),但是比较次数仍是O(n^2)。然而也是很大的一个改进。
* 因为这些大量的记录需要在内存中移动，
* 这就使得交换的时间和比较的时间相比起来，交换的时间更为重要。（在Java语言中不是这种情况，Java只是改变了引用位置，实际对象的位置并没有改变）
* 。 思想：从数组最左边第一个开始，遍历一遍找到最小的元素，将其和第一个位置的元素交换位置；
* 第二遍从最左边第二个开始，便利一遍找到最小的，和第二个位置元素交换 。。。遍历完 每一轮比较O(n)次，交换一次.
* 不变性：下表小于或等于外层循环变量的数据项总是有序的。
* 效率：和冒泡比起来更快，因为进行的交换次数少。当数据项较少时，特别是如果交换的时间级比比较的时间级大得多时，选择排序实际上相当快。
*/
public void selectSort() {
int minFlag;
for (int i = 0; i < nElement; i++) {
minFlag = i;
for (int j = i; j < nElement; j++) {
if (arr[j] < arr[minFlag]) {
minFlag = j;
}
}
swap(minFlag, i);
System.out.print("第" + (i + 1) + "遍排列");
display();
}
}
/**
* 插入排序：在外层for循环中，out变量从1开始，向右移动，标记了未排序不分的最左端的数据。
* 在内层while循环中，in变量从out开始，向左移动，直到temp变量小于in所指的元素，
* 或者已经不能再往左移动为止。while循环的每一趟都向右移动了一个已排序的数据项。
*
* 不变性：每趟结束时，在将temp位置的项插入后，比out变量下标号小的元素都是局部有序的。
* 效率：第一趟排序最多比较一次，第二趟最多2次。。。最后一趟比较N-1次。复制的次数大致等于
* 比较的次数，然而一次复制和一次交换的时间耗费不同，所以相对于随机数据，插入比冒泡快一倍
* 比选择排序略快。对于随机顺序数据进行插入排序也需要O(n^2)的时间级。
* 应用：对于有序或者基本有序的数据来说，插入排序要好得多。当数据有序的时候，while循环
* 的条件总为假，所以变成了外层循环中的一个简单语句，执行N-1次。这种情况下，算法
* 运行只需要O(n)的复杂度。///////然而对于逆序排列的数据，每次比较和移动都会执行，所以
* 插入排序不比冒泡排序快。
*/
public void insertSort() {
for (int out = 1; out < nElement; out++) {
long temp = arr[out];
int in = out;
while (in > 0 && arr[in - 1] >= temp) {
arr[in] = arr[in - 1];
in--;
}
arr[in] = temp;
System.out.println("第"+out+"遍排序"+toString());
}
}
/**
* 交换元素
*
* @param first
* @param second
*/
private void swap(int first, int second) {
long temp = arr[first];
arr[first] = arr[second];
arr[second] = temp;
}
}
public class BubSortDemo {
public static void main(String[] args) {
long[] a = { 12, 33, 2, 45, 43, 1, 9 };
ArrayBub ab = new ArrayBub(6);
for (int i = 0; i < a.length; i++) {
ab.insert(a[i]);
ab.display();
}
// ab.bubbleSort();
// ab.selectSort();
ab.insertSort();
ab.display();
}
}