主要内排序算法排序算法，平台，实现(二)
// TODO Auto-generated constructor stub
}
int[] arr;
int end;
@Override
public void doSort(int[] arr) {
this.arr =arr;
buidHeap();
for(int i = arr.length-1; i>0; i--){
arr[i] = getTop();
}
}
public void buidHeap(){
for(int i=1; i
for(int j=i; j>0; j=(j-1)/2){
int father = (j-1)/2;
if(arr[father]
int temp = arr[father];
arr[father] = arr[j];
arr[j] = temp;
}else{
break;
}
}
}
this.end =arr.length-1;
}
public int getTop(){
int top =arr[0];
arr[0] = arr[end];
end--;
//siftDown 0
for(int i=1;i<=end;i=i*2+1){
if(arr[i]
i++;
}
int father = (i-1)/2;
if(arr[father]
int temp = arr[father];
arr[father] = arr[i];
arr[i] = temp;
}else{
break;
}
}
return top;
}
}
选择排序实现：
[java]
package lee.sort;
public class SelectSort extends Sort{
public SelectSort() {
super("SelectSort");
// TODO Auto-generated constructor stub
}
@Override
public void doSort(int[] arr) {
for(int i=0;i
int min = i;
// found the min element in the sub array
for(int j=i;j
if(arr[j]
min = j;
}
}
int temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
}
快速排序实现：
[java]
package lee.sort;
public class QuickSort extends Sort{
public QuickSort() {
super("QuickSort");
// TODO Auto-generated constructor stub
}
public void doQuickSort(int[] arr , int left ,int right) {
if(left
int mid = partiton(arr,left,right);
doQuickSort(arr , left , mid-1);
doQuickSort(arr , mid+1 , right);
}
}
int partiton(int[] arr,int left ,int right){
int key = arr[left];
while(left
while(leftkey){
right--;
}
arr[left] = arr[right] ;
while(left
left++;
}
arr[right] = arr[left];
}
arr[left] =key;
return left;
}
@Override
public void doSort(int[] arr) {
doQuickSort(arr,0,arr.length-1);
}
}
简单插入排序实现：
[java]
package lee.sort;
public class InsertSort extends Sort{
public InsertSort() {
super("InsertSort");
}
@Override
public void doSort(int[] arr) {
for(int i=1;i
int key = arr[i];
int j;
for(j = i; j>0; j--){
if(arr[j-1]>key){
arr[j] = arr[j-1];
}
else{
break;
}
}
arr[j] = key;
}
}
}