【算法】排序算法(插入排序、希尔排序、选择排序、冒泡排序、快速排序、归并排序、基数排序、堆排序)

快来打我* 2023-09-23 18:25 212阅读 0赞

目录

  • 一.常见排序类型
  • 二.排序详解
    • 1.冒泡排序
    • 2.选择排序
    • 3.插入排序
    • 4.希尔排序
    • 5.快速排序
    • 6.归并排序
    • 7.基数排序(桶排序)
    • 8.堆排序
  • 三.排序算法比较

一.常见排序类型

  • 插入排序：插入排序、希尔排序
  • 选择排序：选择排序、堆排序
  • 交换排序：冒泡排序、快速排序
  • 归并排序
  • 基数排序(又叫桶排序)

二.排序详解

1.冒泡排序

(1)思路图解

从头开始比较相邻元素的值(就是从下标较小的元素开始)，使值较大的元素逐渐从前移向后部，就像水里的气泡一样，越来越大，向上冒。最终得到从小到大的一个序列。

在这里插入图片描述
在这里插入图片描述

(2)算法实现(java)

  1. /**
  2.  * 冒泡排序
  3.  * author：xinxin
  4.  * 时间复杂度是(n*n)
  5.  */
  6. public class GuLouSort {
  8.     public static void main(String[] args) {
  10.         int[] arr = {
  11.     16,28,5,66,88}; //初始化数组
  12.         int temp = 0; //临时变量
  13.         for (int i = 0; i < arr.length-1; i++){
  14.      //代表大循环  第几趟
  15.             for (int j = 0; j < arr.length-1-i; j++){
  16.      //代表小循环
  17.                 if (arr[j] > arr[j+1]){
  18.      //如果前面的值大于前面的值，那就交换位置
  19.                     temp = arr[j];
  20.                     arr[j] = arr[j+1];
  21.                     arr[j+1] = temp;
  22.                 }
  23.             }
  24.             System.out.println("第"+(i+1)+"趟，排序后的结果");
  25.             System.out.println(Arrays.toString(arr));
  26.         }
  27.     }
  28. }

运行结果
在这里插入图片描述

2.选择排序

(1)思路图解

先从arr[0] ~ arr[n-1]找到一个最小值，和arr[0]交换，在从arr[1] ~ arr[n-1]中找到最小值，和arr[1]交换，以此类推，最终得到一个从小到大排列的序列。

在这里插入图片描述
在这里插入图片描述

(2)算法实现(java)

  1. /**
  2.  * 选择排序
  3.  * author：xinxin
  4.  * 时间复杂度是(n*n)
  5.  */
  6. public class SelectSort {
  8.     public static void main(String[] args) {
  10.         int[] arr = {
  11.     16,6,88,2}; //初始化数组
  12.         for (int i = 0; i < arr.length-1; i++) {
  13.      //代表第几轮循环
  14.             int minIndex = i; //假定最小下标
  15.             int minArr = arr[i]; //假定最小的值
  16.             for (int j = i+1; j < arr.length; j++) {
  17.      //代表每轮循环中去查找最小的值
  18.                 if (minArr > arr[j]){
  19.      //如果假定的最小值比他后面的值要大,记录下标和值(这个地方控制是从大到小排序还是从小到大排序)
  20.                     minIndex = j;    //记录下标
  21.                     minArr = arr[j]; //记录值
  22.                 }
  23.             }
  24.             //交换值
  25.             if (minIndex != i){
  27.                 arr[minIndex] = arr[i];
  28.                 arr[i] = minArr;
  29.             }
  30.             System.out.println("第"+(i+1)+"轮结果为");
  31.             System.out.println(Arrays.toString(arr));
  32.         }
  33.     }
  34. }

运行结果
在这里插入图片描述

3.插入排序

(1)思路图解

n个元素，分成一个有序序列和无序序列，开始有序序列只有一个元素，无序序列包含n-1个元素，排序时每次从无序序列取出第一个元素，和有序序列的元素的排序码进行比较，然后放到合适的位置，最后形成新的有序序列。

在这里插入图片描述
在这里插入图片描述

