|
冒泡：
public void bubbleSort(int[] srr, int len){
for(int i=0;i<len-1;i++){
for(int j=0;j<len-1-i;j++){
if(arr[j]>arr[j+1]){
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=arr[j];
}
}
}
}
选择排序：
public void selectSort(int[] arr){
int len=arr.length;
for(int i=0;i<n;i++){
int min=i;
for(int j=i+1;j<len;j++){
if(arr[min]>arr[j]){
min=j;
}
}
if(min!=i){
int temp=arr[i];
arr[i]=arr[min];
arr[min]=temp;
}
}
}
插入：
public void insertSort(int[] arr){
for(int bound=1;bound<arr.length;bound++){
int v=arr[bound];
int curr=bound-1;
for(;curr>=0;curr--){
if(arr[curr]>v){
arr[curr+1]=arr[curr];
}else{
break;
}
}
arr[curr+1]=v;
}
}
public void insertsort(int[] arr){
int len=arr.length;
for(int bound=1;bound<len;bound++){
int value=arr[bound];
int curr=bound-1;
for(;curr>=0;curr--){
if(arr[curr]>value){
arr[curr+1]=arr[curr];
}else{
break;
}
}
arr[curr]=value;
}
}
希尔排序
public void shellSort(int[] arr){
int gap=arr.length/2;
while(gap>1){
shellSortGap(arr,gap);
gap/=2;
}
shellSortGap(arr,1);
}
public void shellSortGap(int[] arr,int gap){
for(int bound=gap;bound<arr.length;bound++){
int val=arr[bound];
int cur=bound-gap;
for(;cur>=0;cur--){
if(arr[cur]>val){
arr[cur+gap]=arr[cur];
}else{
break;
}
}
arr[cur+gap]=value;
}
}
归并：
public void mergeSort(int[] arr){
mergeSortHelper(arr,0,arr.length);
}
public void mergeSortHelper(int[] arr,int low,int high){
if(high-low<=1){
return;
}
int mid=(low+high)/2;
mergeSortHelper(arr,0,mid);
mergeSortHelper(arr,mid,high);
merge(arr,low,mid,high);
}
public void merge(int[] arr,int low,int mid,int high){
int[] output=new int[high-low];
int outputindex=0;
int cur1=low;
int cur2=mid;
while(cur1<mid && vur2<high){
if(arr[cur1]<=arr[cur2]){
output[outputindex]=arr[cur1];
outputindex++;
cur1++;
}else{
output[outputindex]=arr[cur2];
outputindex++;
cur2++;
}
}
while(cur1<mid){
output[outputindex]=arr[cur1];
outputindex++;
cur1++;
}
while(cur2<high){
output[outputindex]=arr[cur2];
outputindex++;
cur2++;
}
for(int i=0;i<high-low;i++){
arr[i+low]=output[i];
}
}
//非递归
public void mergeByLoop(int[] arr){
int len=arr.length;
for(int gap=1;gap<len;gap*=2){
for(int i=0;i<len;i+=2*gap){
int low=i;
int mid=low+gap;
int high=i+2*gap;
if(mid>len){
mid=len;
}
if(high>len){
high=len;
}
merge(arr,low,mid,high);
}
}
}
快速排序：
public void quickSort(int[] arr){
int len=arr.length;
quickSortHelper(arr,0,len-1);
}
public void quickSortHelper(int[] arr,int left,int right){
if(left>=right){
return;
}
int middle=getMiddle(arr,left,right);
quickSortHelper(arr,left,middle-1);
quickSortHelper(arr,middle+1,high);
}
public void getMiddle(int[] arr,int left,int right){
int temp=arr[left];
while(left<right){
while(left<right &&arr[right]>temp){
right--;
}
arr[left]=arr[right];
while(left<right &&arr[left]<temp){
left++;
}
arr[right]=arr[left];
}
arr[left]=temp;
return left;
}
堆排序：
public void heapSort(int[] arr){
createHeap(arr);
for(int i=0;i<arr.length-1;i++){
swap(arr,0,arr.length-1-i);
shiftDown(arr,arr.length-1-i,0);
}
}
public void createHeap(int[] arr){
for(int i=(arr.length-1-1)/2;i>0;i--){
shiftDown(arr,arr.length,i);
}
}
public void shiftDown(int[] arr, int heaplength,int index){
int parent=index;
int child=index*2+1;
while(child < heaplength){
if(child+1<heaplength&&arr[child+1]>arr[child]){
child=child+1;
}
if(arr[child+1]>arr[parrent]){
swap(arr,child,parent);
}
parent=child;
child=2*parent+1;
}
}
?
|