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

【数据结构】七大排序算法（超详细）_数据结构排序

作者：不正经 | 2024-02-29 05:18:29

赞

踩

数据结构排序

  欢迎来到南方有乔木的博客！！！

博主主页：点击点击！戳一戳！！

博主名:南方有乔木

博主简介：

一名在校大学生，正在努力学习Java语言编程。穷且意坚，不坠青云之志，希望能在编程的世界里找到属于自己的光。

跪谢帅气or美丽的朋友们能够帮我点赞! 请对文中内容请多多指教！！！

​

目录

一.排序算法简介

1.内部排序

2.外部排序

二.排序算法的分类

三.七大排序算法的实现

1.冒泡排序（交换排序之一）

 2.快速排序（交换排序之一）

 3.直接选择排序（选择排序之一）

4.堆排序（选择排序之一）

5.直接插入排序（插入排序之一）

6.希尔排序（插入排序之一）

7.归并排序

一.排序算法简介

排序的定义：

排序就是将一组无序的数据排序成有序的序列的操作。

排序分类：

1.内部排序

内部排序是指待排序序列全部存放在内存中的进行的排序过程。这种方法适用于数量不大的数据元素的排序。

2.外部排序

外部排序是指需要排序的数据非常的多，它们必须存储在外部的存储器上，这种排序的过程需要访问外部存储器，这种排序就是外部排序。

排序的稳定性

概念：

对于一组数据元素序列，使用某种排序算法对它进行排序，若相同数据之间的前后位置排序后和未排序之前是相同的，我们就称这种排序算法是具有稳定性的。

比如 关键字序列：

1，5a，3，7，5b，9，12

这个序列中有两个5，我们将第一个数字记成5a，第二个5记为5b,若排序后：

1，3，5a，5b，7，9，12

5a还是在5b之前，相对位置不变，称排序所用的算法具有稳定性

若排序后：

1，3，5b，5a，7，9，12

5b变到了5a之前，相对位置发生变化，则称排序的算法不具有稳定性。

二.排序算法的分类

常见的七大基于比较的排序算法一共有七种，分别是，冒泡排序

直接选择排序，希尔排序，快速排序，堆排序，直接插入排序，归并排序。

分类示意图：

根据它们的特性这七种算法又被分成了四类

1.选择排序：直接选择排序，堆排序

2.插入排序：直接插入排序，希尔排序

3.交换排序：冒泡排序，快速排序

4.归并排序：归并排序

三.七大排序算法的实现

1.冒泡排序（交换排序之一）

示意图：

原理：

在无序区间中，将两两相邻的元素进行比较，每一轮比较出最大的一个元素，交换到有序区间。

步骤：

1.冒泡排序的主要思想是两两比较，因此先确定要比较多少次，因为前面经过比较只剩最后一个元素的时候，最后一个元素必定已经有序，因此，如果有n个元素，只需要比较n-1次。

2.进行两两比较的过程，从第一个元素开始，把它与它两两相邻的元素比较，把大的换到右边，一直比较，直到把数组里最大的元素换到最右边，因为只需要比较到倒数第二个元素的时候，它与倒数第一个元素比较已经可以换到最右边，因此下标只需要到数组的倒数第二个就行。

实现：

  1. import java.util.Arrays;
  2. public class BubbleSort {
  3.    //实现数组内两元素交换
  4.     public static void swap(int[]array,int i,int j){
  5.         int temp=array[i];
  6.         array[i]=array[j];
  7.         array[j]=temp;
  8.     }
  9.     //冒泡排序
  10.     public static void bubbleSort(int[]array){
  11.         int size=array.length;
  12.       //一开始控制进行两两比较的次数，最后一轮必定有序，所有比较次数为size-1次
  13.         for(int i=0;i<size-1;i++){
  14.             //一开始假设已经有序
  15.             boolean sort=true;
  16.             //两两比较过程
  17.             for(int j=0;j<size-1;j++){
  18.                 if(array[j]>array[j+1]){
  19.                     swap(array,j,j+1);
  20.                     //若发生交换则说明已经还未有序
  21.                     sort=false;
  22.                 }
  23.             }
  24.             if(sort==true){
  25.                 //一轮比较后未发生交换，说明已经有序
  26.                 return ;
  27.             }
  28.         }
  29.     }
  30.     public static void main(String[] args) {
  31.         int[]arr={1,3,5,0,8,2,6};
  32.         bubbleSort(arr);
  33.         System.out.println("冒泡排序："+Arrays.toString(arr));
  34.     }
  35. }

 执行结果：

 2.快速排序（交换排序之一）

