java面试中常用的排序算法
转载自：http://blog.csdn.net/spy19881201/archive/2010/09/07/5867721.aspx







一、冒泡排序




view plaincopy to clipboardprint?
package sort.bubble;  
import java.util.Random;  
/** 
* 依次比较相邻的两个数，将小数放在前面，大数放在后面 
* 冒泡排序，具有稳定性 
* 时间复杂度为O（n^2） 
* 不及堆排序，快速排序O（nlogn，底数为2） 
* @author liangge 
* 
*/ 
public class Main {  
    public static void main(String[] args) {  
        Random ran = new Random();  
        int[] sort = new int[10];  
        for(int i = 0 ; i < 10 ; i++){  
            sort[i] = ran.nextInt(50);  
        }  
        System.out.print("排序前的数组为");  
        for(int i : sort){  
            System.out.print(i+" ");  
        }  
        buddleSort(sort);  
        System.out.println();  
        System.out.print("排序后的数组为");  
        for(int i : sort){  
            System.out.print(i+" ");  
        }  
    }  
      
    /** 
     * 冒泡排序 
     * @param sort 
     */ 
    private static void buddleSort(int[] sort){  
        for(int i=1;i<sort.length;i++){  
            for(int j=0;j<sort.length-i;j++){  
                if(sort[j]>sort[j+1]){  
                    int temp = sort[j+1];  
                    sort[j+1] = sort[j];  
                    sort[j] = temp;  
                }  
            }  
        }  
    }  
} 
package sort.bubble;
import java.util.Random;
/**
* 依次比较相邻的两个数，将小数放在前面，大数放在后面
* 冒泡排序，具有稳定性
* 时间复杂度为O（n^2）
* 不及堆排序，快速排序O（nlogn，底数为2）
* @author liangge
*
*/
public class Main {
public static void main(String[] args) {
  Random ran = new Random();
  int[] sort = new int[10];
  for(int i = 0 ; i < 10 ; i++){
   sort[i] = ran.nextInt(50);
  }
  System.out.print("排序前的数组为");
  for(int i : sort){
   System.out.print(i+" ");
  }
  buddleSort(sort);
  System.out.println();
  System.out.print("排序后的数组为");
  for(int i : sort){
   System.out.print(i+" ");
  }
}

/**
  * 冒泡排序
  * @param sort
  */
private static void buddleSort(int[] sort){
  for(int i=1;i<sort.length;i++){
   for(int j=0;j<sort.length-i;j++){
    if(sort[j]>sort[j+1]){
     int temp = sort[j+1];
     sort[j+1] = sort[j];
     sort[j] = temp;
    }
   }
  }
}
}


二、选择排序

view plaincopy to clipboardprint?
package sort.select;  
import java.util.Random;  
/** 
* 选择排序 
* 每一趟从待排序的数据元素中选出最小（或最大）的一个元素， 
* 顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。  
* 选择排序是不稳定的排序方法。 
* @author liangge 
*  
*/ 
public class Main {  
    public static void main(String[] args) {  
        Random ran = new Random();  
        int[] sort = new int[10];  
        for (int i = 0; i < 10; i++) {  
            sort[i] = ran.nextInt(50);  
        }  
        System.out.print("排序前的数组为");  
        for (int i : sort) {  
            System.out.print(i + " ");  
        }  
        selectSort(sort);  
        System.out.println();  
        System.out.print("排序后的数组为");  
        for (int i : sort) {  
            System.out.print(i + " ");  
        }  
    }  
    /** 
     * 选择排序 
     * @param sort 
     */ 
    private static void selectSort(int[] sort){  
        for(int i =0;i<sort.length-1;i++){  
            for(int j = i+1;j<sort.length;j++){  
                if(sort[j]<sort[i]){  
                    int temp = sort[j];  
                    sort[j] = sort[i];  
                    sort[i] = temp;  
                }  
            }  
        }  
    }  
} 
package sort.select;
import java.util.Random;
/**
* 选择排序
* 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，
* 顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
* 选择排序是不稳定的排序方法。
* @author liangge
*
*/
public class Main {
public static void main(String[] args) {
  Random ran = new Random();
  int[] sort = new int[10];
  for (int i = 0; i < 10; i++) {
   sort[i] = ran.nextInt(50);
  }
  System.out.print("排序前的数组为");
  for (int i : sort) {
   System.out.print(i + " ");
  }
  selectSort(sort);
  System.out.println();
  System.out.print("排序后的数组为");
  for (int i : sort) {
   System.out.print(i + " ");
  }
}
/**
  * 选择排序
  * @param sort
  */
private static void selectSort(int[] sort){
  for(int i =0;i<sort.length-1;i++){
   for(int j = i+1;j<sort.length;j++){
    if(sort[j]<sort[i]){
     int temp = sort[j];
     sort[j] = sort[i];
     sort[i] = temp;
    }
   }
  }
}
}


