java 数据结构学习之（二） 简单排序

冒泡排序最经典：

public void BubbleSort1(){

package sort;public class Sort {/** * @param args */public static void main(String[] args) {// TODO Auto-generated method stubSort o = new Sort(10000);for (int i = 10; i > 0; i--) {o.insert(i);}o.insert(9);o.insert(8);/*for (int i = 0; i < 10000; i++) {o.insert(i);}*/long begin = System.currentTimeMillis();o.insertSort();long end = System.currentTimeMillis();System.out.println("time="+(end - begin));o.display();}private int[] arr = null;private int nElement = 0;//当前数组的实际长度public Sort(int size){this.arr = new int[size];this.nElement = 0;}public int[] getArr(){return this.arr;}/**插入 * @param c */public void insert(int c){arr[nElement++] = c;}public void BubbleSort1(){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);}}}}/**（优化后的冒泡排序） * 双向冒泡排序  * ps: 获取最大的数放在最右边后，回头获取最小的数放在最左边。以此类推，外层循环次数 n / 2，貌似比单向冒泡快一点。 */public void BubbleSort2(){int i,j,k,left = 0,right = nElement - 1;for (i = nElement/2; i > 0; i--) {for (j = left; j < right; j++) {if(arr[j] > arr[j+1]){swap(j,j+1);}}for (k = right - 1; k > left; k--) {if(arr[k] < arr[k - 1] ){swap(k,k - 1);}}left++;right--;}}/**（优化后的冒泡排序） * ps:如果 有一次比较没有做任何数据移动，说明已经排好序了，可以结束比较了。 */public void BubbleSort3(){boolean isSorted = false;for (int i = nElement - 1; i > 0 && !isSorted; i--) {isSorted = true;//假设已经排好序for (int j = 0; j < i; j++) {if(arr[j] > arr[j + 1]){swap(j,j + 1);isSorted = false;}}}}/**（优化后的冒泡排序） * ps:记录最后一次交换位置，这样就可以确定到底那些区域还没有排好序，缩小比较范围。 */public void BubbleSort4(){int lastIndex = nElement - 1,j=0;while(lastIndex > 0){for (int i = j = 0; i < lastIndex; i++) {if(arr[i] > arr[i + 1]){swap(i, i+1);j = i;}}lastIndex = j;}}/** * 奇偶排序  * 第一次比较奇数对，第二次比较偶数对。 * 听说如果是多处理器这样排序效率高  */public void OddEvenSort(){boolean isSorted = false;int i=0;while(!isSorted){i++;isSorted = OddOrEventSort(0) || OddOrEventSort(1);}System.out.println(i);}private boolean OddOrEventSort(int i){boolean isSorted = true;for (int j = i; j < nElement - 1; j+=2) {if(arr[j] > arr[j+1]){swap(j, j+1);isSorted = false;}}return isSorted;}public void insertSort(){int repeat = 0,t = 0;for (int i = 1; i < nElement; i++) {int j = i;while (j > t && arr[i] <= arr[j - 1]){//发现重复值 设置为-1if(arr[i]==arr[j - 1]){arr[i] = -1;repeat++;}--j;}t = repeat;if(j < i){int temp = arr[i];for (int k = i; k > j; k--) {arr[k] = arr[k - 1];}arr[j] = temp;}}if(repeat > 0){nElement = nElement - repeat;for (int i = 0; i < nElement; i++) {arr[i] = arr[i + repeat];}}}public void insertSort2(){for (int i = 1; i < nElement; i++) {int j = i;int temp = arr[i];while(j > 0 && temp < arr[j - 1]){arr[j] = arr[--j];}arr[j] = temp;}}public static void insertSort(int[] elements){         for(int i = 1;i <elements.length; i++){             int j = -1;             while(j <= i && elements[i] > elements[++j]);//找到element[i]应该摆放的位置，此处可以利用查找算法进行优化             if(j < i){                 //将j之后的数据移动一位，然后把elements[i]移动到j处                 int temp = elements[i];                 for(int k = i-1;k >= j;k--){                     elements[k+1] = elements[k];                 }                 elements[j] = temp;             }         } }public void selectSort() {for (int i = 0; i < nElement - 1; i++) {int k = i;for (int j = i + 1; j < nElement; j++) {if (arr[k] > arr[j]) {k = j;}}if (k != i) {swap(k, i);}}}public void display(){for (int i = 0; i <nElement; i++) {System.out.println(arr[i]);}}private void swap(int a,int b){    arr[a] = arr[a] + arr[b];arr[b] = arr[a] - arr[b];arr[a] = arr[a] - arr[b];}}

?