插入,冒泡,选择,快速排序,二分查找

插入,冒泡,选择,快速排序,二分查找

关键字: java

一. 直接插入排序

voidinsertSort(int[]a){
for(inti=1;i<a.length;i++){
if(a[i]<a[i-1]){
temp=a[i];//1
a[i]=a[i-1];//2

//继续和前面的进行比较
for(intj=i-2;j>=0;j--){
if(temp<a[j])
a[j+1]=a[j];//3
}
a[j+1]=temp;//4
}
}
}

void insertSort(int[] a){
      for(int i=1;i<a.length; i++){
           if (a[i]<a[i-1]){
               temp = a[i];  //1 
               a[i] = a[i-1]; //2

               // 继续和前面的进行比较
               for(int j=i-2; j>=0; j--){
                    if(temp < a[j])
                         a[j+1] =a[j];//3
               }
               a[j+1] = temp;//4
           }
      }
}

二.冒泡排序

冒泡排序，就是从最底那个开始往上比较，遇到比它小的就交换，相当于过五关看六将，不断地向前冲。接着循环第二个...

voidbubbleSort(int[]a){
//每个都进行冒泡(一个一个来)
for(inti=0;i<a.length;i++){

//和后面的每个都进行比较(过五关看六将)
for(intj=i;j<a.length-1;j++){
if(a[j]>a[j+1]){
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}

void bubbleSort(int[] a){ 
            //每个都进行冒泡(一个一个来) 
           for (int i=0; i<a.length; i++){ 
   
                   //和后面的每个都进行比较(过五关看六将) 
                    for (int j=i; j<a.length-1; j++){ 
                            if (a[j]>a[j+1]){ 
                                   temp = a[j]; 
                                    a[j] = a[j+1]; 
                                    a[j+1] = temp; 
                            } 
                    } 
            } 
    } 

三.选择排序
选择排序，就是选择最小的，然后置换，循环再找到最小的，再置换...

voidselectSort(int[]a){
for(inti=0;i<a.length;i++){
small=i;

//找出最小的
for(intj=i+1;j<a.lenth;j++){
if(a[small]>a[j]){
small=j;
}
}

//置换位置
if(i!=small){
temp=a[small];
a[small]=a[i];
a]i]=temp;
}
}
}

void selectSort(int[] a){ 
        for (int i=0; i<a.length; i++){ 
                small = i; 

                //找出最小的 
                 for (int j=i+1; j<a.lenth; j++){ 
                        if (a[small]>a[j]){ 
                                small = j; 
                        } 
                } 

                //置换位置 
                 if (i != small){ 
                        temp = a[small]; 
                        a[small] = a[i]; 
                        a]i] = temp; 
                } 
        } 
}

四.快速排序
快速排序的基本过程:
得到枢轴索引：compare首先从high位置向前搜索找到第一个小于compare值的索引，并置换(这时high索引位置上的值为compare 值)；然后从low位置往后搜索找到第一个大于compare值的索引，并与high索引上的值置换(这时low索引位置上的值为compare值)；重复这两步直到low=high为止。
得到枢轴索引后，则递归进行枢轴两边的队列的排序....

voidquickSort(int[]a,intlow,inthigh){
intp=get(a,low,high);
quickSort(a,low,p-1);
quickSort(a,p+1,high);
}

intget(int[]a,intlow,inthigh){
compare=a[low];

while(low<high){//无论如何置换,被置换的都包含compare的值
while(low<high&&a[high]>=compare)
high--;

//在low<high的情况下找到a[high]<compare并置换
temp=a[low];
a[low]=a[high];
a[high]=temp;

while(low<high&&a[low]<=compare)
low++;

//在low<high的情况下找到a[low]>compare并置换
temp=a[low];
a[low]=a[high];
a[high]=temp;
}
returnlow;//while(low==hight)停止循环,并返回枢轴位置
}

void quickSort(int[] a, int low, int high) { 
        int p = get(a, low, high); 
        quickSort(a, low, p-1); 
        quickSort(a, p+1, high); 
} 

int get(int[] a, int low, int high){ 
     compare = a[low]; 

     while(low < high){ //无论如何置换, 被置换的都包含compare的值
         while(low<high && a[high]>=compare)    
              high--; 

         //在 low<high 的情况下找到a[high]<compare并置换 
         temp = a[low];
         a[low] = a[high];
         a[high] = temp;

         while(low<high && a[low]<=compare) 
              low++; 

         //在 low<high 的情况下找到a[low]>compare并置换 
          temp = a[low]; 
              a[low] = a[high]; 
              a[high] = temp; 
     } 
     return low; //while(low==hight)停止循环, 并返回枢轴位置 
}

非递归的实现

voidQsort(int[]a){
intstack=newint[a.len];
inttop=-1;
inthigh=0,low=0;
stack[++top]=0;
stack[++top]=array.length-1;
while(top!=-1){
high=stack[top--];
low=stack[top--];
if(low<high){
intpos=get(a,low,high);
stack[++top]=low;
stack[++top]=pos-1;
stack[++top]=pos+1;
stack[++top]=high;
}
}
}

void Qsort(int[] a){
    int stack = new int[a.len];
    int top = -1;
  int high = 0, low = 0;
  stack[++top] = 0;
  stack[++top] = array.length-1;
  while(top != -1){
       high = stack[top--];
       low = stack[top--];
       if(low < high){
             int pos = get(a, low, high); 
             stack[++top] = low;
             stack[++top] = pos-1;
             stack[++top] = pos+1;
             stack[++top] = high;
       }
   }
}

五.二分查找
二分查找原理很容易懂，想象为二叉查找树就明白了。

intbinarySearch(int[]a,intvalue){
intlow=0;
inthigh=a.length-1;

while(low<=high){
mid=(low+high)/2;//**
if(a[mid]==value)
returnmid;
elseif(a[mid]>value)
high=mid-1;
else
low=mid+1;
}
return-1;
}

int binarySearch(int[] a, int value){ 
        int low = 0; 
        int high = a.length-1; 
         
        while(low <= high){ 
                mid = (low+high)/2; //**
                if (a[mid] == value) 
                        return mid; 
                else if (a[mid] > value) 
                        high = mid-1; 
                else 
                        low = mid +1; 
        } 
        return -1; 
}

** mid = (low + high) / 2; 有问题，当low + high大于int范围时就会溢出的。Sun的jdk里面的二分查找源码原先也有同样的问题。
解决的方法是mid = low/2 + high/2。这样用2先除一下，就不会溢出了。

http://binbin8497.javaeye.com/blog/489724