三、快速排序

view plaincopy to clipboardprint?
package sort.quick;  
/** 
* 快速排序 通过一趟排序将要排序的数据分割成独立的两部分， 其中一部分的所有数据都比另外一部分的所有数据都要小， 
* 然后再按此方法对这两部分数据分别进行快速排序， 整个排序过程可以递归进行，以此达到整个数据变成有序序列。 
* @author liangge 
*  
*/ 
public class Main {  
    public static void main(String[] args) {  
        int[] sort = { 54, 31, 89, 33, 66, 12, 68, 20 };  
        System.out.print("排序前的数组为：");  
        for (int data : sort) {  
            System.out.print(data + " ");  
        }  
        System.out.println();  
        quickSort(sort, 0, sort.length - 1);  
        System.out.print("排序后的数组为：");  
        for (int data : sort) {  
            System.out.print(data + " ");  
        }  
    }  
    /** 
     * 快速排序 
     * @param sort 要排序的数组 
     * @param start 排序的开始座标 
     * @param end 排序的结束座标 
     */ 
    public static void quickSort(int[] sort, int start, int end) {  
        // 设置关键数据key为要排序数组的第一个元素，  
        // 即第一趟排序后，key右边的数全部比key大，key左边的数全部比key小  
        int key = sort[start];  
        // 设置数组左边的索引，往右移动判断比key大的数  
        int i = start;  
        // 设置数组右边的索引，往左移动判断比key小的数  
        int j = end;  
        // 如果左边索引比右边索引小，则还有数据没有排序  
        while (i < j) {  
            while (sort[j] > key && j > start) {  
                j--;  
            }  
            while (sort[i] < key && i < end) {  
                i++;  
            }  
            if (i < j) {  
                int temp = sort[i];  
                sort[i] = sort[j];  
                sort[j] = temp;  
            }  
        }  
        // 如果左边索引比右边索引要大，说明第一次排序完成，将sort[j]与key对换，  
        // 即保持了key左边的数比key小，key右边的数比key大  
        if (i > j) {  
            int temp = sort[j];  
            sort[j] = sort[start];  
            sort[start] = temp;  
        }  
        //递归调用  
        if (j > start && j < end) {  
            quickSort(sort, start, j - 1);  
            quickSort(sort, j + 1, end);  
        }  
    }  
} 
package sort.quick;
/**
* 快速排序 通过一趟排序将要排序的数据分割成独立的两部分， 其中一部分的所有数据都比另外一部分的所有数据都要小，
* 然后再按此方法对这两部分数据分别进行快速排序， 整个排序过程可以递归进行，以此达到整个数据变成有序序列。
* @author liangge
*
*/
public class Main {
public static void main(String[] args) {
  int[] sort = { 54, 31, 89, 33, 66, 12, 68, 20 };
  System.out.print("排序前的数组为：");
  for (int data : sort) {
   System.out.print(data + " ");
  }
  System.out.println();
  quickSort(sort, 0, sort.length - 1);
  System.out.print("排序后的数组为：");
  for (int data : sort) {
   System.out.print(data + " ");
  }
}
/**
  * 快速排序
  * @param sort 要排序的数组
  * @param start 排序的开始座标
  * @param end 排序的结束座标
  */
public static void quickSort(int[] sort, int start, int end) {
  // 设置关键数据key为要排序数组的第一个元素，
  // 即第一趟排序后，key右边的数全部比key大，key左边的数全部比key小
  int key = sort[start];
  // 设置数组左边的索引，往右移动判断比key大的数
  int i = start;
  // 设置数组右边的索引，往左移动判断比key小的数
  int j = end;
  // 如果左边索引比右边索引小，则还有数据没有排序
  while (i < j) {
   while (sort[j] > key && j > start) {
    j--;
   }
   while (sort[i] < key && i < end) {
    i++;
   }
   if (i < j) {
    int temp = sort[i];
    sort[i] = sort[j];
    sort[j] = temp;
   }
  }
  // 如果左边索引比右边索引要大，说明第一次排序完成，将sort[j]与key对换，
  // 即保持了key左边的数比key小，key右边的数比key大
  if (i > j) {
   int temp = sort[j];
   sort[j] = sort[start];
   sort[start] = temp;
  }
  //递归调用
  if (j > start && j < end) {
   quickSort(sort, start, j - 1);
   quickSort(sort, j + 1, end);
  }
}
}