示意图：

一秒教会你快速排序_你算哪块小饼饼干的博客-CSDN博客

原理：

从待排序的区间取一个基准值，比基准值大的放到基准值的右边，比基准值小的放到基准值的左边，对于左右两边，再次充分这样的步骤。

快速排序是冒泡排序的改进算法，它采用了分治的思想，将原问题划分为若干个规模更小的子问题，子问题的依旧与原问题是相似的，递归解决所有的子问题，也就解决了原问题。

步骤：

1.从待排序区间取一个数作为基准值

2.遍历待排序区间，把所有比基准值小的数放到基准值的左边，比基准值大的放到基准值的右边，这个过程使用专业的术语叫做parttion.

3.对于基准值的左右两边重复以上过程，直到整个序列变得有序。

实现：

  1. import java.util.Arrays;
  2. public class QuickSort {
  3.     public static void swap(int[]arr,int i,int j) {
  4.         int temp = arr[i];
  5.         arr[i] = arr[j];
  6.         arr[j] = temp;
  7.     }
  8.     private static void quickSort(int[]arr){
  9.         quickSortRange(arr,0,arr.length-1);
  10.  
  11.     }
  12.     private static void quickSortRange(int[]arr,int formIndex,int toIndex){
  13.         //求出要求数组区间的元素个数
  14.         int size=toIndex-formIndex+1;
  15.         if(size<=1){
  16.             return;
  17.         }
  18.         int pivotIdx=partition(arr,formIndex,toIndex);
  19.         quickSortRange(arr,formIndex,pivotIdx-1);
  20.         quickSortRange(arr,pivotIdx+1,toIndex);
  21.     }
  22.     //partition Hoare法
  23.     private static int partition(int[]arr,int formIndex,int toIndex){
  24.  
  25.         int lefIdx=formIndex;
  26.         int rigIdx=toIndex;
  27.  
  28.         int pivot=arr[toIndex];
  29.  
  30.         while(rigIdx>lefIdx){
  31.             while(rigIdx>lefIdx&&arr[lefIdx]<=pivot){
  32.                 lefIdx++;
  33.             }
  34.             //此循环结束说明找到了大于基准值的元素
  35.             while(rigIdx>lefIdx&&arr[rigIdx]>=pivot){
  36.                 rigIdx--;
  37.             }
  38.             //此循环结束说明找到了小于基准值的元素
  39.             swap(arr,lefIdx,rigIdx);
  40.  
  41.         }
  42.         swap(arr,lefIdx,toIndex);
  43.         return lefIdx;
  44.     }
  45.  
  46.  
  47.   //检测：
  48.     public static void main(String[] args) {
  49.         int[]arr={1,5,2,4,8,3,7,10};
  50.         quickSort(arr);
  51.         System.out.println(Arrays.toString(arr));
  52.  
  53.     }
  54. }

运行结果：

 3.直接选择排序（选择排序之一）

示意图：

原理：

每一次从无序区间选出最大（或者最小）的元素，放在有序区间的最后（或者无序区间的最前），直到所有的元素有序。

步骤：（此步骤针对无序区间在前，有序区间在后）

1.找到到无序区间的最大值元素的下标

2.将无序区间最大值元素的下标交换到有序区间的最后一个

3.重复此过程，直到数组有序