(2)算法实现(java)

  1. /**
  2.  * 插入排序
  3.  * author：xinxin
  4.  */
  5. public class InsertSort {
  7.     public static void main(String[] args) {
  9.         int[] arr = {
  10.     18, 6, 26, 15,  21,10};//初始化数组
  11.         for (int i = 1; i < arr.length; i++) {
  13.             int currValue = arr[i]; //要插入的元素，从arr[1]开始，因为arr[0]是有序序列第一个元素
  14.             int beforeIndex = i-1; //要插入元素前面的元素的下标
  15.             while(beforeIndex >= 0 && currValue < arr[beforeIndex]){
  16.      //判断要插入元素的位置，并且没有找到插入位置(从这里可以改变从大到小排序还是从小到大)
  17.                 arr[beforeIndex + 1] = arr[beforeIndex]; //arr[beforeIndex]后移
  18.                 beforeIndex--;
  19.             }
  21.             //当退出while循环，找到插入位置
  22.             arr[beforeIndex + 1] = currValue;
  23.             System.out.println("第"+i+"次插入结果");
  24.             System.out.println(Arrays.toString(arr));
  25.         }
  27.     }
  28. }

运行结果
在这里插入图片描述

4.希尔排序

(1)思路图解

希尔排序也是一种插入排序，但是更加高效，也称为速效增量排序。
按照一定的增量(步长)进行分组，然后对每组进行插入排序，随着增量减少，每组的元素就越多，当增量减至1时，元素被分为一组，算法结束。

在这里插入图片描述
在这里插入图片描述

(2)算法实现(交换法)

  1. /**
  2.  * 希尔排序(交换法)
  3.  * author：xinxin
  4.  */
  5. public class ShellSort {
  7.     public static void main(String[] args) {
  9.         int[] arr = {
  10.     8, 9, 1, 7, 2, 3, 5, 4, 6, 0};//初始数组
  11.         int temp = 0;
  12.         int count = 0;
  13.         //增量
  14.         for (int gap = arr.length/2; gap > 0; gap=gap/2){
  16.             //遍历组中所有元素，gap为步长
  17.             for (int i = gap; i < arr.length; i++){
  19.                 for (int j = i - gap; j >= 0; j = j-gap){
  21.                     //如果当前元素大于加上步长的元素，那就交换位置
  22.                     if (arr[j] > arr[j+gap]){
  24.                         temp = arr[j];
  25.                         arr[j] = arr[j+gap];
  26.                         arr[j+gap] = temp;
  27.                     }
  28.                 }
  29.             }
  30.             System.out.println("希尔排序(交换法)第"+(++count)+"轮的结果");
  31.             System.out.println(Arrays.toString(arr));
  32.         }
  33.     }
  34. }

运行结果(交换法)
在这里插入图片描述

(3)算法实现(移动法)

  1. /**
  2.  * 希尔排序(移动法)
  3.  * author：xinxin
  4.  */
  5. public class ShellSort2 {
  7.     public static void main(String[] args) {
  9.         int[] arr = {
  10.     8, 9, 1, 7, 2, 3, 5, 4, 6, 0};//初始数组
  11.         int count = 0;
  12.         for (int gap = arr.length/2; gap > 0; gap = gap/2){
  14.             //从第gap元素开始进行插入排序
  15.             for (int i = gap; i<arr.length; i++){
  17.                 int j = i;
  18.                 int temp = arr[j];
  19.                 if (arr[i] < arr[j - gap]){
  21.                     while(j - gap >= 0 && temp < arr[j - gap]){
  23.                         //移动
  24.                         arr[j] = arr[j - gap];
  25.                         j = j - gap;
  26.                     }
  27.                     arr[j] = temp;
  28.                 }
  29.             }
  30.             System.out.println("希尔排序(移动法)第"+(++count)+"轮的结果");
  31.             System.out.println(Arrays.toString(arr));
  32.         }
  33.     }
  34. }

运行结果(移动法)
在这里插入图片描述

5.快速排序

(1)思路图解

快速排序是对冒泡排序的一种改进。
基本思想是：把需要排序的元素分成两部分，一部分比另一部分都要小，然后进行快速排序，然后递归，最终得到有序序列。

在这里插入图片描述
这个图是以第一个元素为中间值分割。（黄色的就相当于中间值，然后把比大小分成两组）
在这里插入图片描述

