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)希尔排序,对有序序列插入时采用移动法,并测试排序速度


版权声明:本文为qq_56469942原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
THE END
< <上一篇
下一篇>>