排序算法:冒泡排序、插入排序、希尔排序 | 玄数

2014-11-04

1、冒泡排序 Bubble Sort:

  • 从列表的第一个元素开始,与相邻的元素比较,若前者>后者,便交换两个元素。直到把最大的元素排到了最末,完成第一次排列
  • 重复第一步,但比较的次数会减一,直到把第二大的元素排到了倒数第二,完成第二次排列
  • 重复第一步,比较次数依次减一,直到把最小的元素排在首位

 

java程序如下:

import java.util.Arrays;

public class SortOrder {

  int[] array = {9, 7, 5, 3, 1};
  int c = 0;
  int m = 0;

  private void bubbleSort(){

    for(int i = array.length – 1; i > 0; i–){

      for(int j = 0; j < i; j++){
        c++;
        if(array[j] > array[j+1]){
          int temp = array[j];
          array[j] = array[j+1];
          array[j+1] = temp;
          m++;
          System.out.println(Arrays.toString(array));
        }
      }
    }
  }

  public static void main(String[] args) {

    SortOrder sort = new SortOrder();
    sort.bubbleSort();

    System.out.println(“这个算法一共比较了” + sort.c + “次”);
    System.out.println(“移动了” + sort.m + “次”);
  }

}

冒泡排序 Bubble Sort

 

2、 插入排序 Insertion Sort:

  • 把数组分为有序区{a1}和无序区{a2, a3 … an}
  • 从i=2,也就是a2开始,把ai插入到有序区中。有序区元素的个数逐步加1,无序区元素的个数逐步减1。插入位置:从后往前逐个比较,大的往后移,直到把这一轮比较中的数最小的放在最前面

a2与a1相比,若a1<a2,a2插入到a1的后面,此时的有序区和无序区为{a1, a2},{a3, a4 … an};若a1>a2,不是交换两数的位置,而是先建立一个局部变量temp把小的a2暂时保存起来,把大的复制到后边,此时的暂时有序区为{a1, a1},再把第一个a1去掉,替换为temp

 

private void injectSort(){

  for(int i = 1; i < array.length; i++){

    int temp = array[i];
    int j = i – 1;
    c++;

    while(array[j] > temp){

      array[j + 1] = array[j];
      j–;
      m++;
      System.out.println(Arrays.toString(array));
      if(j == -1){
        break;
      }
    }
    array[j+1] = temp;
    System.out.println(Arrays.toString(array));
  }
}

main中的替换为 sort.injectSort();
插入排序 Insertion Sort

 

3、希尔排序 Shell Sort:

private void shellSort(){

  int d = array.length;

  while(true){
    d = d/2;

    for (int x = 0; x < d; x++) {
      c++;
      for (int i = x + d; i < array.length; i = i + d) {
        int temp = array[i];
        int j;
        for (j = i – d; j >= 0 && array[j] > temp; j = j – d) {
          array[j + d] = array[j];
          m++;
          System.out.println(Arrays.toString(array));
        }
        array[j + d] = temp;
        System.out.println(Arrays.toString(array));
      }
    }
    if (d == 1) {
      break;
    }
  }
}

main中的替换为 sort.shellSort();
希尔排序 Shell Sort

排序算法:冒泡排序、插入排序、希尔排序