java数据结构–排序

1. 数据的移动方式，可分为“直接移动”和“逻辑移动”两种。直接移动改变两个数据的位置，而逻辑移动，则是改变数据的指针。
2. 数据移动使用的内存：内部排序，排序的数据量小，可以完全在内存中进行。外部排序，排序的数据量无法直接在内存内进行排序，而必须使用辅助存储器。
3. 排序算法的选择，通常由以下几点决定
   1. 算法是否稳定，排序过后，两个相同值的记录位置先后顺序不变，则为稳定。
   2. 时间复杂度
   3. 空间复杂度
4. 内部排序法简介

代码如下

package com.cjm.mvnbook.test8.SourceTest;

public class SortTest {

    public static void main(String[] args) {
        int[] arr = new int[]{6, 5, 3, 2, 4, 8, 9, 1};
        ShellSort(arr);
    }

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

    }

    //选择排序
    public static void SelectSort(int[] arr){
        int length = arr.length - 1;
        int temp;

        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length + 1; j++) {
                if(arr[i] > arr[j]){
                    temp = arr[i];
                    arr[i]  = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }

    //插入排序
    public static void InsertSort(int[] arr){
        int length = arr.length;
        int i,j,tmp;
        for (i = 1; i < length; i++) {
            tmp = arr[i];
            j = i -1;
            while (j >=0 && tmp < arr[j]){
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = tmp;

            showData(arr);
        }
    }

    //希尔排序
    public static void ShellSort(int[] arr){
        int i;  //i为扫描次数
        int j;  //以j来定位比较的元素
        int k = 1; //k打印计数
        int tmp;//tmp用来暂存数据
        int jmp;//设定间隔位移量
        int size = arr.length;
        jmp =size/2;
        while (jmp != 0){
            for (i = jmp; i < size; i++){
                tmp = arr[i];
                j = i - jmp;
                while (j >= 0 && tmp < arr[j]){
                    arr[j + jmp] = arr[j];
                    j = j - jmp;
                }
                arr[jmp + j] = tmp;
            }
            System.out.println("第" + (k++) + "次排序：");
            showData(arr);
            jmp = jmp/2;
        }
    }

    public static void showData(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println("\n");
    }
}