devbox
菜鸟追梦旅行
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

八大排序之图文详解

作者：菜鸟追梦旅行 | 2024-05-20 06:34:47

赞

踩

八大排序之图文详解

前言 

在数据结构中，排序是非常重要的内容，也是未来面试和笔试的重点。

本文代码是Java

目录

前言 

一、插入排序

 （一）直接插入排序

（二）希尔排序

二、选择排序

（一）选择排序

（二）堆排序

三、交换排序

（一）冒泡排序

（二）快速排序

四、归并排序

（一）归并排序

五、计数排序

六、其他排序

结语

一、插入排序

 （一）直接插入排序

将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表。

适用于顺序表、链表

排序过程如下：

 代码：

  1. public static void InlineSort(int[] arr){
  2.         for (int i = 1; i < arr.length; i++) {
  3.             if(arr[i] < arr[i-1]){
  4.                 int tmp = arr[i];
  5.                 int j = i-1;
  6.                 for (; j >= 0; j--) {
  7.                     if(arr[j]>tmp){
  8.                         arr[j+1] = arr[j];
  9.                     }else{
  10.                         break;
  11.                     }
  12.                 }
  13.                 arr[j+1] = tmp;
  14.             }
  15.         }
  16.     }

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

空间复杂度：O(1)

稳定性：稳定

（二）希尔排序

仅适用于顺序表，不适用于链表

记录按下标的一定增量分组，对每组使用直接插入排序算法排序

排序过程如下：

 代码：

  1. public static void shellSort(int[] arr){
  2.         int len = arr.length;
  3.         int d = len/2;//组数，数据之间的间距
  4.         while(d >= 1){
  5.             for(int i = 0; i < d; i++){
  6.                 for (int j = i+d; j < len; j+=d) {
  7.                     int tmp = arr[j];
  8.                     int k = j-d;
  9.                     for (; k >= 0; k-=d) {
  10.                         if(tmp < arr[k]){
  11.                             arr[k+d] = arr[k];
  12.                         }else{
  13.                             break;
  14.                         }
  15.                     }
  16.                     arr[k+d] = tmp;
  17.                 }
  18.             }
  19.             d /= 2;
  20.         }
  21.     }

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

空间复杂度：O(1)

稳定性：不稳定

二、选择排序

（一）选择排序

在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

顺序表和链表都适用

排序过程：

代码：

  1. public static void selectSort(int[] arr){
  2.         int left = 0;
  3.         int right = arr.length-1;
  4.         while(left < right){
  5.             int min = left;
  6.             int max = right;
  7.             for (int i = left; i <= right; i++) {
  8.                 if(arr[i] < arr[min]){
  9.                     min = i;
  10.                 }
  11.                 if(arr[i] > arr[max]){
  12.                     max = i;
  13.                 }
  14.             }
  15.             //交换
  16.             swap(arr,min,left);
  17.             if(left == max){
  18.                 max = min;
  19.             }
  20.             swap(arr,max,right);
  21.             left++;
  22.             right--;
  23.         }
  24.     }
  25.     //交换
  26.     public static void swap(int[] arr, int s1, int s2) {
  27.         int tmp = arr[s1];
  28.         arr[s1] = arr[s2];
  29.         arr[s2] = tmp;
  30.     }

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

空间复杂度：O(1)

稳定性：不稳定

该排序与数据是否有序无关

（二）堆排序

建立大根堆 -> 把堆顶与最末尾元素交换，直到建立有序的小根堆

