Java 常用排序算法实现--快速排序 插入排序 选择 冒泡

publicclassArrayOperation{

//二分查找算法

publicstaticintbranchSearch(int[]array,intsearchNum){

if(array==null)

thrownewNullPointerException("NullReferrence");

if(array.length==0)

thrownewIllegalArgumentException("ArrayLengthisZero");

intlow=0,high=array.length;

intmiddle=(high+low)/2;

intindex=-1;

if(searchNum<array[0]||searchNum>array[array.length-1])

returnindex;

while(middle>=0){

if(array[middle]==searchNum){

index=middle;

break;

}

if(searchNum>array[middle]){

low=middle;

}else{

high=middle;

}

middle=(low+high)/2;

}

returnindex;

}

//快速排序

publicstaticvoidquickSort(inta[],intleft,intright){

inti,j,temp;

i=left;

j=right;

if(left>right)

return;

temp=a[left];

while(i!=j)/*找到最终位置*/

{

while(a[j]>=temp&&j>i)

j--;

if(j>i)

a[i++]=a[j];

while(a[i]<=temp&&j>i)

i++;

if(j>i)

a[j--]=a[i];

}

a[i]=temp;

quickSort(a,left,i-1);/*递归左边*/

quickSort(a,i+1,right);/*递归右边*/

}

//插入排序

//特点：用temp保存将要排序的临时值，然后把大的值插入到这个位置。

publicstaticint[]insert_Sort(int[]array){

inti,j,temp;

for(i=1;i<array.length;i++){

for(j=i,temp=array[i];j>0&&temp<array[j-1];j--)

array[j]=array[j-1];

array[j]=temp;

}

returnarray;

}

//冒泡排序

//特点：从第一个元素开始，如果需要交换，就一直冒泡到底，如果不需要交换，就从下一个元素开始比较

publicvoidbubble_Sort(int[]array,intsize){

inti,j,temp;

for(i=size-1;i>1;i--)

for(j=0;j<i;j++)

if(array[j]>array[j+1]){

temp=array[j+1];

array[j+1]=array[j];

array[j]=temp;

}

}

//交换排序

//特点：始终是第一个元素与其他元素一一比较，交互后，继续用第一个元素与后面元素一一比较，重复下去。

publicint[]change_Sort(int[]array,intsize){

inti,j,temp;

for(i=0;i<size;i++)

for(j=i+1;j<size;j++)

if(array[i]>array[j]){

temp=array[j];

array[j]=array[i];

array[i]=temp;

}

returnarray;

}

//选择排序一（便于区分：咱就叫：选择最小值排序法）

//特点：分有序区（第一个元素）和无序区（除第一元素外的元素），从无序区找出最小的元素移动到有序区

publicvoidSelectSort(int[]array){

inti,j,k;//分别为有序区，无序区，无序区最小元素指针

for(i=0;i<array.length;i++){

k=i;

for(j=i+1;j<array.length;j++){

if(array[j]<array[k])

k=j;

}

if(k!=i)//若发现最小元素，则移动到有序区

{

inttemp=array[k];

array[k]=array[i];

array[i]=array[temp];

}

}

}

//选择排序二

publicint[]select_Sort(int[]array,intsize){

inti,j,temp,pos;

for(i=0;i<size;i++){

for(j=i+1,temp=array[i],pos=i;j<size;j++)

if(temp>array[j]){

temp=array[j];

pos=j;

}

array[pos]=array[i];

array[i]=temp;

}

returnarray;

}

//希尔排序

//属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序

//排序过程：先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；

//然后取d2<d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止

publicstaticvoidShellSort(int[]array){

intlength=array.length;

for(inth=length/2;h>0;h=h/2){

//hereisinsertsort

for(inti=h;i<length;i++){

inttemp=array[i];

if(temp<array[i-h]){

for(intj=0;j<i;j+=h){

if(temp<array[j]){

temp=array[j];

array[j]=array[i];

array[i]=temp;

}

}

}

}

}

}

}