实现：

  1. import java.util.Arrays;
  2. public class SelectSort {
  3.     private static void swap(int[]arr,int i,int j){
  4.  
  5.         int temp=arr[i];
  6.         arr[i]=arr[j];
  7.         arr[j]=temp;
  8.     }
  9.    //直接选择排序（无序区间在前，有序区间在后的写法）
  10.     public static void selectSort(int[]arr,int size) {
  11.         //外层需要选择size-1次
  12.         for (int i = 0; i < size - 1; i++) {
  13.             //无序区间 [0,size-i)
  14.  
  15.             //有序区间 [size-i,size)
  16.             //要找到一个最大值下标，可以先假设最大值下标，再拿其他与它比较
  17.             int maxIdx = 0;
  18.             //遍历整个无序区间
  19.             int j=0;//已经取了第一个元素为最大
  20.             //遍历时从第二个元素开始遍历
  21.             for( j=1;j<size-i;j++){
  22.                 if(arr[maxIdx]<arr[j]){
  23.                     //找到无序区间最大元素的下标
  24.                    maxIdx=j;
  25.  
  26.                 }
  27.             }
  28.            //每一次选择到最大下标之后 将它交换到无序区间的最后一个
  29.             //无序区间的最后一个下标 size-i-1
  30.             swap(arr,maxIdx,size-i-1);
  31.         }
  32.     }
  33.     //直接选择排序（有序区间在前，无序区间在后）
  34.     public static void selectSort2(int[]arr,int size){
  35.         for(int i=0;i<size-1;i++){
  36.             //有序区间 [0,i)
  37.             //无序区间 [i,size)
  38.             int minIdx=i;
  39.             int j=i;
  40.             for( j=i+1;j<size;j++){
  41.                 if(arr[minIdx]>arr[j]){
  42.                     minIdx=j;
  43.                 }
  44.             }
  45.             //找到无序区间的最小值以后，交换到无序区间的第一个元素
  46.             swap(arr,minIdx,i);
  47.         }
  48.  
  49.     }
  50.     //直接选择排序（左边为有序区间，中间为无序区间，右边为无序区间）
  51.     //每次找出最大与最小，最大往右边有序区间移，最小往左边有序区间移
  52.  
  53.     public static void selectSort3(int[]arr,int size){
  54.  
  55.  
  56.     }
  57. //简单测试：
  58.     public static void main(String[] args) {
  59.         int[]arr={9,8,5,9,2,3,4};
  60.         selectSort2(arr, arr.length);
  61.         System.out.println(Arrays.toString(arr));
  62.     }
  63.  
  64. }

简单测试结果：

4.堆排序（选择排序之一）

示意图：

原理：

堆排序也是选择排序中的一种，找到无序区间中的最大值（或者最小值），将它交换到有序区间的最后（或者无序区间的最前）。与直接选择排序最大的不同在于，它不在使用遍历的方式来寻找无序区间的最大值（或最小值），而是通过创建堆的方式来创建最大值（或者最小值）。

步骤：

1.创建堆，要创建堆，先实现向下调整。

2.创建堆以后，堆顶元素就是最大值，找到了最大值就将它交换到最后，放到无序区间的最后

3.放到无序区间最后以后，再从堆顶进行向下调整，调整长度减掉有序区间的长度

实现：

  1. import java.util.Arrays;
  2. public class HeapSort{
  3.  
  4.     // 堆排序
  5.        public static void heapSort(int[] array){
  6.         createHeap(array);
  7.         for(int i=0;i<array.length;i++){
  8.   //将堆顶元素交换到无序区间的最后，再从堆顶开始向下调整
  9.             swap(array,0,array.length-1-i);
  10.             shiftDown2(array, array.length-1-i,0);
  11.         }
  12.     }
  13.  
  14.     //创建堆
  15.         public static void createHeap(int[]array){
  16.         int size=array.length;
  17.         //创建堆需要从倒数第一个根结点开始向下调整
  18.         int i=(size-1-1)/2;
  19.         for(;i>=0;i--){
  20.             //创建最大堆
  21.             shiftDown2(array,array.length,i);
  22.         }
  23.         }
  24.  
  25.      //最大堆向下调整
  26.         public static void shiftDown2(int[]array,int size,int index){
  27.  
  28.         while(true){
  29.           int leftIdx=2*index+1;
  30.           if(leftIdx>=size){
  31.               return;
  32.           }
  33.           int maxIdx=leftIdx;
  34.           if(leftIdx+1<size&&array[leftIdx+1]>array[leftIdx]){
  35.               maxIdx=leftIdx+1;
  36.           }
  37.           if(array[maxIdx]<=array[index]){
  38.               return ;
  39.           }
  40.           swap(array,maxIdx,index);
  41.           index=maxIdx;
  42.        }
  43.       }
  44.  
  45.         public static void main (String[]args){
  46.            //简单测试
  47.  
  48.             int[] arr2 = {27, 15, 19, 18, 28, 34, 65, 49, 25, 37};
  49.             shiftDown(arr2, 0,arr2.length);
  50.             System.out.println("向下调整："+Arrays.toString(arr2));
  51.  
  52.             int[]arr3={8,4,6,5,1,3};
  53.             createHeap(arr3);
  54.             System.out.println("创建堆："+Arrays.toString(arr3));
  55.  
  56.             int[]arr4={1,0,9,55,4,5,8,3};
  57.             heapSort(arr4);
  58.             System.out.println("堆排序"+Arrays.toString(arr4));
  59.  
  60.         }
  61. }