排序过程：

 代码：

  1.     public static void heapSort(int[] arr){
  2.         //使arr成为大根堆
  3.         int len = arr.length;
  4.         for (int i = (len-1-1)/2; i >= 0; i--) {
  5.             shiftDown(arr, i, len-1);
  6.         }
  7.         while(len > 0){
  8.             //将堆顶与堆末尾交换
  9.             swap(arr,0,len-1);
  10.             len--;
  11.             shiftDown(arr,0,len-1);
  12.         }
  13.     }
  14.     //向下调整
  15.     public static void shiftDown(int[] arr, int parent, int k){
  16.         int child = parent*2+1;
  17.         while(child <= k){
  18.             if(child+1<=k && arr[child+1]>arr[child]){
  19.                 child++;
  20.             }
  21.             if(arr[child] > arr[parent]){
  22.                 swap(arr,parent,child);
  23.                 parent = child;
  24.                 child = parent*2+1;
  25.             }else{
  26.                 break;
  27.             }
  28.         }
  29.     }
  30.     //交换
  31.     public static void swap(int[] arr, int s1, int s2){
  32.         int tmp = arr[s1];
  33.         arr[s1] = arr[s2];
  34.         arr[s2] = tmp;
  35.     }

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

空间复杂度：O(1)

稳定性：不稳定

该排序与数据是否有序无关

三、交换排序

（一）冒泡排序

比较相邻的元素。如果第一个比第二个大，就交换他们两个

顺序表和链表都适用

排序过程：

代码： 

  1.     public static void bubbleSort(int[] arr){
  2.         int len = arr.length;
  3.         for (int i = 0; i < len-1; i++) {
  4.             boolean ret = true;
  5.             for (int j = 0; j < len-i-1; j++) {
  6.                 if(arr[j] > arr[j+1]){
  7.                     swap(arr, j, j+1);
  8.                     ret = false;
  9.                 }
  10.             }
  11.             if(ret == true){
  12.                 break;
  13.             }
  14.         }
  15.     }
  16.     public static void swap(int[] arr, int s1, int s2){
  17.         int tmp = arr[s1];
  18.         arr[s1] = arr[s2];
  19.         arr[s2] = tmp;
  20.     }

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

空间复杂度：O(1)

稳定性：稳定

该排序与数据是否有序无关

（二）快速排序

本文讲解挖坑法

顺序表和链表都适用

  • 以第一个元素为基准，存储在tmp当中，设置l和r两个下标，寻找比tmp小/大的元素，
  • 先和tmp交换，再互相交换，直到r和l相等或者r小于l，tmp存储的数值赋值给r指向的下标的位置
  • 此时r指向的下标位置把该数据分为两部分，再把这两部分按照上面的步骤进行排序，直到每一个部分只有一个元素或零个元素为止

 代码：

  1.     public static void quickSort(int[] arr){
  2.         quickSortFunc2(arr,0,arr.length-1);
  3.     }
  4.     //基准 左右不断递归
  5.     public static void quickSortFunc2(int[] arr, int left, int right){
  6.         //出递归条件
  7.         if(left >= right) return;
  8.         //优化 当left right中间数字较少时，进行直插
  9.         if(right-left+1 <= 7){
  10.             insertSort(arr,left,right);
  11.             return;
  12.         }
  13.         //基准下标
  14.         int index = quickSortFunc1(arr,left,right);
  15.         quickSortFunc2(arr,left,index-1);
  16.         quickSortFunc2(arr,index+1,right);
  17.     }
  18.     //直插
  19.     public static void insertSort(int[] arr,int left1, int right1){
  20.         for (int i = left1+1; i <= right1; i++) {
  21.             int tmp = arr[i];
  22.             //最左边下标
  23.             int left = 0;
  24.             //最右边下标
  25.             int right = i-1;
  26.             while(left <= right){
  27.                 int mid = (left+right)/2;
  28.                 if(tmp < arr[mid]){
  29.                     right = mid-1;
  30.                 }else{
  31.                     left = mid+1;
  32.                 }
  33.             }
  34.             for (int j = i-1; j >= right+1; j--) {
  35.                 arr[j+1] = arr[j];
  36.             }
  37.             arr[right+1] = tmp;
  38.         }
  39.     }
  40.     //找基准，划分基准左右
  41.     public static int quickSortFunc1(int[] arr, int left, int right){
  42.         int mid = (left+right)/2;
  43.         int index = mid;
  44.         if(arr[left] < arr[right]){
  45.             if(arr[mid] < arr[left]){
  46.                 index = left;
  47.             }else if(arr[mid] > arr[right]){
  48.                 index = right;
  49.             }
  50.         }else{
  51.             if(arr[mid] < arr[right]){
  52.                 index = right;
  53.             }else if(arr[mid] > arr[left]){
  54.                 index = left;
  55.             }
  56.         }
  57.         swap(arr,index,left);
  58.         int tmp = arr[left];
  59.         while (left < right){
  60.             while(left < right && arr[right] >= tmp){
  61.                 right--;
  62.             }
  63.             arr[left] = arr[right];
  64.             while(left < right && arr[left] <= tmp){
  65.                 left++;
  66.             }
  67.             arr[right] = arr[left];
  68.         }
  69.         arr[left] = tmp;
  70.         return left;
  71.     }
  72.     //交换
  73.     public static void swap(int[] arr, int s1, int s2){
  74.         int tmp = arr[s1];
  75.         arr[s1] = arr[s2];
  76.         arr[s2] = tmp;
  77.     }

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

