devbox
木道寻08
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构_排序

作者：木道寻08 | 2024-07-20 11:28:39

赞

踩

数据结构_排序

目录

一、排序

二、插入排序

2.1 直接插入排序

2.2 希尔排序

三、选择排序

3.1 直接选择排序

3.2 堆排序

四、交换排序

4.1 冒泡排序

4.2 快速排序

五、归并排序

六、排序算法分析

总结

一、排序

排序：就是使一串记录序列，按照其中某个或某些关键字的大小，进行递增或递减的排列操作。

稳定性：假定在待排序的记录序列中，存在多个具有相同关键字的记录，若经过排序后，这些记录的相对次序保持不变，则称这种排序算法是稳定的；否则称为不稳定。

例如，在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，若排序后的序列中，r[i] 仍在 r[j] 之前，则排序算法稳定，反之即不稳定。

二、插入排序

2.1 直接插入排序

核心思想：从第二个元素开始遍历，每次遍历将该元素与其前方元素对比，做出相应交换。

  1.     public static void insertSort(int[] array) {
  2.         //初始 i 下标指向第二个元素
  3.         for (int i = 1; i < array.length; i++) {
  4.             //将 i下标的值放入 temp 中
  5.             int temp = array[i];
  6.             //初始 j 下标指向 i 下标的前一位
  7.             int j = i-1;
  8.             for (; j >= 0; j--) {
  9.                 //若 j 下标的值比 temp 中的值大，则将其往后移一位
  10.                 if (array[j] > temp) {
  11.                     array[j+1] = array[j];
  12.                 } else {
  13.                     break;
  14.                 }
  15.             }
  16.             //循环结束将原本 i 的值放至 j 下标的后一位中
  17.             array[j+1] = temp;
  18.         }
  19.     }

【总结】

时间复杂度：

        最坏情况下：O(n^2)

        最好情况下：O(n)

空间复杂度：O(1)

稳定性：稳定

适用性：待排序序列接近有序

2.2 希尔排序

希尔排序也叫缩小增量排序，基本思想：选定一个整数 gap，将待排序序列分为 gap 组，所有距离为 gap 的元素为同一组，每组分别进行直接插入排序；然后缩小 gap，继续分组排序，直至 gap = 1 时，所有元素为一组，最后进行一次直接插入排序。

  1.     public static void shellSort(int[] array) {
  2.         int gap = array.length;
  3.         //gap>1 都属于预排序
  4.         while (gap > 1) {
  5.             //取 gap 为全部元素的一半
  6.             gap /= 2;
  7.             //每组排序
  8.             shell(array, gap);
  9.         }
  10.     }
  11.  
  12.     private static void shell(int[] array, int gap) {
  13.         //初始 i 下标指向 gap，即每组的第二个元素
  14.         for (int i = gap; i < array.length; i++) {
  15.             //将 i下标的值放入 temp 中
  16.             int temp = array[i];
  17.             //初始 j 下标指向 i 下标的前 1gap 位
  18.             //j 每次往前 1gap 位
  19.             int j = i-gap;
  20.             for (; j >= 0; j-=gap) {
  21.                 //若 j 下标的值比 temp 中的值大，则将其往后移 1gap 位
  22.                 if (array[j] > temp) {
  23.                     array[j+gap] = array[j];
  24.                 } else {
  25.                     break;
  26.                 }
  27.             }
  28.             //循环结束将原本 i 的值放至 j 下标的后 1gap 位中
  29.             array[j+gap] = temp;
  30.         }
  31.     }

【总结】 

1、希尔排序是对直接插入排序的优化。

2、当 gap>1 时，都是预排序，是为了让序列趋于有序。

3、稳定性：不稳定

三、选择排序

3.1 直接选择排序

核心思想：遍历每个元素，每次遍历确定一个最小值令其有序。

  1.     public static void selectSort(int[] array) {
  2.         //遍历每个元素
  3.         for (int i = 0; i < array.length; i++) {
  4.             //初始化 minIndex 用于指向最小值
  5.             int minIndex = i;
  6.             //i 下标与后方每个元素对比
  7.             for (int j = i+1; j < array.length; j++) {
  8.                 //确保 minIndex 指向 i 下标及其后方元素的最小值
  9.                 if (array[j] < array[minIndex]) {
  10.                     minIndex = j;
  11.                 }
  12.             }
  13.             //交换 i 下标与 minIndex 下标的值
  14.             int temp = array[i];
  15.             array[i] = array[minIndex];
  16.             array[minIndex] = temp;
  17.         }
  18.     }

【总结】

时间复杂度：O(n^2)

空间复杂度：O(1)

稳定性：不稳定

3.2 堆排序

① 创建大根堆，初始化 end = array.length-1，即 end 指向最后一个结点；

