package sorting; /* * 常用排序算法 * out控制外层循环 * in控制内存循环 */ public class Array { private int[] array; private int n; //元素个数 //构造方法中初始化数组长度 public Array(int maxLength) { this.array = new int[maxLength]; this.n = 0; } //插入一个元素,未检查边界 public void insert(int value) { if(this.array.length==this.n) { System.out.println("数组已满，不能插入！"); return; } this.array[n] = value; this.n++; } //终端输出所有元素 public void display() { for(int j=0; j<this.n; j++) { System.out.print(this.array[j] + " "); if(j%10==9) //每输出10个元素换一行 { System.out.println(""); } } System.out.println(""); } //冒泡排序 /* * 向后冒泡 * 先比较交换a[0]和a[1],再a[1]和a[2],再a[2]和a[3].... * 这样经过第一轮冒泡，最大(小)的元素被排到了最后， * 此时最后一个元素已经变为有序 * 再对前n-1个元素进行同样的冒泡 */ public void bubbleSort() { int in, out; for(out=this.n-1; out>=1; out--) //n个元素总共进行n-1轮冒泡 { for(in=0; in<out; in++) { if(this.array[in] > this.array[in+1]) //升序排列 { swap(in, in+1); } } } } //选择排序 /* * 先假定第一个元素是排好序的， * 然后将后面的元素依次与第一个进行比较， * 如果小于第一个元素，则与第一个交换， * 这样经过第一轮选择比较， * 最小的元素被排到了第一， * 再对后面的n-1个元素进行同样的处理 */ public void selectSort() { int in, out, min; //min保留每一轮最小值的下标 for(out=0; out<this.n-1; out++) { min = out; //对于每轮选择，首先假定第一个已经有序,保存每一轮已排好序子序列中的最后一个元素的下标 for(in=out+1; in<this.n; in++) //依次将待排序的每个元素与已排序的最后一个元素比较 { if(this.array[in] < this.array[min]) { min = in; //保存最小元素的下标，在内层循环中，min值不断被替换 } } swap(out, min); } } //直接插入排序 /* * 先假定第一个元素是一个排好序的序列， * 然后将后面的n-1个元素依次插入到这个已排好序的序列中， * 插入的方法为：找到待排序元素的插入位置， * 然后将这个位置以后的元素（属于已排好序的序列）都向后移动一个位置， * 腾出一个空间给待排序元素， * 这样，已排好序的序列从一个元素，不断增长，直到所有的待排序元素都加入到了这个序列中 */ public void insertSort() { int in, out; for(out=1; out<this.n; out++) //首先假定第一个已经排好序，从第2个元素开始，将其依次插入到前面的已排序序列中 { int temp = this.array[out]; //保存待待排序元素的值 in = out; //初始待插入位置in //寻找合适位置 while(in>0 && this.array[in-1]>temp) //向前推移，一次比较 { this.array[in] = this.array[in-1]; //向后移动，腾出位置 --in; } this.array[in] = temp; //插入 } } //shell排序 public void shellSort() { int inner; int outer; int temp; int h = 1; while(h <= this.n / 3) //计算最大间隔 { h = h*3 + 1; } while(h>0) //直到间隔为1 { for(outer=h; outer<this.n; outer++) { temp = this.array[outer]; inner = outer; while(inner>h-1 && this.array[inner-h]>=temp) //内层插入排序 { this.array[inner] = this.array[inner-h]; inner -= h; } this.array[inner] = temp; } h = (h-1)/3; //缩小间隔 } } //快速排序 public void quickSort(int left, int right) { if(left>=right) { return; } else { int pivot = this.array[right]; //选择每个子数组最右端的元素作为枢纽元素 int partition = partition(left, right, pivot); quickSort(left, partition-1); //对左子数组递归 quickSort(partition+1, right); //对右子数组递归 } } //划分 public int partition(int left, int right, int pivot) { int leftPointer = left-1; //left of the first element int rightPointer = right; //right of the pivot //最外层循环退出以后，左右指针重叠，或者刚好互相越过 while(true) { //将左指针不断向右推移，直到遇到大于或等于枢纽元素为止 while(this.array[++leftPointer]<pivot); //将右指针不断向左推移，直到遇到小于或等于枢纽元素为止 while(rightPointer>0 && this.array[--rightPointer]>pivot); //每个子数组最右端的元素开始不动，作为枢纽元素 if(leftPointer >= rightPointer) //左右指针重叠或互相越过，退出循环 { break; } else { swap(leftPointer,rightPointer); //交换 } } swap(leftPointer, right); //把枢纽插入到正确位置 return leftPointer; //返回左指针，即右边子数组最左边的那个元素 } //按数组下标交换值 public void swap(int one, int two) { int temp = this.array[one]; this.array[one] = this.array[two]; this.array[two] = temp; } public int[] getArray() { return array; } public void setArray(int[] array) { this.array = array; } public int getN() { return n; } public void setN(int n) { this.n = n; } }