view plaincopy to clipboardprint?
/** 
    * 快速排序 
    *  
    * @param a 
    * @param low 
    * @param high 
    *            voidTest 
    */ 
   public static void kuaisuSort(int[] a, int low, int high)  
   {  
       if (low >= high)  
       {  
           return;  
       }  
       if ((high - low) == 1)  
       {  
           if (a[low] > a[high])  
           {  
               swap(a, low, high);  
               return;  
           }  
       }  
       int key = a[low];  
       int left = low + 1;  
       int right = high;  
       while (left < right)  
       {  
           while (left < right && left <= high)// 左边向右  
           {  
               if (a[left] >= key)  
               {  
                   break;  
               }  
               left++;  
           }  
           while (right >= left && right > low)  
           {  
               if (a[right] <= key)  
               {  
                   break;  
               }  
               right--;  
           }  
           if (left < right)  
           {  
               swap(a, left, right);  
           }  
       }  
       swap(a, low, right);  
       kuaisuSort(a, low, right);  
       kuaisuSort(a, right + 1, high);  
   } 
/**
     * 快速排序
     *
     * @param a
     * @param low
     * @param high
     *            voidTest
     */
    public static void kuaisuSort(int[] a, int low, int high)
    {
        if (low >= high)
        {
            return;
        }
        if ((high - low) == 1)
        {
            if (a[low] > a[high])
            {
                swap(a, low, high);
                return;
            }
        }
        int key = a[low];
        int left = low + 1;
        int right = high;
        while (left < right)
        {
            while (left < right && left <= high)// 左边向右
            {
                if (a[left] >= key)
                {
                    break;
                }
                left++;
            }
            while (right >= left && right > low)
            {
                if (a[right] <= key)
                {
                    break;
                }
                right--;
            }
            if (left < right)
            {
                swap(a, left, right);
            }
        }
        swap(a, low, right);
        kuaisuSort(a, low, right);
        kuaisuSort(a, right + 1, high);
    }

四、插入排序

view plaincopy to clipboardprint?
package sort.insert;  
/** 
* 直接插入排序 
* 将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据 
* 算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。 
*/ 
import java.util.Random;  
public class DirectMain {  
    public static void main(String[] args) {  
        Random ran = new Random();  
        int[] sort = new int[10];  
        for (int i = 0; i < 10; i++) {  
            sort[i] = ran.nextInt(50);  
        }  
        System.out.print("排序前的数组为");  
        for (int i : sort) {  
            System.out.print(i + " ");  
        }  
        directInsertSort(sort);  
        System.out.println();  
        System.out.print("排序后的数组为");  
        for (int i : sort) {  
            System.out.print(i + " ");  
        }  
    }  
    /** 
     * 直接插入排序 
     *  
     * @param sort 
     */ 
    private static void directInsertSort(int[] sort) {  
        for (int i = 1; i < sort.length; i++) {  
            int index = i - 1;  
            int temp = sort[i];  
            while (index >= 0 && sort[index] > temp) {  
                sort[index + 1] = sort[index];  
                index--;  
            }  
            sort[index + 1] = temp;  
        }  
    }  
} 
package sort.insert;
/**
* 直接插入排序
* 将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据
* 算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。
*/
import java.util.Random;
public class DirectMain {
public static void main(String[] args) {
  Random ran = new Random();
  int[] sort = new int[10];
  for (int i = 0; i < 10; i++) {
   sort[i] = ran.nextInt(50);
  }
  System.out.print("排序前的数组为");
  for (int i : sort) {
   System.out.print(i + " ");
  }
  directInsertSort(sort);
  System.out.println();
  System.out.print("排序后的数组为");
  for (int i : sort) {
   System.out.print(i + " ");
  }
}
/**
  * 直接插入排序
  *
  * @param sort
  */
private static void directInsertSort(int[] sort) {
  for (int i = 1; i < sort.length; i++) {
   int index = i - 1;
   int temp = sort[i];
   while (index >= 0 && sort[index] > temp) {
    sort[index + 1] = sort[index];
    index--;
   }
   sort[index + 1] = temp;
  }
}
}