② 将栈顶元素交换至 end 下标。由于大根堆中栈顶元素最大，故交换一次，end--，保证每次交换后的栈顶元素位置不变；

③ 重新向下调整为大根堆；

④ 重复 ②、③ 操作，直至排序完成。

  1.     //创建大根堆
  2.     private static void createHeap(int[] array) {
  3.         //从最后一棵子树开始调整，依次往前，直至根结点
  4.         //父亲结点 = (孩子结点-1) / 2
  5.         //usedSize-1 是树中最后一个结点
  6.         for (int parent = (array.length-1-1) / 2; parent >= 0; parent--) {
  7.             //向下调整
  8.             siftDown(array, parent,array.length);
  9.         }
  10.     }
  11.     //堆排序
  12.     public static void heapSort(int[] array) {
  13.         //创建大根堆
  14.         createHeap(array);
  15.         
  16.         int end = array.length-1;
  17.         while (end > 0) {
  18.             //将大根堆中栈顶元素交换至 end
  19.             swap(array, 0, end);
  20.             //向下调整为大根堆
  21.             siftDown(array, 0, end);
  22.             //保证每次调整的栈顶元素位置不变
  23.             end--;
  24.         }
  25.     }
  26.     //向下调整
  27.     private static void siftDown(int[] array, int parent, int length) {
  28.         //左孩子结点 = 父亲结点*2 + 1
  29.         int child = parent*2 + 1;
  30.  
  31.         //首先保证该结点有左孩子结点
  32.         while (child < length) {
  33.  
  34.             //再次确定该结点有右孩子结点，再进行比较
  35.             //保证 child 引用指向孩子结点中最大值
  36.             if ((child+1) < length && array[child] < array[child+1]) {
  37.                 //若右孩子的值大于左孩子，则 child 引用指向右孩子
  38.                 child = child + 1;
  39.             }
  40.  
  41.             if (array[child] > array[parent]) {
  42.                 //若 child 比 parent 大，则交换元素
  43.                 swap(array, child, parent);
  44.  
  45.                 //parent 指向 child 位置，向下调整至下方无子树
  46.                 parent = child;
  47.                 child = parent*2 + 1;
  48.             } else {
  49.                 //子结点都比父结点小
  50.                 break;
  51.             }
  52.         }
  53.     }
  54.     //交换元素
  55.     private static void swap(int[] array, int i, int j) {
  56.         int temp = array[i];
  57.         array[i] = array[j];
  58.         array[j] = temp;
  59.     }

【总结】 

时间复杂度：O(n*log n)

空间复杂度：O(1)

稳定性：不稳定

四、交换排序

4.1 冒泡排序

核心思想：进行 array.length-1 趟比较，每次确定一个最大值元素。

  1.     public static void bubbleSort(int[] array) {
  2.         //i 表示趟数
  3.         for (int i = 0; i < array.length-1; i++) {
  4.             //设置一个标签，检测该趟是否发生交换
  5.             boolean flag = false;
  6.  
  7.             //j 表示该趟比较次数
  8.             for (int j = 0; j < array.length-1-i; j++) {
  9.                 //每趟确定一个最大值
  10.                 if (array[j] > array[j+1]) {
  11.                     int temp = array[j];
  12.                     array[j] = array[j+1];
  13.                     array[j+1] = temp;
  14.                     //若交换，则改变标签状态
  15.                     flag = true;
  16.                 }
  17.             }
  18.             //若标签状态未改变，则序列已经有序
  19.             if (!flag) {
  20.                 break;
  21.             }
  22.         }
  23.     }

【总结】

时间复杂度：O(n^2)，若加上 flag 优化，则最好可以达到 O(n)

空间复杂度：O(1)

稳定性：稳定

4.2 快速排序

1、Hoare版

核心思想：以 0 下标元素为基准，保证每次排序后，基准左侧元素小于基准，右侧大于基准，分别在左序列与右序列进行递归排序。

  1.     public static void quickSort(int[] array) {
  2.           quick(array, 0, array.length-1);
  3.     }
  4.  
  5.     private static void quick(int[] array, int start, int end) {
  6.         // start < end 时才需要排序
  7.         if (start >= end) {
  8.             return;
  9.         }
  10.  
  11.         //找到基准的下标
  12.         int pivot = partitionHoare(array, start, end);
  13.  
  14.         //左序列
  15.         quick(array, start, pivot-1);
  16.         //右序列
  17.         quick(array, pivot+1, end);
  18.     }
  19.  
  20.     private static int partitionHoare(int[] array, int left, int right) {
  21.         //保存基准的值
  22.         int temp = array[left];
  23.         //保存基准的下标
  24.         int index = left;
  25.  
  26.         while (left < right) {
  27.             //在右侧找到比基准小的数
  28.             while (left < right && array[right] >= temp) {
  29.                 right--;
  30.             }
  31.             //在左侧找到比基准小的数
  32.             while (left < right && array[left] <= temp) {
  33.                 left++;
  34.             }
  35.             swap(array, left, right);
  36.         }
  37.         //保证基准左侧都比基准小，右侧都比基准大
  38.         swap(array, index, left);
  39.         //确定基准的位置时，left = right
  40.         return left;
  41.     }

