图解数据结构——排序(一)

 排序 (Sorting) 是计算机程序设计中的一种重要操作，它的功能是将一个数据元素(或记录）的任意序列，重新排列成一个关键字有序(升序或者降序)的序列.

• 稳定性

• 内部排序: 数据在内存中进行排序.
• 外部排序: 数据在磁盘中进行排序.
  

中国计算机学校排名:

插入排序是一种最简单直观的排序算法，它的基本思想是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入.

 public static void insertSort(int arr[]) {
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i-1;
            for (; j >= 0; j--) {
                if(arr[j] > tmp) {
                    arr[j+1] = arr[j];
                }else {
                   // arr[j+1] = tmp;
                    break;
                }
            }
            arr[j+1] = tmp;
        }
    }

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本.该方法因 D.L.Shell 于 1959 年提出而得名.

public static void shell(int arr[],int gap) {
        for (int i = gap; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i-gap;
            for (; j >= 0; j-=gap) {
                if(arr[j] > tmp) {
                    arr[j+gap] = arr[j];

                }else {
                    // arr[j+1] = tmp;
                    break;
                }
            }
            arr[j+gap] = tmp;
        }
    }
    public static void shellSort(int arr[]) {
        int gap = arr.length;
        while (gap > 1) {
            shell(arr,gap);
            gap /= 2;
        }
        shell(arr,1);
    }

基本思想：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的开始的位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。

   public static void selectSort(int arr[]) {
        for (int i = 0; i < arr.length-1; i++) {
            for (int j = i+1; j < arr.length; j++) {
                if(arr[i] > arr[j]) {
                    arr[i] = arr[i] ^ arr[j];
                    arr[j] = arr[i] ^ arr[j];
                    arr[i] = arr[i] ^ arr[j];
                }
            }
        }
    }

基本思想: 比较相邻的两个元素。如果第一个比第二个大，就进行数据的交换。

  public static void bubblingSort(int[] arr) {
        for (int i = 0; i < arr.length-1; i++) {
            for (int j = 0; j < arr.length-1-i; j++) {
                if(arr[j] > arr[j+1]) {
                    arr[j] = arr[j] ^ arr[j+1];
                    arr[j+1] = arr[j] ^ arr[j+1];
                    arr[j] = arr[j] ^ arr[j+1];
                }
            }
        }
    }

  public static void main2(String[] args) {
        int arr[] = new int[10_0000];
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(10_0000);
        }
        long beg = System.currentTimeMillis();
        //shellSort(arr);
       insertSort(arr);
        long end = System.currentTimeMillis();
        System.out.println(end-beg);

    }