[数据结构与算法]06-java数据结构之排序算法（冒泡，选择，插入，希尔，快速，归并等排序算法）

一、排序算法的介绍

排序是将一组数据，依指定的顺序进行排列的过程。

二、排序的分类

2.1、内部排序

指将需要处理的所有数据都加载到内部存储器（内存）中进行排序。

2.2、外部排序

数据量过大，无法全部加载到内存中，需要借助**外部存储（文件等）**进行排序。

三、算法

3.1、冒泡排序

3.1.1、基本介绍

基本思想：通过对待排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值，
		若发现逆序则交换，使值较大的元素慢慢从前移向后部，就像水底的气泡一样向上冒。

优化：
因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。

3.1.2、演示冒泡过程的图解

第一趟排序，就是将最大的数放在最后
第二趟排序，就是将第二大的数排列在倒数第二位
第三趟排序，就是将第三大的数排列在倒数第三位
第四趟排序，就是将第四大的数排列在倒数第四位
最后就是一个排好序的数组了。

3.1.3、代码实现

public class BubbleSort {
    public static void main(String[] args) {
        int[] a={3,9,-1,10,20};
        BubbleSortTest(a);
        for (int item:a) {
            System.out.print(item+"\t");
        }
    }

    public static void BubbleSortTest(int[] arr){
        int temp=0; //临时变量用于交换
        boolean flag=false; // 标识，判断是否进行了交换
        // 第一层循环
        for(int j=0;j<arr.length-1;j++){
        	// 第二层循环
            for(int i=0;i<arr.length-1-j;i++) {
            	// 如果前一个大于后一个数就开始交换
                if (arr[i] > arr[i + 1]) {
                    flag = true;
                    // 先把大的数存入临时变量
                    temp = arr[i];
                    // 把小的数放在前面
                    arr[i] = arr[i + 1];
                    // 把临时变量中的大的数放在后面
                    arr[i + 1] = temp;
                }
            }
            if(!flag){ //在一趟排序中，一次交换都没有发生过
                break;
            }else{
                flag=false;  // 重置flag,进行下次判断
            }
        }
    }
}

3.2、选择排序

3.2.1、基本介绍

选择排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。

3.2.2、演示选择过程的图解

说明：
1、选择排序一共有数组大小-1轮排序
2、每一轮排序，又是一个循环，循环的规则
? 2.1、先假定当前这个数是最小值
? 2.2、然后和后面的每个数进行比较，如果发现有比当前数更小的数，
? 就重新确定最小值，并得到下标
? 2.3、当遍历到数组的最后时，就得到本轮最小数和下标
? 2.4、交换

3.2.3、代码实现

public class selectSort {
    public static void main(String[] args) {
        int a[]={101,34,119,1,-3,99,100,66,55};
        selectSort(a);
        for (int item:a) {
            System.out.printf(item+"\t");
        }
    }

    public static void selectSort(int[] arr){
        for(int i=0;i<arr.length-1;i++){
            // 先让a[i]表示最小值
            int minSize=arr[i];
            // index表示最小值的下标
            int index=i;
            for(int j=i+1;j<arr.length;j++){
                // 如果有值比minSize小，就把该值赋值给minSize,并把对应的下标赋值给index
                if(minSize>arr[j]){
                    minSize=arr[j];
                    index=j;
                }
            }
            // 一层循环执行后，找到了最小值，然后arr[i]与最小值进行互换
            arr[index]=arr[i];
            arr[i]=minSize;
        }
    }
}

3.3、插入排序

3.3.1、基本介绍

插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。

3.3.2、演示插入过程的图解

3.3.3、代码实现

public class InsertSort {
    public static void main(String[] args) {
        int[] num={17,3,25,14,20,9};
        InsertSort(num);
        for (int item:num) {
            System.out.printf(item+"\t");
        }
    }

    public static void InsertSort(int[] arr){
        int insertVal=0;
        int insertIndex=0;

        for(int i=1;i<arr.length;i++){
            // 待插入的值
            insertVal=arr[i];
            // 待插入值的下标的前一个下标
            insertIndex=i-1;
            // 给insertVal找到插入位置
            // while的作用就是让插入的值跟前面的值比较，并让比插入的值大的值后退
            while(insertIndex>=0&&insertVal<arr[insertIndex]){
                arr[insertIndex+1]=arr[insertIndex];
                insertIndex--;
            }
            // 当退出循环，找到插入的位置为insertIndex+1
            // 判断是否需要赋值
            if(insertIndex!=i){
                arr[insertIndex+1]=insertVal;
            }
        }
    }
}

3.4、希尔排序

3.4.1、基本介绍

希尔排序是一种插入排序，它是简单插入排序经过改进的一个更高效的版本，也称为缩小增量排序。

3.4.2、演示希尔过程的图解

?希尔排序是把记录按下标的一定增量分组，对每组使用直接插入算法排序；随着增量的减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

3.4.3、代码实现

1）希尔排序，对有序序列插入时采用交换法，并测试排序速度
2）希尔排序，对有序序列插入时采用移动法，并测试排序速度