简单测试结果:

5.直接插入排序（插入排序之一）

示意图

原理：

每次在无序区间选择无序区间的第一个元素，在有序区间找到合理的位置插入。可以将它想象成平时打牌我们对于扑克牌的排序。

步骤：

1.遍历整个无序区间，循环选择无序区间的第一个元素

2.在有序区间找到合适的位置，进行插入即可。（在插入时，要提前把不合适的位置往后搬）

实现：

  1. import java.util.Arrays;
  2.  
  3. //插入排序
  4. public class InsertSort {
  5.  
  6.     //对数组全部做插入排序
  7.     public static void insertSort(int[]arr,int size){
  8.         //一开始认为第一个数已经有序
  9.         for(int i=1;i<size;i++){
  10.             //有序区间 [0,i)
  11.             //无序区间 [i,size)
  12.             //再倒着遍历有序区间，找到合适插入位置
  13.             int key=arr[i];
  14.             int j=i-1;
  15.             for( j=i-1;j>=0&&key<arr[j];j--){
  16.                 //要提前把不合适的位置往后搬
  17.                 arr[j+1]=arr[j];
  18.             }
  19.             //循环结束，表明key>=arr[j]找到了合适的插入位置
  20.             //找到key>=arr[j]后，插入到arr[j]的后面就是arr[j+1]位置
  21.             arr[j+1]=key;
  22.         }
  23.     }
  24.     //对指定范围做插入排序
  25.     public static void insertSort2(int[]arr,int formIndex,int toIndex){
  26.         int n=toIndex-formIndex;
  27.         for(int i=1;i<n;i++){
  28.             //有序区间 [formIndex,formIndex+i)
  29.             //无序区间 [formIndex+i,size)
  30.             //插入的有序区间的元素下标[formIndex+i]
  31.  
  32.             int key=arr[i];
  33.             //要先保存无序区间需要拿出的去插入的元素
  34.             int j=formIndex+i-1;
  35.             //倒着遍历有序区间，能够提前把不合适的位置往后移动，找到合适的插入位置
  36.             for(j=formIndex+i-1;j>=formIndex&&key<arr[j];j--){
  37.                 arr[j+1]=arr[j];
  38.             }
  39.             //循环结束 表明找到了合适的插入位置
  40.             arr[j+1]=key;
  41.         }
  42.     }
  43.    //简单测试
  44.     public static void main(String[] args) {
  45.         int[]arr={2,7,5,9,1,5,8};
  46.         insertSort(arr, arr.length);
  47.         System.out.println("插入排序："+Arrays.toString(arr));
  48.         int []arr2=arr;
  49.         insertSort2(arr,0,7);
  50.         System.out.println("插入排序："+Arrays.toString(arr2));
  51.  
  52.     }
  53. }

简单测试结果：

6.希尔排序（插入排序之一）

第 7 章 排序算法_OnebyWang的博客-CSDN博客

原理：

希尔排序还叫做缩小增量排序。它开始先选定一个增量gap，把间隔为增量gap的数分为一组，对每个组内进行插入排序。一次排序完成后，缩小增量，再次分组，再次对每个组内进行插入排序。当增量gap==1，说明数组已经有序。

步骤：

1.确定增量，根据增量进行分组。

2.对每组内元素进行插入排序。

3.完成上两步后缩小增量，再次循环进行

