冒泡排序

冒泡排序算法运行起来非常慢,但在概念上他是排序算法中最简单的,因为冒泡排序算法在刚开始研究排序技术时是一个非常好的算法。

排序思路

  • 首先确定,最大的放在最右边
  • 外层循环从右到左,逐步缩小范围
  • 内层循环从小到大,一直到外层最大下标
  • 每次比较大小,大的放在右边

核心代码

  /**
   * 冒泡核心算法
   */
  @Override
  public void sort() {
    int out, in;
    for (out = data.length - 1; out > 1; out--) {    // outer loop (backward)
      for (in = 0; in < out; in++) {                 // inner loop (forward)
        if (data[in] > data[in + 1]) {               // out of order ?
          swap(in, in + 1);                          // swap them
        }
      }
    }
  }

一般来说,数组中有N个数据项,则第一趟排序中有N-1次比较,第二趟中有N-2次,如此类推。这种序列的求和公式如下: (N-1)+(N-2)+(N-3)+...+1=N*(N-1)/2,忽略常数1,约等价于 N*N/2,所以,算法做了约 N*N/2 次比较。 因为数据是随机的,所以左边数据大于右边数据的概率大概是1/2,也就是说只有一半的数据需要交换,那么交换的次数 就是比较次数的1/2,也就是 N*N/4(不过在最坏的情况下,即初始数据逆序时,每次比较都需要交换)。 交换和比较次数都和 N*N 成正比,由于常数不算在大O表示法中,可以忽略2和4,并且认为冒泡排序运行需要 O(N*N/2) 时间级别。

选择排序

选择排序的比较次数和冒泡排序一样,但是交换次数会减少很多,每次遍历最多只交换一次即可。

排序思路

  • 首先确定,最小的放在最左边
  • 外层循环从左到右,逐步缩小范围
  • 内层循环从外层最小下标,一直到最后
  • 比较大小,记住最小值下标,比较完毕之后交换外层和最小值

核心代码

  /**
   * 选择排序核心算法
   */
  @Override
  public void sort() {
    int min, out, in;
    for (out = 0; out < data.length - 1; out++) {        // outer loop
      min = out;                                         // minimum
      for (in = out + 1; in < data.length; in++) {       // inner loop
        if (data[in] < data[min]) {                      // if min greater
          min = in;                                      // we have a new min
        }
      }
      swap(out, min);                                    // swap them
    }
  }

插入排序

排序思路

  • 外层for循环中,out变量从1开始向右移动,它标记了未排序部分的最左端的数据
  • 内层的while循环中,in变量从out变量开始,向左移动,直到temp变量小于in所指的数组数据项,或者它已经不能再往左移动为止
  • while循环的每一趟都向右移动了一个已排序的数据项

核心代码

  /**
   * 选择排序核心算法
   */
  @Override
  public void sort() {
    int out, in;
    for (out = 1; out < data.length; out++) {   // out is dividing line
      int temp = data[out];                     // remove marked item
      in = out;                                 // start shifts at out
      while (in > 0 && data[in - 1] >= temp) {  // until one is smaller
        data[in] = data[in - 1];                // shift item right
        --in;                                   // go left one position
      }
      data[in] = temp;                          // insert marked item
    }
  }

参考资料