空间复杂度：O(log n)

稳定性：不稳定

四、归并排序

（一）归并排序

代码：

  1.     public static void mergeSort(int[] arr){
  2.         mergeSortFunc1(arr,0,arr.length-1);
  3.     }
  4.  
  5.     //合并
  6.     public static void mergeSortFunc1(int[] arr, int left,int right){
  7.         if(left>=right) return;
  8.         int mid = (right+left)/2;
  9.         mergeSortFunc1(arr,left,mid);
  10.         mergeSortFunc1(arr,mid+1,right);
  11.         mergeSortFunc2(arr,left,mid,right);
  12.     }
  13.     //插入
  14.     public static void mergeSortFunc2(int[] arr,int left, int mid, int right){
  15.         int[] arr1 = new int[right-left+1];
  16.         int i = 0;
  17.         int tmp =left;
  18.         int left2 = mid+1;
  19.         while(left<=mid && left2<=right){
  20.             if(arr[left] < arr[left2]){
  21.                 arr1[i++] = arr[left++];
  22.             }else{
  23.                 arr1[i++] = arr[left2++];
  24.             }
  25.         }
  26.         while(left<=mid){
  27.             arr1[i++] = arr[left++];
  28.         }
  29.         while(left2<=right){
  30.             arr1[i++] = arr[left2++];
  31.         }
  32.  
  33.         for (int j = 0; j < i; j++) {
  34.             arr[tmp+j] = arr1[j];
  35.         }
  36.     }

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

空间复杂度：O(n)

稳定性：稳定

该排序与数据是否有序无关

五、计数排序

  1. 统计相同元素出现次数
  2. 根据统计的结果将序列回收到原来的序列

代码：

  1. public static void CountSort(int[] arr){
  2.         int min = arr[0];
  3.         int max = arr[0];
  4.         for (int i = 1; i < arr.length; i++) {
  5.             if(arr[i] < min){
  6.                 min=arr[i];
  7.             }
  8.             if(arr[i] > max){
  9.                 max = arr[i];
  10.             }
  11.         }
  12.         int[] arr1 = new int[max-min+1];
  13.  
  14.         for (int i = 0; i < arr.length; i++) {
  15.             arr1[arr[i]-min]++;
  16.         }
  17.         int k = 0;
  18.         for (int i = 0; i < arr1.length; i++) {
  19.             while(arr1[i]-- > 0){
  20.                 arr[k++] = min+i;
  21.             }
  22.         }
  23.     }

六、其他排序

基数排序（无比较排序）：

创建十个的队列(依次代表 0 1 2 3 4 5 6 7 8 9），从所有数据的最高位开始入队列再出队列，直到根据个位数的数据完成出队列时，总数据完成排序。

 桶排序：

创建对应的桶，桶内排序。

结语

本文排序都是递归写法，如果对非递归写法有兴趣了解，可以点击Yjun6/DataStructrue: data_structrue (github.com)

排序有很多，期待我们下次再见！

小编能力有限，有问题和疑惑评论区见哦~

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

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

  

闽ICP备14008679号