记录几个常用排序算法(冒泡排序、快速排序、直接插入排序、选择排序)的思想 和 源码
1.jpg

冒泡排序

冒泡排序 (Bubble Sort)，又被称为气泡排序或泡沫排序
思想：它会遍历若干次要排序的数列，每次遍历时，它都会从前往后依次的比较相邻两个数的大小；如果前者比后者大，则交换它们的位置。这样，一次遍历之后，最大的元素就在数列的末尾！ 采用相同的方法再次遍历时，第二大的元素就被排列在最大元素之前。重复此操作，直到整个数列都有序为止！

时间复杂度

冒泡排序的时间复杂度是 O(N2)
假设被排序的数列中有 N 个数。遍历一趟的时间复杂度是 O(N)，需要遍历多少次呢？N-1 次！因此，冒泡排序的时间复杂度是 O(N2)

Java 实现冒泡排序

  1. // 冒泡排序
  2. public class BubbleSort {
  4.     public static void bubbleSort(int[] a, int n){
  5.         int i,j;
  6.         int flag;
  8.         for(i = n-1; i > 0; i--){
  9.             flag = 0;
  10.             for (j = 0; j < i; j++){
  11.                 if(a[j] > a[j+1]){
  12.                     int tmp = a[j];
  13.                     a[j] = a[j+1];
  14.                     a[j+1] = tmp;
  15.                     flag = 1;
  16.                 }
  17.             }
  18.             if (flag==0)
  19.                 break;
  20.         }
  22.     }
  24.     public static void main(String[] args) {
  25.         int i;
  26.         int[] a = {20,40,30,10,60,50};
  28.         System.out.printf("before sort:");
  29.         for (i=0; i<a.length; i++)
  30.             System.out.printf("%d ", a[i]);
  31.         System.out.printf("\n");
  33.         bubbleSort(a, a.length);
  35.         System.out.printf("after  sort:");
  36.         for (i=0; i<a.length; i++)
  37.             System.out.printf("%d ", a[i]);
  38.     }
  39. }

快速排序

快速排序 (Quick Sort)使用分治法策略
思想：选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分；其中一部分的所有数据都比另外一部分的所有数据都要小。然后，再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
快速排序流程：

  1. 从数列中挑出一个基准值
  2. 将所有比基准值小的摆放在基准前面，所有比基准值大的摆在基准的后面(相同的数可以到任一边)；在这个分区退出之后，该基准就处于数列的中间位置
  3. 递归地把”基准值前面的子数列”和”基准值后面的子数列”进行排序

下面以数列 a={30,40,60,10,20,50}为例，演示它的快速排序过程
2.jpg

时间复杂度

快速排序的时间复杂度在最坏情况下是 O(N2)，平均的时间复杂度是 O(N*lgN)
这句话很好理解：假设被排序的数列中有 N 个数。遍历一次的时间复杂度是 O(N)，需要遍历多少次呢？至少 lg(N+1)次，最多 N 次

Java 实现快速排序

  1. // 快速排序
  2. public class QuickSort {
  3.     public static void quickSort(int[] a, int l, int r){
  4.         if(l<r){
  5.             int i,j,x;
  6.             i = l;j = r;
  7.             x = a[i];
  8.             while (i<j){
  9.                 while (i<j && x<a[j])
  10.                     j--;
  11.                 if(i<j)
  12.                     a[i++] = a[j];
  13.                 while (i<j && x>a[i])
  14.                     i++;
  15.                 if (i<j)
  16.                     a[j--] = a[i];
  17.             }
  18.             a[i] = x;
  19.             quickSort(a,l,i-1);
  20.             quickSort(a,j+1,r);
  22.         }
  23.     }
  25.     public static void main(String[] args) {
  26.         int i;
  27.         int a[] = {30,40,60,10,20,50};
  29.         System.out.printf("before sort:");
  30.         for (i=0; i<a.length; i++)
  31.             System.out.printf("%d ", a[i]);
  32.         System.out.printf("\n");
  34.         quickSort(a, 0, a.length-1);
  35.         System.out.printf("after  sort:");
  36.         for (i=0; i<a.length; i++)
  37.             System.out.printf("%d ", a[i]);
  38.     }
  39. }

直接插入排序

思想：把 n 个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含 1 个元素，无序表中包含有 n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复 n-1 次可完成排序过程
假设 {20,30,40,10,60,50} 中的前3个数已经排列过，是有序的了；接下来对10进行排列，如下：
3.jpg
图中将数列分为有序区和无序区。我们需要做的工作只有两个：

  1. 取出无序区中的第1个数，并找出它在有序区对应的位置

  2. 将无序区的数据插入到有序区；若有必要的话，则对有序区中的相关数据进行移位

    Java 实现直接插入排序

    1. // 直接插入排序
    2. public class InsertSort {
    3.  public static void insertSort(int[]a,int n){
    4.      int i,j,k;
    5.      for (i = 1;i < n;i++){
    6.          // a[i]是从无序列表中取出来的值，要找到放它的位置
    7.          for (j = i-1;j>=0;j--){
    8.              if (a[j] < a[i])
    9.                  break;
    10.          }
    12.          if(j != i-1){
    13.              int tmp = a[i];
    14.              // 将有序列表中往后挪，然后把a[i]插入列表中
    15.              for(k = i-1;k > j;k--){
    16.                  a[k+1] = a[k];
    17.              }
    18.              a[k+1] = tmp;
    19.          }
    20.      }
    21.  }
    23.  public static void main(String[] args) {
    24.      int i;
    25.      int[] a = {20,40,30,10,60,50};
    27.      System.out.printf("before sort:");
    28.      for (i=0; i<a.length; i++)
    29.          System.out.printf("%d ", a[i]);
    30.      System.out.printf("\n");
    32.      insertSort(a, a.length);
    33.      System.out.printf("after  sort:");
    34.      for (i=0; i<a.length; i++)
    35.          System.out.printf("%d ", a[i]);
    36.  }
    37. }

    选择排序

    选择排序 (Selection sort)是一种简单直观的排序算法。
    思想：首先在未排序的数列中找到最小(or最大)元素，然后将其存放到数列的起始位置；接着，再从剩余未排序的元素中继续寻找最小(or最大)元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕
    选择排序的时间复杂度是 O(N2)

    Java 实现选择排序

    1. // 选择排序
    2. public class SelectSort {
    3.  public static void selectSort(int[] a,int n){
    4.      int i,j,min;
    5.      for (i=0;i<n;i++){
    6.          min = i;
    7.          for (j=i+1;j<n;j++){
    8.              if (a[min]>a[j])
    9.                  min = j;
    10.          }
    11.          if (i != min){
    12.              int tmp = a[min];
    13.              a[min] = a[i];
    14.              a[i] = tmp;
    15.          }
    17.      }
    18.  }
    20.  public static void main(String[] args) {
    21.      int i;
    22.      int[] a = {20,40,30,10,60,50};
    23.      System.out.printf("before sort:");
    24.      for (i=0; i<a.length; i++)
    25.          System.out.printf("%d ", a[i]);
    26.      System.out.printf("\n");
    28.      selectSort(a, a.length);
    29.      System.out.printf("after  sort:");
    30.      for (i=0; i<a.length; i++)
    31.          System.out.printf("%d ", a[i]);
    32.  }
    33. }