【Java数据结构与算法】第七章冒泡排序选择排序插入排序和希尔排序

第七章冒泡排序、选择排序、插入排序和希尔排序

文章目录

第七章冒泡排序、选择排序、插入排序和希尔排序一、冒泡排序1.基本介绍2.代码实现二、选择排序1.基本介绍2.代码实现三、插入排序1.基本介绍2.代码实现四、希尔排序1.基本介绍2.代码实现

一、冒泡排序

1.基本介绍

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

如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，即相同元素的前后顺序并没有改变，因此冒泡排序是一种稳定排序算法

算法步骤

比较相邻的元素。如果第一个比第二个大，就交换他们两个对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数针对所有的元素重复以上的步骤，除了最后一个持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

2.代码实现

package com.sisyphus.sort;import java.text.SimpleDateFormat;import java.util.Arrays;import java.util.Date;/*** @Description: 冒泡排序$* @Param: $* @return: $* @Author: Sisyphus* @Date: 7/17$*/public class BubbleSort {public static void main(String[] args) {//int arr[] = {3, 9, -1, 10, 20};//System.out.println("排序前");//System.out.println(Arrays.toString(arr));//测试一下冒泡排序的速度，给 80000个数据//创建一个 80000 个随机数的数组int[] arr = new int[80000];for (int i = 0; i < 80000; i++) {arr[i] = (int)(Math.random() * 8000000);//生成一个 [0,8000000] 的随机数}Date date1 = new Date();SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");String data1Str = simpleDateFormat.format(date1);System.out.println("排序前的时间是：" + data1Str);bubbleSort(arr);Date date2 = new Date();String data2Str = simpleDateFormat.format(date2);System.out.println("排序后的时间是：" + data2Str);}//封装成方法private static void bubbleSort(int[] arr){int temp = 0;//临时变量，用于数据交换boolean flag = false;//标识变量，判断是否进行过交换//冒泡排序的时间复杂度 O(n^2)for (int i = 0; i < arr.length; i++) {for (int j = 0; j < arr.length - 1; j++) {//如果前面的数比后面的数大，则交换if (arr[j] > arr[j + 1]){flag = true;temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}//System.out.println("第"+(i + 1)+"趟排序后的数组");//System.out.println(Arrays.toString(arr));if (!flag) {//在一趟排序中，一次交换都没有发生break;}else {flag = false;//重置 flag，进行下次判}}}}

二、选择排序

1.基本介绍

选择排序（Selection Sort）是一种简单的排序方法。它的基本思想是第一次从 arr 数组中选择最小值与 arr[0] 交换，接下来每次都从剩余数里选择最小的数与剩余数的第一个数进行交换。总共进行 n - 1 次，得到一个从小到大排序的有序序列

在一趟选择中，如果当前元素比这一趟中的第一个元素小，而这个较小的元素又出现在一个和第一个元素相等的元素后面，那么交换后两个相同元素的相对顺序就被改变了，因此选择排序是一种不稳定的排序算法。举个例子，序列 5 8 5 2 9，在第一遍选择中，第 1 个元素 5 会和 2 交换，那么原序列中 2 个 5 的相对前后顺序就被破坏了

算法步骤

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾重复第二步，直到所有元素均排序完毕

2.代码实现

package com.sisyphus.sort;import java.text.SimpleDateFormat;import java.util.Arrays;import java.util.Date;/*** @Description: 选择排序$* @Param: $* @return: $* @Author: Sisyphus* @Date: 7/17$*/public class SelectionSort {public static void main(String[] args) {//int[] arr = {101, 34, 119, 1, -1, 90, 123};//创建一个 80000 个随机数的数组int[] arr = new int[80000];for (int i = 0; i < 80000; i++) {arr[i] = (int)(Math.random() * 8000000);//生成一个 [0,8000000] 的随机数}Date date1 = new Date();SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");String data1Str = simpleDateFormat.format(date1);System.out.println("排序前的时间是：" + data1Str);selectionSort(arr);Date date2 = new Date();String data2Str = simpleDateFormat.format(date2);System.out.println("排序后的时间是：" + data2Str);// System.out.println("排序前");// System.out.println(Arrays.toString(arr));// selectionSort(arr);// System.out.println("排序后");// System.out.println(Arrays.toString(arr));}public static void selectionSort(int[] arr){for (int i = 0; i < arr.length - 1; i++) {int minIndex = i;int min = arr[i];for (int j = i + 1; j < arr.length; j++) {if (min > arr[j]){//说明假定的最小值，并不是最小；如果需要从大到小排序，只需要改成小于号min = arr[j];//重置 minminIndex = j;//重置 minIndex}}//将最小值与 arr[i] 交换if (minIndex != i){arr[minIndex] = arr[i];arr[i] = min;}//System.out.println("第" + (i + 1) + "轮后");//System.out.println(Arrays.toString(arr));}}}

三、插入排序

1.基本介绍

插入排序（Insertion Sort）是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入

在碰见一个和插入元素相等的时候，插入元素会把想插入的元素放在相等元素的后面。这样，相等元素的前后顺序没有改变，从原无序表出去的顺序就是排好序后的顺序，因此插入排序是稳定的

算法步骤

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面）

2.代码实现

package com.sisyphus.sort;import java.text.SimpleDateFormat;import java.util.Arrays;import java.util.Date;/*** @Description: 插入排序$* @Param: $* @return: $* @Author: Sisyphus* @Date: 7/17$*/public class InsertionSort {public static void main(String[] args) {//int[] arr = {101, 34, 119, 1, -1, 89};//创建一个 80000 个随机数的数组int[] arr = new int[80000];for (int i = 0; i < 80000; i++) {arr[i] = (int)(Math.random() * 8000000);//生成一个 [0,8000000] 的随机数}Date date1 = new Date();SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");String data1Str = simpleDateFormat.format(date1);System.out.println("排序前的时间是：" + data1Str);insertionSort(arr);Date date2 = new Date();String data2Str = simpleDateFormat.format(date2);System.out.println("排序后的时间是：" + data2Str);}public static void insertionSort(int[] arr){int insertVal = 0;int insertIndex = 0;for (int i = 1; i < arr.length; i++) {//定义待插入的数insertVal = arr[i];insertIndex = i - 1;//即 arr[1] 的前面这个数的下标//给 insertVal 找到插入的位置//说明//1.insertIndex >= 0 保证在给 insertVal 找插入位置，不越界；当 insertIndex = -1 时退出循环，说明待查如的数 insertVal 是最小的，需要插入到开头，即（-1 + 1 = 0）的位置//2.insertVal < arr[insertIndex] 待插入的数，还没有找到插入的位置//3.就需要将 arr[insertIndex]//4.继续循环，找到之后退出循环while((insertIndex >= 0) && (insertVal < arr[insertIndex])){arr[insertIndex + 1] = arr[insertIndex];//arr[insertIndex]insertIndex--;}//当退出 while 循环时，说明插入的位置找到，insertIndex + 1//这里我们判断是否需要赋值if (insertIndex +1 != i){arr[insertIndex + 1] = insertVal;}//System.out.println("第" + i + "轮插入");//System.out.println(Arrays.toString(arr));}}}

四、希尔排序

1.基本介绍

希尔排序（Shell’s Sort），也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序

由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的

算法步骤

选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1按增量序列个数 k，对序列进行 k 趟排序每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1时，整个序列作为一个表来处理，表长度即为整个序列的长度

2.代码实现

package com.sisyphus.sort;import java.text.SimpleDateFormat;import java.util.Arrays;import java.util.Date;/*** @Description: 希尔排序$* @Param: $* @return: $* @Author: Sisyphus* @Date: 7/17$*/public class ShellSort {public static void main(String[] args){//int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6 ,0};//创建一个 80000 个随机数的数组int[] arr = new int[80000];for (int i = 0; i < 80000; i++) {arr[i] = (int)(Math.random() * 8000000);//生成一个 [0,8000000] 的随机数}Date date1 = new Date();SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");String data1Str = simpleDateFormat.format(date1);System.out.println("排序前的时间是：" + data1Str);shellSort(arr);Date date2 = new Date();String data2Str = simpleDateFormat.format(date2);System.out.println("排序后的时间是：" + data2Str);}public static void shellSort(int[] arr){//增量 gap，并逐步地缩小增量for (int gap = arr.length/2; gap > 0; gap /= 2) {//从第 gap 个元素开始，对其所在的组逐个进行插入排序for (int i = gap; i < arr.length; i++) {int j = i;int temp = arr[i];if (arr[j] < arr[j - gap]){while((j - gap >= 0) && (temp < arr[j - gap])){//移动arr[j] = arr[j - gap];j -= gap;}//当退出 while 循环后，就给 temp 找到了插入的位置arr[j] = temp;}}}}}