4.当增量==1，数组有序，排序结束

  1. import java.util.Arrays;
  2.  
  3. public class ShellSort {
  4.     //希尔排序
  5.  
  6.     private static void shellSort(int[]arr){
  7.         //假设有10个元素就分5组
  8.         int group= arr.length/2;
  9.         //分组后循环对每个组内的元素进行插入排序
  10.         while(true){
  11.             insertSortWithGroup(arr,group);
  12.             if(group==1){
  13.                 //如果只剩一组说明已经有序
  14.                 return;
  15.             }
  16.             //每次排序后再分组
  17.             group=group/2;
  18.         }
  19.     }
  20.  
  21.     //希尔排序分组后对每一组的插入排序方法
  22.     private static void insertSortWithGroup(int[]arr,int group){
  23.  
  24.         for(int i=group;i< arr.length;i++){
  25.             int key=arr[i];
  26.             int j=i-group;
  27.             for( j=i-group;j>=0&&key<arr[j];j=j-group){
  28.                 arr[j+1]=arr[j];
  29.             }
  30.             arr[j+group]=key;
  31.         }
  32.     }
  33. //简单测试
  34.     public static void main(String[] args) {
  35.         int[]arr={1,5,6,8,7,5,1,};
  36.         shellSort(arr);
  37.         System.out.println("希尔排序："+Arrays.toString(arr));
  38.     }
  39.  
  40. }

简单测试结果：

7.归并排序

示意图：

原理：

归并排序的原理是原序列先分割成一个一个的小的子序列，先使每个子序列有序，再将子序列合并，得到一个完整的有序序列，这就是归并排序。

（我这里采用二路归并）步骤：

1.先将原来的无序序列分割成若干个子序列，当分割到一个序列里只有一个元素时说明分割完毕。

2.再将分割后的子序列不断归并，归并的原理是合并两个有序的子序列，一直归并，直到归并得到一个完整的序列。

实现：

  1. import java.util.Arrays;
  2. public class MergeSort {
  3.     public static void mergeSort(int[] array){
  4.         mergeSortFunc1(array,0,array.length-1);
  5.     }
  6.     public static void mergeSortFunc1(int[]array,int left,int right){
  7.         //开始先分割
  8.         if(left>=right){
  9.             return ;
  10.         }
  11.         int mid=(left+right)/2;
  12.         //递归左区间和递归右区间分割
  13.         mergeSortFunc1(array,left,mid);
  14.         mergeSortFunc1(array,mid+1,right);
  15.         //分割后合并
  16.         merge(array,left,mid,right);
  17.  
  18.     }
  19.      // 合并原理：合并两个有序数组
  20.     public static void merge(int[]array,int start,int mid,int end){
  21.  
  22.         //先分别找出两个数组中第一个更小的元素，将更小的元素搬到
  23.         //额外空间
  24.         int[] extra=new int[end-start+1];
  25.  
  26.         int i=start;
  27.         int j=mid+1;
  28.         int k=0;
  29.         //两个数组都还有元素时
  30.         while(i<=mid&&j<=end){
  31.             if(array[i]<=array[j]){
  32.                  extra[k++]=array[i++];
  33.             }else {
  34.                 extra[k++] = array[j++];
  35.             }
  36.         }
  37.         //当有一个数组已经搬完时，需要判断哪个数组搬完了
  38.         while(i<=mid){
  39.             //把没有搬完的数组全部搬到额外数组
  40.             extra[k++]=array[i++];
  41.         }
  42.         while(j<=end){
  43.             //把没有搬完的数组全部搬到额外数组
  44.           extra[k++]=array[j++];
  45.         }
  46.         //全部搬到额外空间时，再搬回原数组
  47.  
  48.         for(int n=0;n<extra.length;n++){
  49.             //原来的数组不一定是从零开始
  50.             array[start+n]=extra[n];
  51.         }
  52.     }
  53. //简单测试
  54.     public static void main(String[] args) {
  55.         int[] array={1,5,1,0,6,88,-5,0,64};
  56.         mergeSort(array);
  57.         System.out.println(Arrays.toString(array));
  58.  
  59.     }
  60. }

 简单测试结果：

以上就是7种常见的排序算法，对于排序算法，必须需要掌握它们的基本原理，只有知道了它们的基本原理，我们才能够根据原理写出对应的实现代码。

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

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

  

闽ICP备14008679号