简单排序算法_JAVA_编程开发_程序员俱乐部

本人是个抄代码，以下不一定对（希望指出不对的地方帮助我学习）：
插入排序是这样实现的：
1、首先新建一个空列表，用于保存已排序的有序数列（我们称之为"有序列表"）。
2、从原数列中取出一个数，将其插入"有序列表"中，使其仍旧保持有序状态。
3、重复2号步骤，直至原数列为空。
插入排序的平均时间复杂度为平方级的，效率不高，但是容易实现。它借助了"逐步扩大成果"的思想，使有序列表的长度逐渐增加，直至其长度等于原列表的长度。
插入排序的基本思想是在遍历数组的过程中，假设在序号 i 之前的元素即 [0..i-1] 都已经排好序，本趟需要找到 i 对应的元素 x 的正确位置 k ，并且在寻找这个位置 k 的过程中逐个将比较过的元素往后移一位，为元素 x “腾位置”，最后将 k 对应的元素值赋为 x ，一般情况下，插入排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1)。（百度抄的）

class="java" name="code">
  /** 插入式排序 */
  public static void insertionSort(int[] ary){
    int i,j,k;
    for(i=1; i<ary.length; i++){
      k = ary[i];//取出
      //查找位置
      for(j=i-1; j>=0 && k<ary[j]; j--){
        ary[j+1]=ary[j];//向后移动元素
      }
      ary[j+1]=k;//插入
    }
  }

分析：
true                           j>=0 && k<ary[j]的值
1                              i的值
0                              j的值
[3, 3, 4, 9, 2, 5, 6]
[1, 3, 4, 9, 2, 5, 6]          循环后的数组
false
[1, 3, 4, 9, 2, 5, 6]
false
[1, 3, 4, 9, 2, 5, 6]
true
4
3
[1, 3, 4, 9, 9, 5, 6]
4
2
[1, 3, 4, 4, 9, 5, 6]
4
1
[1, 3, 3, 4, 9, 5, 6]
[1, 2, 3, 4, 9, 5, 6]
true
5
4
[1, 2, 3, 4, 9, 9, 6]
[1, 2, 3, 4, 5, 9, 6]
true
6
5
[1, 2, 3, 4, 5, 9, 9]
[1, 2, 3, 4, 5, 6, 9]
[1, 2, 3, 4, 5, 6, 9]

冒泡排序
冒泡排序是这样实现的：
1、从列表的第一个数字到倒数第二个数字，逐个检查：若某一位上的数字大于他的下一位，则将它与它的下一位交换。
2、重复1号步骤，直至再也不能交换。
冒泡排序的平均时间复杂度与插入排序相同，也是平方级的，但冒泡排序是原地排序的，也就是说它不需要额外的存储空间。（百度抄的）

  /** 冒泡排序 */
  public static void bubbleSort(int[] ary){
    for(int i=0; i<ary.length-1; i++){
      for(int j=0; j<ary.length-i-1; j++){
        if(ary[j]>ary[j+1]){
          int t=ary[j];ary[j]=ary[j+1];ary[j+1]=t;
        }
      }
    }
  }

分析：
j=0
ary[j]>ary[j+1]=true
[1, 3, 4, 9, 2, 5, 6]
j=1
ary[j]>ary[j+1]=false
j=2
ary[j]>ary[j+1]=false
j=3
ary[j]>ary[j+1]=true
[1, 3, 4, 2, 9, 5, 6]
j=4
ary[j]>ary[j+1]=true
[1, 3, 4, 2, 5, 9, 6]
j=5
ary[j]>ary[j+1]=true
[1, 3, 4, 2, 5, 6, 9]
[1, 3, 4, 2, 5, 6, 9]
j=0
ary[j]>ary[j+1]=false
j=1
ary[j]>ary[j+1]=false
j=2
ary[j]>ary[j+1]=true
[1, 3, 2, 4, 5, 6, 9]
j=3
ary[j]>ary[j+1]=false
j=4
ary[j]>ary[j+1]=false
[1, 3, 2, 4, 5, 6, 9]
j=0
ary[j]>ary[j+1]=false
j=1
ary[j]>ary[j+1]=true
[1, 2, 3, 4, 5, 6, 9]
j=2
ary[j]>ary[j+1]=false
j=3
ary[j]>ary[j+1]=false
[1, 2, 3, 4, 5, 6, 9]
j=0
ary[j]>ary[j+1]=false
j=1
ary[j]>ary[j+1]=false
j=2
ary[j]>ary[j+1]=false
[1, 2, 3, 4, 5, 6, 9]
j=0
ary[j]>ary[j+1]=false
j=1
ary[j]>ary[j+1]=false
[1, 2, 3, 4, 5, 6, 9]
j=0
ary[j]>ary[j+1]=false
[1, 2, 3, 4, 5, 6, 9]
[1, 2, 3, 4, 5, 6, 9]

选择排序
选择排序是这样实现的：
1、设数组内存放了n个待排数字，数组下标从1开始，到n结束。
2、初始化i=1
3、从数组的第i个元素开始到第n个元素，寻找最小的元素。
4、将上一步找到的最小元素和第i位元素交换。
5、i++,直到i=n－1算法结束，否则回到第3步
选择排序的平均时间复杂度也是O(n^2)的。（百度抄的）

  /** 选择排序: 每轮选择一个最小的放到前面 */
  public static void selectionSort(int[] ary){
    for(int i=0; i<ary.length-1; i++){
      for(int j=i+1; j<ary.length; j++){
        if(ary[i]>ary[j]){
          int t=ary[i];ary[i]=ary[j];ary[j]=t;
          System.out.println(Arrays.toString(ary));
        }
      }
    }
  }