2、挖坑版

核心思想：以 0 下标元素为基准，0 下标处为第一个坑位，从右侧开始遍历，找到比基准小的元素放至 left 下标 (初始即 0 下标) 处；然后从左侧遍历到比基准大的放至 right 下标处，循环至 left 与 right 相遇，将基准放入最后一个坑位。

  1.     public static void quickSort(int[] array) {
  2.           quick(array, 0, array.length-1);
  3.     }
  4.  
  5.     private static void quick(int[] array, int start, int end) {
  6.         // start < end 时才需要排序
  7.         if (start >= end) {
  8.             return;
  9.         }
  10.  
  11.         //找到基准的下标
  12.         int pivot = partition(array, start, end);
  13.  
  14.         //左序列
  15.         quick(array, start, pivot-1);
  16.         //右序列
  17.         quick(array, pivot+1, end);
  18.     }
  19.  
  20.     private static int partition(int[] array, int left, int right) {
  21.         //保存基准的值
  22.         int temp = array[left];
  23.         //保存基准的下标
  24.         int index = left;
  25.  
  26.         while (left < right) {
  27.             //在右侧找到比基准小的数
  28.             while (left < right && array[right] >= temp) {
  29.                 right--;
  30.             }
  31.             //找到放置左边的坑位
  32.             array[left] = array[right];
  33.  
  34.             //在左侧找到比基准小的数
  35.             while (left < right && array[left] <= temp) {
  36.                 left++;
  37.             }
  38.             //找到放置右边的坑位
  39.             array[right] = array[left];
  40.         }
  41.         //将基准值放入最后一个坑中
  42.         array[left] = temp;
  43.         //确定基准的位置时，left = right
  44.         return left;
  45.     }

【总结】 

时间复杂度：O(n*log n)

空间复杂度：O(log n)

稳定性：不稳定

五、归并排序

将两个有序序列合并成一个有序序列的操作，称为二路归并。

核心步骤：先分解再合并。

  1.     public static void mergeSort(int[] array) {
  2.         merge(array, 0, array.length-1);
  3.     }
  4.  
  5.     private static void merge(int[] array, int start, int end) {
  6.         // start < end 时才需要排序
  7.         if (start >= end) {
  8.             return;
  9.         }
  10.  
  11.         //标记序列中间下标
  12.         int mid = (start+end)/2;
  13.         //左序列
  14.         merge(array, start, mid);
  15.         //右序列
  16.         merge(array, mid+1, end);
  17.  
  18.         //排序, 合并
  19.         mergeMethod(array, start, mid, end);
  20.     }
  21.  
  22.     private static void mergeMethod(int[] array, int left,int mid, int right) {
  23.         //指向左右序列最小值
  24.         int min1 = left;
  25.         int min2 = mid+1;
  26.  
  27.         //定义一个新的空间用于排序
  28.         int[] sort = new int[right-left+1];
  29.         //新空间的下标
  30.         int k = 0;
  31.  
  32.         //保证左右序列都有元素
  33.         while (min1 <= mid && min2 <= right) {
  34.             //左右序列从最左侧(最小值)开始比较
  35.             if (array[min1] <= array[min2]) {
  36.                 sort[k++] = array[min1++];
  37.             } else {
  38.                 sort[k++] = array[min2++];
  39.             }
  40.         }
  41.  
  42.         //表示右序列中无元素，即左序列剩下元素比右序列都要大
  43.         while (min1 <= mid) {
  44.             sort[k++] = array[min1++];
  45.         }
  46.         //表示左序列中无元素，即右序列剩下元素比左序列都要大
  47.         while (min2 <= right) {
  48.             sort[k++] = array[min2++];
  49.         }
  50.  
  51.         //将排序好的数组，拷贝回原数组
  52.         for (int i = 0; i < sort.length; i++) {
  53.             //利用 left 下标(每个序列起始下标) 保证右序列可以顺利拷贝
  54.             array[i+left] = sort[i];
  55.         }
  56.     }

【总结】 

时间复杂度：O(n*log n)

空间复杂度：O(n)

稳定性：稳定

适用性：更多是在解决磁盘中的外排序问题

六、排序算法分析

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

总结

1、希尔排序是对直接插入排序的优化。

2、直接选择排序效率不高，很少使用；堆排序效率高。

3、快速排序综合性能和使用场景都是比较好的。

4、归并排序更多是在解决磁盘中的外排序问题。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/木道寻08/article/detail/856647
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号