排序算法：插入排序、冒泡排序、选择排序、希尔排序、堆排序、快速排序、归并排序

た 入场券 2024-04-21 19:30 188阅读 0赞

排序算法相关总结，涉及的排序算法有：插入排序、冒泡排序、选择排序、希尔排序、堆排序、快速排序、归并排序（动图不是自己画的?）。

目录

      • 1.插入排序
      • 2.冒泡排序
      • 3.选择排序
      • 4.希尔排序
      • 5.堆排序
      • 6.快速排序
      • 7.归并排序
      • 总结

稳定性概念:
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i] = r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的,否则称为不稳定的。

1.插入排序

思路：当前元素左边为有序序列，右边为待排序序列，当前元素与有序数列的最后一个元素依次比较，如果比它大，则不动，若比它小，则有序序列最后一个元素后移一位，为当前元素空出一个坑位，循环比较，直到找到当前元素的位置。

图示：

在这里插入图片描述

代码：时间复杂度O(n^2)，空间复杂度O(1)

  1. //插入排序
  3. public class InsertSort {
  5.     public static void main(String[] args) {
  7.         //验证
  8.         int[] arr = new int[]{
  9.     5, 4, 3, 8, 4, 1, 6, 0, 9, 10};
  10.         insertSort(arr);
  11.         for (int i : arr) {
  13.             System.out.print(i + " ");
  14.         }
  15.     }
  17.     //插入排序
  18.     public static void insertSort(int[] arr) {
  20.         for (int i = 0; i < arr.length; i++) {
  22.             //有序区间为 [0,i)
  23.             int k = i;
  24.             //记录i下标当前值 与有序序列比较
  25.             int tmp = arr[i];
  26.             //如果下标合法且比tmp大 则元素后移
  27.             while (k > 0 && tmp < arr[k - 1]) {
  29.                 arr[k] = arr[k - 1];
  30.                 k--;
  31.             }
  32.             arr[k] = tmp;
  33.         }
  34.     }

2.冒泡排序

冒泡！！！好的解释完了

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

代码： 老老老朋友了，时间复杂度O(n^2)，空间复杂度O(1)

  1. //冒泡排序
  3. public class BubbleSort {
  5.     public static void main(String[] args) {
  7.         //验证
  8.         int[] arr = new int[]{
  9.     5, 4, 3, 8, 4, 1, 6, 0, 9, 10};
  10.         bubblesort(arr);
  11.         for (int i : arr) {
  13.             System.out.print(i + " ");
  14.         }
  15.     }
  17.     //冒泡排序
  18.     public static void bubblesort(int[] arr) {
  20.         for (int i = 0; i < arr.length; i++) {
  22.             //判断该趟是否发生交换
  23.             boolean flag = true;
  24.             for (int j = 0; j < arr.length - 1 - i; j++) {
  26.                 if (arr[j] > arr[j + 1]) {
  28.                     //交换
  29.                     int tmp = arr[j];
  30.                     arr[j] = arr[j + 1];
  31.                     arr[j + 1] = tmp;
  32.                     flag = false;
  33.                 }
  34.             }
  35.             //如果没有发生交换 则说明后面的已经有序 结束循环
  36.             if (flag) {
  38.                 break;
  39.             }
  40.         }
  41.     }

3.选择排序

思路：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

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

代码： 时间复杂度O(n^2)，空间复杂度O(1)

  1. //选择排序（将找到的较大元素放置末尾 和上图演示的反着的 但不影响理解）
  3. public class SelectSort {
  5.     public static void main(String[] args) {
  7.         //验证
  8.         int[] arr = new int[]{
  9.     5, 4, 3, 8, 4, 1, 6, 0, 9, 10};
  10.         selectSort(arr);
  11.         for (int i : arr) {
  13.             System.out.print(i + " ");
  14.         }
  15.     }
  17.     public static void selectSort(int[] arr) {
  19.         for (int i = 0; i < arr.length - 1; i++) {
  21.             int maxIdx = 0;
  22.             for (int j = 1; j < arr.length - i; j++) {
  24.                 if (arr[j] > arr[maxIdx]) {
  26.                     maxIdx = j;
  27.                 }
  28.             }
  29.             //swap
  30.             int idx = arr.length - 1 - i;
  31.             int tmp = arr[maxIdx];
  32.             arr[maxIdx] = arr[idx];
  33.             arr[idx] = tmp;
  34.         }
  35.     }

4.希尔排序

我们知道插入排序元素越有序效率越高，当全部有序时，效率达到O(n)，希尔排序正是利用这个特点，进行了大量的分组插入排序，从而达到有序目的。
基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

图示：

在这里插入图片描述

动图：

在这里插入图片描述

代码： 时间复杂度O(n^2)，空间复杂度O(1)

  1. //希尔排序
  3. public class ShellSort {
  5.     public static void main(String[] args) {
  7.         //验证
  8.         int[] arr = new int[]{
  9.     5, 4, 3, 8, 4, 1, 6, 0, 9, 10, -5, 50, 33, 41, 7, 30, 45, 11};
  10.         shellSort(arr);
  11.         for (int i : arr) {
  13.             System.out.print(i + " ");
  14.         }
  15.     }
  17.     public static void shellSort(int[] arr) {
  19.         if (arr.length == 0 || arr.length == 1) {
  21.             return;
  22.         }
  23.         int gap = arr.length / 2;
  24.         while (true) {
  26.             for (int i = gap; i < arr.length; i++) {
  28.                 int tmp = arr[i];
  29.                 int k = i;
  30.                 while (k - gap >= 0 && tmp < arr[k - gap]) {
  32.                     arr[k] = arr[k - gap];
  33.                     k -= gap;
  34.                 }
  35.                 arr[k] = tmp;
  36.             }
  37.             if (gap == 1) {
  39.                 break;
  40.             }
  41.             gap /= 2;
  42.         }
  43.     }

5.堆排序

**堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。

首先，我们应该明白什么是堆，知道我们需要建什么。
堆的特点：

  1. 堆是一棵完全二叉树；
  2. 堆序性 (heap order): 任意节点都优于它的所有孩子。
    a. 如果是任意节点都大于它的所有孩子，这样的堆叫大顶堆，Max Heap;
    b. 如果是任意节点都小于它的所有孩子，这样的堆叫小顶堆，Min Heap;

完全二叉树左右孩子与父节点的坐标关系：
父节点：k
左孩子：2 * k + 1
右孩子： 2 * k + 2

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

代码： 时间复杂度O(N*log(N))，空间复杂度O(1)

  1. //堆排序
  3. public class HeapSort {
  5.     public static void main(String[] args) {
  7.         //验证
  8.         int[] arr = new int[]{
  9.     5, 4, 3, 8, 4, 1, 6, 0, 9, 10, -5, 50, 33, 41, 7, 30, 45, 11};
  10.         heapSort(arr);
  11.         for (int i : arr) {
  13.             System.out.print(i + " ");
  14.         }
  15.     }
  17.     public static void heapSort(int[] arr) {
  19.         //建堆
  20.         createHeap(arr);
  21.         for (int i = 0; i < arr.length - 1; i++) {
  23.             swap(arr, 0, arr.length - 1 - i);
  24.             adjustDown(arr, 0, arr.length - 1 - i);
  25.         }
  26.     }
  28.     public static void createHeap(int[] arr) {
  30.         for (int i = (arr.length - 1 - 1) / 2; i >= 0; i--) {
  32.             adjustDown(arr, i, arr.length);
  33.         }
  34.     }
  36.     //在无序区间内进行向下调整
  37.     public static void adjustDown(int[] arr, int idx, int len) {
  39.         while (2 * idx + 1 < len) {
  41.             int maxIdx = 2 * idx + 1;
  42.             int rightIdx = maxIdx + 1;
  43.             if (rightIdx < len && arr[maxIdx] < arr[rightIdx]) {
  45.                 maxIdx = rightIdx;
  46.             }
  47.             if (arr[maxIdx] < arr[idx]) {
  49.                 break;
  50.             }
  51.             swap(arr, maxIdx, idx);
  52.             //更新
  53.             idx = maxIdx;
  54.         }
  55.     }
  57.     private static void swap(int[] arr, int i, int j) {
  59.         //swap
  60.         int tmp = arr[i];
  61.         arr[i] = arr[j];
  62.         arr[j] = tmp;
  63.     }

6.快速排序

基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

代码：时间复杂度O(n*logn)，空间复杂度O(log n) ~ O(n)

  1. public static void quickSort(int[] arr, int from, int to) {
  3.         //判断是否结束
  4.         if (to - from < 1) {
  6.             return;
  7.         }
  8.         //划分方法 下面有实现
  9.         int div = partition(arr, from, to);
  10.         quickSort(arr, from, div - 1);
  11.         quickSort(arr, div + 1, to);
  12.     }

将区间按照基准值划分为左右两半部分的常见方式有：

1.Hoare：

1.选出一个基准值pivot，一般是最左边或最右边的为基准值
2.找到右边第一个小于pivot的值
3.找到左边第一个大于pivot的值
4.交换两个值，然后重复步骤2、3
5.将基准值放到i == j 的位置，返回基准值下标

  1. public static int partition(int[] arr, int left, int right) {
  3.         int i = left;
  4.         int j = right;
  5.         int pivot = arr[left];
  6.         while (i < j) {
  8.             //注意这里判断j与先判断i的区别
  9.             //先判断j：当i == j时 arr[i] == arr[j] <= povit
  10.             //先判断i：当i == j时 arr[i] == arr[j] >= povit
  11.             while (i < j && arr[j] >= povit) {
  13.                 j--;
  14.             }
  15.             while (i < j && arr[i] <= povit) {
  17.                 i++;
  18.             }
  19.             swap(arr, i, j);
  20.         }
  21.         swap(arr, left, i);
  22.         return i;
  23.     }

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

2.挖坑法：

1.选出一个基准值pivot，一般是最左边或最右边的为基准值 让它做坑位
2.找到右边第一个小于pivot的值 将该值放入坑位 该值的原下标做为新坑位
3.找到左边第一个大于pivot的值 将该值放入坑位 该值的原下标做为新坑位
4.重复步骤2、3
5.将基准值放到i == j 的位置，返回基准值下标

  1. public static int partition(int[] arr, int left, int right) {
  3.         int i = left;
  4.         int j = right;
  5.         int pivot = arr[left];
  6.         while (i < j) {
  8.             while (i < j && arr[j] >= pivot) {
  10.                 j--;
  11.             }
  12.             arr[i] = arr[j];
  13.             while (i < j && arr[i] <= pivot) {
  15.                 i++;
  16.             }
  17.             arr[j] = arr[i];
  18.         }
  19.         arr[i] = pivot;
  20.         return i;
  21.     }

图示：

在这里插入图片描述

3.前后指针法：

1.选出一个基准值pivot，一般是最左边或最右边的为基准值
2.规定[0,pre)为小于pivot的范围，[pre,right]为大于pivot的范围
3.遍历找小于pivot的值，交换arr[pre]和该值，然后pre++
4.最后将pivot值放入数组，放哪里合适呢？当然是pre - 1处，这样确保它的右边大于等于pivot，左边小于等于pivot

  1. public static int partition(int[] arr, int left, int right) {
  3.         int pre = left + 1;
  4.         int pivot = arr[left];
  5.         for (int cur = pre; cur <= right; cur++) {
  7.             if (arr[cur] < pivot) {
  9.                 swap(arr, cur, pre);
  10.                 pre++;
  11.             }
  12.         }
  13.         swap(arr, pre - 1, left);
  14.         return pre - 1;
  15.     }

7.归并排序

基本思想：归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

图示：

在这里插入图片描述

动图：

在这里插入图片描述
代码：时间复杂度O(n*logn)，空间复杂度O(n)

  1. //归并排序
  3. public class MergeSort {
  5.     public static void main(String[] args) {
  7.         //验证
  8.         int[] arr = new int[]{
  9.     5, 4, 3, 8, 4, 1, 6, 0, 9, 10, -5, 50, 33, 41, 7, 30, 45, 11};
  10.         mergeSort(arr, 0, arr.length);
  11.         for (int i : arr) {
  13.             System.out.print(i + " ");
  14.         }
  15.     }
  17.     //[)
  18.     public static void mergeSort(int[] arr, int start, int end) {
  20.         if (end - start <= 1) {
  22.             return;
  23.         }
  24.         int mid = start + (end - start) / 2;
  26.         mergeSort(arr, start, mid);
  27.         mergeSort(arr, mid, end);
  29.         merge(arr, start, mid, end);
  30.     }
  32.     public static void merge(int[] arr, int start, int mid, int end) {
  34.         int[] e = new int[end - start];
  35.         int eIdx = 0;
  36.         int leftIdx = start;
  37.         int rightIdx = mid;
  38.         //归并
  39.         while (leftIdx < mid || rightIdx < end) {
  41.             if (leftIdx == mid) {
  43.                 e[eIdx++] = arr[rightIdx++];
  44.             } else if (rightIdx == end) {
  46.                 e[eIdx++] = arr[leftIdx++];
  47.             } else if (arr[leftIdx] <= arr[rightIdx]) {
  49.                 e[eIdx++] = arr[leftIdx++];
  50.             } else {
  52.                 e[eIdx++] = arr[rightIdx++];
  53.             }
  54.         }
  55.         //放回原数组
  56.         for (int i = 0; i < e.length; i++) {
  58.             arr[start + i] = e[i];
  59.         }
  60.     }
  61. }

总结






































































排序算法 时间复杂度（平均） 时间复杂度（最坏） 时间复杂度（最好） 空间复杂度 稳定性
插入排序 O(n^2) O(n^2) O(n) O(1) 稳定
冒泡排序 O(n^2) O(n^2) O(n) O(1) 稳定
选择排序 O(n^2) O(n^2) O(n^2) O(1) 不稳定
希尔排序 O(n^1.3) O(n^2) O(n) O(1) 不稳定
堆排序 O(nlog n) O(nlog n) O(nlog n) O(1) 不稳定
快速排序 O(nlog n) O(n^2) O(nlog n) O(log n) ~ O(n) 不稳定
归并排序 O(nlog n) O(nlog n) O(nlog n) O(n) 稳定

发表评论

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

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

相关阅读