顺便添加一份，差不多的

view plaincopy to clipboardprint?
public static void charuSort(int[] a)  
    {  
        int len = a.length;  
        for (int i = 1; i < len; i++)  
        {  
            int j;  
            int temp = a[i];  
            for (j = i; j > 0; j--)//遍历i之前的数字  
            {  
                //如果之前的数字大于后面的数字，则把大的值赋到后面  
                if (a[j - 1] > temp)  
                {  
                    a[j] = a[j - 1];  
                } else 
                {  
                    break;  
                }  
            }  
            a[j] = temp;  
        }  
    } 
public static void charuSort(int[] a)
    {
        int len = a.length;
        for (int i = 1; i < len; i++)
        {
            int j;
            int temp = a[i];
            for (j = i; j > 0; j--)//遍历i之前的数字
            {
                //如果之前的数字大于后面的数字，则把大的值赋到后面
                if (a[j - 1] > temp)
                {
                    a[j] = a[j - 1];
                } else
                {
                    break;
                }
            }
            a[j] = temp;
        }
    }

把上面整合起来的一份写法：

view plaincopy to clipboardprint?
/** 
* 插入排序: 
*  
*/ 
public class InsertSort {  
    public void sort(int[] data) {  
        for (int i = 1; i < data.length; i++) {  
            for (int j = i; (j > 0) && (data[j] < data[j - 1]); j--) {  
                swap(data, j, j - 1);  
            }  
        }  
    }  
      
    private void swap(int[] data, int i, int j) {  
        int temp = data[i];  
        data[i] = data[j];  
        data[j] = temp;  
    }  
} 
/**
* 插入排序:
*
*/
public class InsertSort {
public void sort(int[] data) {
  for (int i = 1; i < data.length; i++) {
   for (int j = i; (j > 0) && (data[j] < data[j - 1]); j--) {
    swap(data, j, j - 1);
   }
  }
}

private void swap(int[] data, int i, int j) {
  int temp = data[i];
  data[i] = data[j];
  data[j] = temp;
}
}

五、顺便贴个二分搜索法

view plaincopy to clipboardprint?
package search.binary;  
public class Main {  
    public static void main(String[] args) {  
        int[] sort = {1,2,3,4,5,6,7,8,9,10};  
        int mask = binarySearch(sort,6);  
        System.out.println(mask);  
          
    }  
      
      
    /** 
     * 二分搜索法，返回座标，不存在返回-1 
     * @param sort 
     * @return 
     */ 
    private static int binarySearch(int[] sort,int data){  
        if(data<sort[0] || data>sort[sort.length-1]){  
            return -1;  
        }  
        int begin = 0;  
        int end = sort.length;  
        int mid = (begin+end)/2;  
        while(begin <= end){  
            mid = (begin+end)/2;  
            if(data > sort[mid]){  
                begin = mid + 1;  
            }else if(data < sort[mid]){  
                end = mid - 1;  
            }else{  
                return mid;  
            }  
        }  
        return -1;  
          
    }  
} 
package search.binary;
public class Main {
public static void main(String[] args) {
  int[] sort = {1,2,3,4,5,6,7,8,9,10};
  int mask = binarySearch(sort,6);
  System.out.println(mask);
 
}


/**
  * 二分搜索法，返回座标，不存在返回-1
  * @param sort
  * @return
  */
private static int binarySearch(int[] sort,int data){
  if(data<sort[0] || data>sort[sort.length-1]){
   return -1;
  }
  int begin = 0;
  int end = sort.length;
  int mid = (begin+end)/2;
  while(begin <= end){
   mid = (begin+end)/2;
   if(data > sort[mid]){
    begin = mid + 1;
   }else if(data < sort[mid]){
    end = mid - 1;
   }else{
    return mid;
   }
  }
  return -1;
 
}
}