(2)算法实现(java)

  1. /**
  2.  * 快速排序
  3.  * author：xinxin
  4.  */
  5. public class QuikeSort {
  7.     public static void main(String[] args) {
  9.         int[] arr = {
  10.     1, 66, 2, 28, 0, 18};
  11.         quickeSotr(arr,0,arr.length-1);
  12.         System.out.println("快速排序结果为"+ Arrays.toString(arr));
  13.     }
  15.     public static void quickeSotr(int arr[],int left,int right){
  17.         int l = left;//左下标
  18.         int r = right;//右下标
  19.         int center = arr[(l + r)/2];//中间值
  20.         int temp = 0;//临时变量
  22.         //找到比center值小的放左边，比center值大的放右边
  23.         while(l < r){
  26.             //找到比center小的值，才退出
  27.             while (arr[l] < center){
  29.                 l = l + 1;
  30.             }
  31.             //找到比center大的值，才退出
  32.             while (arr[r] > center){
  34.                 r = r - 1;
  35.             }
  37.             //证明左边都是小于center的数，右边都是大于center的数
  38.             if (l >= r){
  40.                 break;
  41.             }
  42.             //交换变量
  43.             temp = arr[l];
  44.             arr[l] = arr[r];
  45.             arr[r] = temp;
  47.             //前移
  48.             if (arr[l] == center){
  50.                 r = r - 1;
  51.             }
  53.             //后移
  54.             if (arr[r] == center){
  56.                 l = l + 1;
  57.             }
  58.         }
  60.         //如果相等必须进行下面操作，不然会栈溢出
  61.         if (l == r){
  63.             l = l + 1;
  64.             r = r - 1;
  65.         }
  67.         //向左递归
  68.         if (left < r){
  70.             quickeSotr(arr,left,r);
  71.         }
  73.         //向右递归
  74.         if (right > l){
  76.             quickeSotr(arr,l,right);
  77.         }
  78.     }
  79. }

运行结果
在这里插入图片描述

6.归并排序

(1)思路图解

利用归并的思想实现排序，采用分治策略：将问题分成小的问题然后递归求解，而治的阶段将分的阶段得到的结果放一起组合，即分而治之。

下面治的阶段相当于 [4,5,7,8]和[1,2,3,6]各有指针去移动比较两个数组元素大小(和快速排序移动指针一样)，然后放入新的数组。

在这里插入图片描述
在这里插入图片描述

(2)算法实现(java)

  1. public class MergeSort {
  3.     public static void main(String[] args) {
  5.         int[] arr = {
  6.     8, 4, 5, 7, 1, 3, 6, 2};
  7.         int[] temp = new int[arr.length];
  8.         mergeSort(arr,0,arr.length-1,temp);
  9.         System.out.println("归并排序结果为"+ Arrays.toString(arr));
  10.     }
  12.     /**
  13.      * 分 + 合
  14.      * @param arr
  15.      * @param left
  16.      * @param right
  17.      * @param temp
  18.      */
  19.     public static void mergeSort(int[] arr, int left, int right, int[] temp) {
  21.         if (left < right){
  23.             int center = (left + right)/2;//中间索引
  24.             mergeSort(arr,left,center,temp);//左递归
  25.             mergeSort(arr,center + 1,right,temp);//右递归
  26.             merge(arr,left,center,right,temp);//合并(治)
  27.         }
  28.     }
  29.         /**
  30.          * 合并的方法
  31.          * 
  32.          * @param arr 原数组
  33.          * @param left 左下标
  34.          * @param center 中间值
  35.          * @param right 右下标
  36.          * @param temp 中转数组
  37.          */
  38.     public static void merge(int[] arr, int left, int center, int right, int[] temp){
  40.         int i = left;//左边序列初始索引
  41.         int j = center + 1;//右边序列初始索引
  42.         int t = 0;//temp数组初始下标
  44.         //把左右两边的有序序列按规则填充到temp中
  45.         while(i <= center && j <= right){
  47.             //当左边序列元素小于右边序列元素，把左边序列元素放进temp数组中
  48.             if (arr[i] < arr[j]){
  50.                 temp[t] = arr[i];
  51.                 i = i + 1;
  52.                 t = t + 1;
  53.             }else{
  54.     //反之，将右边序列元素放进temp数组中
  55.                 temp[t] = arr[j];
  56.                 j = j + 1;
  57.                 t = t + 1;
  58.             }
  59.         }
  60.         //左边序列剩余元素放进temp数组
  61.         while(i <= center){
  63.             temp[t] = arr[i];
  64.             i = i + 1;
  65.             t = t + 1;
  66.         }
  68.         //右边序列剩余元素放进temp数组
  69.         while(j <= right){
  71.             temp[t] = arr[j];
  72.             j = j + 1;
  73.             t = t + 1;
  74.         }
  76.         //将temp拷贝到arr，有可能不是全部拷贝
  77.         t = 0;
  78.         int tempLeft = left;
  79.         System.out.println(" ");
  80.         System.out.println("tempLeft="+tempLeft+" right="+right);
  81.         while (tempLeft < right){
  83.             arr[tempLeft] = temp[t];
  84.             tempLeft = tempLeft + 1;
  85.             t = t + 1;
  86.         }
  87.     }
  88. }

运行结果
在这里插入图片描述

7.基数排序(桶排序)

(1)思路图解

将整数按位数切割成不同数字，然后按每个位数分别比较。
将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后从最低位开始，依次进行依次排序。这样从最低到最高位排序完成之后，就得到一个有序序列。

