• 数据结构_排序总结

    目录

    1.插入排序

    2.希尔排序

    3.选择排序

    4.堆排序

    5.冒泡排序

    6.快速排序

    7.归并排序

    8.计数排序

    1.插入排序

    1. //插入排序
    2.     /**
    3.      * 时间复杂度：最坏 即逆序情况：O（N^2） 最好：即有序情况O（N）
    4.      * 因此当数据不太多，且接近有序时，直接插入排序效率很高
    5.      * 空间复杂度：随着问题规模的扩大并没有扩展空间，因此空间复杂度为O（1）
    6.      * 稳定性：稳定
    7.      * @param arr
    8.      * @return
    9.      */
    10.     public static void insertSort(int[] arr){
    11.         if(arr.length==0){
    12.             return ;
    13.         }
    14.         int currentValue = 0;//存放当前需要比较插入的值
    15.         for (int i = 0; i < arr.length-1; i++) {
    16.             int preIndex = i;
    17.             currentValue = arr[preIndex+1];
    18.             while(preIndex >= 0 && arr[preIndex] > currentValue){
    19.                 arr[preIndex+1] = arr[preIndex];
    20.                 preIndex--;
    21.             }
    22.             //找到插入的位置
    23.             arr[preIndex+1] = currentValue;
    24.         }
    25.     }
    26.     public static void insertSort1(int[] array){
    27.         for (int i = 1; i < array.length; i++) {
    28.             int j = i-1;
    29.             int tmp = array[i];
    30.             for (; j >= 0 ; j--) {
    31.                 if(array[j] > array[i]){
    32.                     array[j+1] = array[j];
    33.                 }
    34.                 else{
    35.                     break;
    36.                 }
    37.             }
    38.             array[j+1] = tmp;
    39.         }
    40.     }

    2.希尔排序

    1. //shell排序
    2.  
    3.     /**
    4.      * 当增量大于1时，都是进行预排序，gap=1时进行直接插入排序
    5.      * 也是对插入排序的优化
    6.      * 时间复杂度为O（N^1.3）
    7.      * @param arr
    8.      */
    9.     public void shellSort(int[] arr){
    10.         int gap = arr.length;
    11.         while(gap > 1){
    12.             gap /= 2;
    13.             shell(arr,gap);
    14.         }
    15.     }
    16.     public static void shell(int[] arr,int gap){
    17.  
    18.         //这里换成i += gap也能排序，只是并没有完成预排序
    19.         // 是因为无论预排序是几轮
    20.         // 最后gap都会为1进行插入排序
    21.         for (int i = gap; i < arr.length; i++) {
    22.             int tmp = arr[i];
    23.             int j = i-gap;
    24.             for (; j >= 0 ; j-=gap) {
    25.                 if(arr[j] > tmp){
    26.                     arr[j+gap] = arr[j];
    27.                 }
    28.                 else{
    29.                     break;
    30.                 }
    31.             }
    32.             arr[j+gap] = tmp;
    33.         }
    34.     }

    3.选择排序

    1.  //选择排序
    2.     /*
    3.     时间复杂度：O（N^2）
    4.      */
    5.     public  static void selectSort(int[] array){
    6.         int minIndex = 0;
    7.         for (int i = 0; i < array.length; i++) {
    8.             //最小值的下标
    9.             minIndex = i;
    10.             for (int j = i+1; j < array.length; j++) {
    11.                 if(array[j] < array[i]){
    12.                     //更新
    13.                     minIndex = j;
    14.                 }
    15.             }
    16.             //如果最小值下标存的还是i，则说明确实是最小值，没有进行下标的交换
    17.             //当i != minIndex时，要进行交换i位置的值和min位置的值
    18.             if(i != minIndex){
    19.                 swap(array,minIndex,i);
    20.             }
    21.         }
    22.     }
    23.     //优化
    24.     public static void selectSort1(int[] array){
    25.         int left = 0;
    26.         int right = array.length-1;
    27.         while(left<right){
    28.             int minIndex = left;
    29.             int maxIndex = right;
    30.             //每次交换完区间会更新
    31.             for (int i = left+1; i <= right; i++) {
    32.                 if(array[i] > array[maxIndex]){
    33.                     maxIndex = i;
    34.                 }
    35.                 if(array[i] < array[minIndex]){
    36.                     minIndex = i;
    37.                 }
    38.             }
    39.             //交换
    40.             swap(array,minIndex,left);
    41.             //当maxIndex为left时，最小值会和left交换，最大值就被交换走了
    42.             //因此最小值交换后，要更新最大值maxindex，才能将正确的最大值换到right处
    43.  
    44.             if(maxIndex == left){
    45.                 maxIndex = minIndex;
    46.             }
    47.             swap(array,maxIndex,right);
    48.             //更新
    49.             left++;
    50.             right--;
    51.         }
    52.     }
    53.     //交换函数
    54.     public static void swap(int[] array,int i,int j){
    55.         int tmp = array[i];
    56.         array[i] = array[j];
    57.         array[j] = tmp;
    58.     }

    4.堆排序

    1. //堆排序
    2.     //时间复杂度：N(n*log(2(N)))
    3.     //空间复杂度O（1）
    4.     //稳定性：不稳定
    5.     public static void heapSort(int[] array){
    6.         //建立大根堆
    7.         creatBigheap(array);
    8.         int end = array.length-1;
    9.         while(end>0){
    10.             swap(array,0,end);
    11.             shiftDown(array,0,end);
    12.             end--;
    13.         }
    14.  
    15.     }
    16.     private static void creatBigheap(int[] array){
    17.         for (int parent = (array.length-1-1)/2; parent >=0 ; parent--) {
    18.             shiftDown(array,parent,array.length);
    19.         }
    20.     }
    21.     private static void shiftDown(int[] array,int parent,int len){
    22.         int child = (2*parent)+1;
    23.         while(child<len){
    24.             if(child + 1 < len && array[child] < array[child+1]){
    25.                 child++;
    26.             }
    27.             if(array[child] > array[parent]){
    28.                 swap(array,parent,child);
    29.                 parent = child;
    30.                 child = (2*parent)+1;
    31.             }else{
    32.                 break;
    33.             }
    34.         }
    35.     }

    5.冒泡排序

    1. /**
    2.      * 冒泡排序
    3.      * 时间复杂度 不优化O（N^2）
    4.      * 优化: O（N）
    5.      * 空间复杂度 : O（N）
    6.      * 稳定性: 稳定
    7.      * @param array
    8.      */
    9.     public static void bubbleSort(int[] array){
    10.         for (int i = 0; i < array.length-1; i++) {
    11.             boolean flag = false;
    12.             for (int j = 0; j < array.length-1-i; j++) {
    13.                 if(array[j] > array[j+1]){
    14.                     swap(array,j,j+1);
    15.                     flag = true;
    16.                 }
    17.             }
    18.             if(flag ==false){
    19.                 break;
    20.             }
    21.         }
    22.     }

    6.快速排序

    1. /*
    2.     快速排序
    3.      */
    5.     /**
    6.      * 时间复杂度：O（N*log（N））
    7.      * 空间复杂度：O（log（N））
    8.      * 稳定性:不稳定
    9.      * 当数据有序时，时间复杂度O（N^2）空间复杂度O（N）
    10.      * @param array
    11.      */
    12.     public static void quickSort(int[] array){
    13.         sort(array,0, array.length-1);
    14.     }
    15.     private static void sort(int[] array,int start,int end){
    16.         //防止只有左子树或者右子树的情况
    17.         if(start >= end){
    18.             return;
    19.         }
    20.         int povit = partion(array,start,end);
    21.         sort(array,start,povit-1);
    22.         sort(array,povit+1,end);
    23.     }
    24.     private static int partion(int[] array,int left,int right){
    25.         //记录原始位置下标，方便后面和povit位置交换
    26.         int i = left;
    27.         //寻找参考值
    28.         int povit = array[i];
    29.         while(left<right){
    30.             /**
    31.              * 问题1：为什么先从right 向左找？
    32.              * 从右边开始找基准位置，是因为从左边开始找，左边先找到一个比array[left]大的数，然后右边
    33.              * 向左找，左右肯定相遇，这时候交换，会把比基准值大的数交换到基准位置左边，达不到二分的目的了
    34.              *
    35.              * 问题2：为什么左右数组值比较时要带等于号？
    36.              * 如果出现两边开始时值相同的情况，即左值不小于也不大于右值，两个循环都不会进去
    37.              * 只会完成左右值一直交换，死循环了
    38.              */
    39.  
    40.             while(left < right && array[left] <= array[right]){ //单独的循环，防止循环内一直到left>right，要加条件
    41.                 right--;
    42.             }
    43.             while(left < right && array[left] >= array[right]){
    44.                 left++;
    45.             }
    46.             //交换
    47.             swap(array,left,right);
    48.         }
    49.         //交换povit到相遇的位置
    50.         swap(array,left,i);
    51.         return left;
    52.     }
    53.  
    54.     //挖坑法找基准
    55.     private static int paration1(int[] array,int left,int right){
    56.         int povit = array[left];
    57.         while(left<right){
    58.             while (left < right && array[right] >= povit) {
    59.                 right--;
    60.             }
    61.             array[left] = array[right];
    62.             while(left < right && array[left] <= povit){
    63.                 left++;
    64.             }
    65.             array[right] = array[left];
    66.         }
    67.         array[left] = povit;
    68.         return left;
    69.     }
    70.     //前后指针找基准
    71.     private static int paration2(int[] array,int left,int right){
    72.         int prev = left;
    73.         int cur = left+1;
    74.         while(cur <= right){
    75.             if(array[cur] < array[left] && array[++prev] != array[cur]){
    76.                 swap(array,prev,cur);
    77.             }
    78.             cur++;
    79.         }
    80.         swap(array,prev,left);
    81.         return prev;
    82.     }
    83.     /**
    84.      * 一般情况下题目中所给到的都是挖坑法划分出来的序列
    85.      * 如果不是，再尝试其他的两种方法划分出来的序列
    86.      */
    87. //快速排序的优化1：
    88.     /*
    89.     当数据接近有序或有序的时候，快速排序的时间复杂度达到最大，空间复杂度也非常大了，可能会栈溢出
    90.     使用三数取中法优化
    91.  
    92.     在找基准之前，解决划分不均匀的问题
    93.      */
    94.     private static void sort1(int[] array,int start,int end){
    95.         //防止只有左子树或者右子树的情况
    96.         if(start >= end){
    97.             return;
    98.         }
    99.         //在找基准之前，解决划分不均匀的问题,将关键值改变为中间大小的值后，能解决单分支的情况
    100.         int index = findMidValOfIndex(array,start,end);
    101.         swap(array,start,index);
    102.  
    103.         int povit = partion(array,start,end);
    104.         sort(array,start,povit-1);
    105.         sort(array,povit+1,end);
    106.     }
    107.     /*
    108.     找到中位数
    109.      */
    110.     private static int findMidValOfIndex(int[] array,int start,int end){
    111.         int midIndex = (start+end)/2;
    112.  
    113.         if(array[start] < array[end]){
    114.             if(array[midIndex] < array[start]) {
    115.                 return start;
    116.             } else if (array[end] < array[midIndex]) {
    117.                 return end;
    118.             }
    119.             else {
    120.                 return midIndex;
    121.             }
    122.         }
    123.         else {
    124.             if (array[midIndex] > array[start]){
    125.                 return start;
    126.             } else if (array[midIndex] < array[end]) {
    127.                 return end;
    128.             }
    129.             else {
    130.                 return midIndex;
    131.             }
    132.         }
    133.     }
    134. //快速排序的优化2：
    135.     /*
    136.     当递归的区间很小的时候我们可以用插入排序，二叉树后几层节点数占总体节点数的大部分，
    137.     递归次数最多也发生在后几层，往后也越来越有序，就不递归了。用插入排序
    138.      */
    139.     private static void sort2(int[] array,int start,int end){
    140.         //防止只有左子树或者右子树的情况
    141.         if(start >= end){
    142.            return;
    143.         }
    144.         if(( end-start+1) <= 15){
    145.         //插入排序减少后几层 的递归
    146.             insertSort1(array,start,end);
    147.         }
    148.         //在找基准之前，解决划分不均匀的问题,将关键值改变为中间大小的值后，能解决单分支的情况
    149.         int index = findMidValOfIndex(array,start,end);
    150.         swap(array,start,index);
    151.  
    152.         int povit = partion(array,start,end);
    153.         sort(array,start,povit-1);
    154.         sort(array,povit+1,end);
    155.     }
    156.     public static void insertSort1(int[] array,int left,int right){
    157.         for (int i = left+1; i <= right ; i++) {
    158.             int j = i-1;
    159.             int tmp = array[i];
    160.             for (; j >= left ; j--) {
    161.                 if(array[j] > array[i]){
    162.                     array[j+1] = array[j];
    163.                 }
    164.                 else{
    165.                     break;
    166.                 }
    167.             }
    168.             array[j+1] = tmp;
    169.         }
    170.     }

    7.归并排序

    1.  //归并排序递归写法
    2.     /*
    3.     时间复杂度:O(n*log(n))
    4.     空间复杂度:O(n)
    5.     稳定性:稳定
    6.     还有:插入 , 冒泡 , 归并
    7.      */
    8.     //1.递归
    9.     public static void mergeSort(int[] array){
    10.         mergeSortChild(array,0,array.length-1);
    11.     }
    12.     private static void  mergeSortChild(int[] array,int left,int right){
    13.         if(left == right){
    14.             return;
    15.         }
    16.         //分解
    17.         int mid = (left+right)/2;
    18.         mergeSortChild(array,left,mid);
    19.         //先递归左边,当左边都递归完成,会返回一个array中放的是tmpArr的值
    20.         //递归右边结束,array[i] = arrTmp[i] 又会从0开始赋值,是错误的.
    21.         //array[i+left] = tmpArr[i];可以避免错误,左边left =0相当于没有调整,右边left改变,进行调整正确赋值
    22.         mergeSortChild(array,mid+1,right);
    23.         //合并
    24.         merge(array,left,mid,right);
    25.     }
    26.  
    27.     private static void merge(int[] array,int left,int mid,int right){
    28.         int s1 = left;
    29.         int e1 = mid;
    30.         int s2 = mid+1;
    31.         int e2 = right;
    32.         int k = 0;//tmpArr下标
    33.         int[] tmpArr = new int[right-left+1];
    34.         while (s1 <= e1 && s2 <= e2){
    35.             if(array[s1] <= array[s2]){
    36.                 tmpArr[k] = array[s1];
    37.                 k++;
    38.                 s1++;
    39.             }
    40.             else {
    41.                 tmpArr[k] = array[s2];
    42.                 k++;
    43.                 s2++;
    44.             }
    45.         }
    46.         while(s1 <= e1){
    47.             tmpArr[k] = array[s1];
    48.             k++;
    49.             s1++;
    50.         }
    51.         while(s2 <= e2){
    52.             tmpArr[k] = array[s2];
    53.             k++;
    54.             s2++;
    55.         }
    56.         //转换
    57.         //递归右边结束,array[i] = arrTmp[i] 又会从0开始赋值,是错误的.
    58.         //array[i+left] = tmpArr[i];
    59.         // 可以避免错误,左边left =0相当于没有调整,右边left改变,进行调整正确赋值
    60.         for (int i = 0; i < tmpArr.length; i++) {
    61.             array[i+left] = tmpArr[i];
    62.         }
    63.     }
    64.  
    65.     //归并非递归写法
    66.     //有了合并的函数,只需要研究怎样分解这个数组后调用合并函数合并即可
    67.     public static void mergeSort2(int[] array){
    68.         int gap = 1;
    69.         while(gap < array.length){
    70.             for (int i = 0; i < array.length; i+=gap*2) {
    71.                 int left = i;
    72.                 int mid = left + gap -1;
    73.                 int right = mid + gap;
    74.                 //mid和right在有些情况下会越界
    75.                 if(mid >= array.length){
    76.                     mid = array.length-1;
    77.                 }
    78.                 if(right >= array.length){
    79.                     right = array.length-1;
    80.                 }
    81.                 merge(array,left,mid,right);
    82.             }
    83.  
    84.             gap = gap*2;
    85.  
    86.  
    87.         }
    88.     }

    8.计数排序

    1. public static void countSort(int[] array){
    2.        //1.找到最大最小值
    3.         int maxVal = array[0];
    4.         int minVal = array[0];
    5.         for (int i = 0; i < array.length; i++) {
    6.             if(array[i] > maxVal){
    7.                 maxVal = array[i];
    8.             }
    9.             if(array[i] < minVal){
    10.                 minVal = array[i];
    11.             }
    12.         }
    13.         //2.创建计数数组
    14.         int len = maxVal-minVal +1 ;
    15.         int[] countArr = new int[len];
    16.         //3.遍历数组
    17.         for (int i = 0; i < array.length; i++) {
    18.             int val = array[i];
    19.             countArr[val-minVal]++;
    20.         }
    21.         //4.覆盖
    22.         int index = 0;
    23.         for (int i = 0; i < countArr.length; i++) {
    24.             while(countArr[i] > 0){
    25.                 array[index] = i+minVal;
    26.                 countArr[i]--;
    27.                 index++;
    28.             }
    29.         }
    30.     }

  • 相关阅读:
    边坡安全监测系统的功能优势
    Linux 本地RStudio 工具安装&远程访问
    第九章 APP项目测试（3） 测试工具
    Apache网页优化
    【Wio Terminal】使用WiFi（3）- Wi-F的高级使用
    Windows10系统 无法更换锁屏图片一直转圈圈（含替换系统默认锁屏壁纸教程）异常处理
    高复用性自动化脚本设计实践
    Java当中的队列
    DS 顺序表--类实现（C++数据结构题）
    gRPC（七）进阶：自定义身份验证
  • 原文地址：https://blog.csdn.net/chenchenchencl/article/details/127795998