在这里插入图片描述
(2)算法实现(java)

  1. /**
  2.  * 基数排序(桶排序)
  3.  * author：xinxin
  4.  */
  5. public class BucketSort {
  7.     public static void main(String[] args) {
  9.         int[] arr = {
  10.     3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
  12.         //找到最大的数
  13.         int max = arr[0];
  14.         for (int k = 1; k < arr.length; k++){
  16.             if (max < arr[k]){
  18.                 max = arr[k];
  19.             }
  20.         }
  21.         //最大的数位数是几位
  22.         int maxLength = (max + "").length();
  24.         //表示10个桶，每个一维数组都是一个桶
  25.         int[][] bucket = new int[10][arr.length];
  27.         //记录每个桶放入数据的个数
  28.         int[] qty = new int[10];
  30.         for (int l = 0,n = 1; l < maxLength; l++,n = n * 10) {
  32.             //取对应位数数放进桶(第一次个位，第二次十位，第三次百位以此类推)
  33.             for (int i = 0; i < arr.length; i++) {
  35.                 int bits = arr[i] / n % 10;
  36.                 //放到这个桶第一个位置，第二次放在第二个位置
  37.                 bucket[bits][qty[bits]] = arr[i];
  38.                 qty[bits]++;
  39.             }
  41.             //取出桶的数据放回原数组
  42.             int index = 0;
  43.             for (int j = 0; j < qty.length; j++) {
  45.                 if (qty[j] != 0){
  47.                     for (int y = 0; y < qty[j]; y++){
  49.                         arr[index++] = bucket[j][y];
  50.                     }
  51.                 }
  52.                 //需要把桶归零
  53.                 qty[j] = 0;
  54.             }
  55.             System.out.println("第"+(l+1)+"轮,对位数的处理");
  56.             System.out.println(Arrays.toString(arr));
  57.         }
  59.     }
  60. }

运行结果
在这里插入图片描述

8.堆排序

(1)思路图解

将待排序序列构成一个大顶堆，最大值就是堆的根节点，将其与末尾元素交换，此时末尾就是最大值，然后剩余的元素重新构成堆，然后反复执行，最终形成一个有序序列。

在这里插入图片描述
(2)算法实现(java)

  1. /**
  2.  * 堆排序
  3.  * author：xinxin
  4.  */
  5. public class HeapSort {
  7.     public static void main(String[] args) {
  9.         int[] arr = {
  10.     5,2,7,3,6,1,4};
  11.         int temp = 0;
  13.         //使数组形成大顶堆
  14.         for (int i = arr.length / 2 - 1; i >= 0; i--) {
  16.             bigHeap(arr,i,arr.length);
  17.         }
  19.         //堆顶元素与末尾元素交换，使最大元素放在数组末端
  20.         for (int j = arr.length-1; j > 0; j--) {
  22.             temp = arr[j];
  23.             arr[j] = arr[0];
  24.             arr[0] = temp;
  25.             bigHeap(arr,0,j);
  26.         }
  27.         System.out.println("堆排序结果");
  28.         System.out.println(Arrays.toString(arr));
  29.     }
  31.     /**
  32.      * 使待排序数组形成大顶堆
  33.      * @param arr  初始数组
  34.      * @param i    非叶子节点在数组中的下标
  35.      * @param length 对多少个元素进行调整，length在减少
  36.      */
  37.     public static void bigHeap(int[] arr, int i, int length){
  39.         int temp = arr[i];
  41.         //i * 2 + 1是 i 的左子节点
  42.       for (int k = i * 2 + 1; k < length; k = k * 2 + 1){
  44.           //左子节点小于右子节点
  45.           if(k + 1 < length && arr[k] < arr[k+1]){
  47.               //指向右子节点
  48.               k++;
  49.           }
  50.           //子节点大于根节点
  51.           if (arr[k] > temp){
  53.               arr[i] = arr[k];
  54.               i = k;
  55.           }else{
  57.               break;
  58.           }
  60.           //把temp放在调整后的位置
  61.           arr[i] = temp;
  62.       }
  63.     }
  64. }

运行结果
在这里插入图片描述

三.排序算法比较

shell排序是希尔排序在这里插入图片描述

  • 稳定

a原本在b前面，而a=b，排序之后a还在b前面。

  • 不稳定

a原本在b前面，而a=b，排序之后a可能在b后面。

  • 时间复杂度

算法执行需要的时间。

  • 空间复杂度

算法运行需要的内存的大小。

发表评论

表情：
评论列表 （有 0 条评论，212人围观）

还没有评论，来说两句吧...

相关阅读